Polish version    English version  
  History of OI -> VI OI 1998/1999 -> Problems

 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
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
Niebieskie ksi.eczki
VI Olimpiada Informatyczna 1998/1999

Task: MON
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.


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. 


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. 


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. 


For the input file MON.IN: 


the correct answer is the text file MON.OUT:


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