History of OI -> VI OI 1998/1999 -> Problems

 News 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 Stage III - results Stage II - results Stage I - results Problems Regulations Organization Hints Schedule Stats 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 Links SIO MAIN
Niebieskie ksi.eczki
 VI Olimpiada Informatyczna 1998/1999

Monodigital representations

 I stage contest

Let K be a decimal digit different from 0. We say that an arithmetic expression is a K-representation of the integer X if a value of this expression is X and if it contains only numbers composed of a digit K. (All the numbers are of course decimal). The following arithmetical operations are allowed in the expression: addition, subtraction, multiplication and division. Round brackets are allowed too. Division may appear only when a dividend is a multiple of a divisor.

#### Example

Each of the following expressions is the 5-representation of the number 12:

• 5+5+(5:5)+(5:5)
• (5+(5))+5:5+5:5
• 55:5+5:5
• (55+5):5

The length of the K-representation is the number of occurrences of digit K in the expression. In the example above the first two representations have the length 6, the third - 5, and the forth - 4.

Write a program which:

• reads the digit K and the series of numbers from the text file MON.IN,
• verifies for each number from the series, whether it has a K-representation of length at most 8, and if it does, then the program finds the minimal length of this representation,
• writes results in the output file MON.OUT.

#### Input

The first line of the input file MON.IN contains digit K, K is en element of {1,...,9}. The second line contains number n, 1<=n<=10. In the following n lines there is the series of natural numbers a1,...,an, 1<=ai<=32000 (for i=1,..,n), one number in each line.

#### Output

The file MON.OUT composes of n lines. The i-th line should contain:

• exactly one number which is the minimal length of K-representation of ai, assuming that such a representation of length not grater then 8 exists,
• one word NIE (means 'no' in Polish), if the minimal length of the K-representation of the number ai is grater than 8.

#### Example

For the input file MON.IN:

```5
2
12
31168
```

the correct answer is the text file MON.OUT:

```4
NIE
```

Your program should look for the file MON.IN in the current directory and produce the output file MON.OUT in current directory too. The file containing source code of your program should have a name MON.???, whereas you should put three-letter abbreviation of used programming language name instead of ???. The same program in executable form should be written in file MON.EXE

Print friendly version