Polish version    English version  
  History of OI

 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery

Task: ban


I stage competition  
Source file: ban.xxx (xxx=pas,c,cpp)
Memory limit: 32 MB

Alternative formats: PostScript | PDF

The BBB (short for Byteotian Bit Bank) owns the largest net of cash dispensers in Byteotia. The clients of the BBB can draw their money from the cash dispensers on the basis of a cash card and a 4-digit PIN code. Lately, in order to increase their clients' security, the BBB has had a camera installed by each cash dispenser. The cameras transmit the recorded image to the BBB using radio signals. Unfortunatelly, the signals are being intercepted by a gang of computer thieves. The thieves attempt to discover the 4-digit PIN codes of the BBB clients, whose cash cards they subsequently steal. Being aware of this fact, the BBB clients try to perform redundant movements over the keyboard while enetring the PIN. The camera is not able to pick out the keystrokes, it only records the finger movements. Consequently, it is usually not possible to determine the PIN unambiguously. For instance, the client moving his finger over the key "1" and then over the key "5" could have entered the following PIN codes: 1111, 1115, 1155, 1555, 5555. Desperate thieves glean the camera recordings, counting on being able to determine the PIN of a client or at least limiting the number of possible codes on the basis of multiple recordings of his transactions. Having accumulated sequences entered by a particular wealthy client of the BBB, they made you an "unnegotiable proposition".


Write a programme which:

  • reads from the standard input a description of the recorded sequences of finger movements, which the client has performed whilst entering his PIN,
  • determines the number of distinct PIN codes, which the client can have (i.e. the number of those 4-digit PIN codes, which could have been entered by performing the given finger movement sequences),
  • writes the outcome to the standard output.


The first line of the standard input contains a single integer n denoting the number of recorded scenes depicting the action of entering the PIN by the client, 1 <=n <= 1000. In the following n lines there are descriptions of these scenes, a single one per line. The description of each scene consists of two positive integers separated by a single space. The first of those numbers, t, denotes the length of the sequence of movements, 1 <= t <= 10,000. The other is a t-digit number, whose consecutive digits denote consecutive keys, over which the client has moved his finger. The total length of all sequences does not exceed 1,000,000.


The first and only line of the output should contain a single positive integer - the number of possible PIN codes of the client.


For the input data:

3 123
3 234

the correct outcome is:


Print friendly version