Polish version    English version  
  History of OI -> V OI 1997/1998 -> 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
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
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
V Olimpiada Informatyczna 1997/1998

Task: BAN
Author: Piotr Chrz±stowski-Wachtel
ATM's

III stage contest  

Every member of Byteland Credit Society is entitled to loan any amount of Bytelandish ducats unless it is 1030 or more, but he has to return the whole amount within seven days. There are 100 ATMs in the Client Service Room of the Society. They are numbered from 0 to 99. Every ATM can perform one action only: it can pay or receive a fixed amount. The i-th ATM pays 2i ducats if i is even or it receives 2i ducats if i is odd. If a client is going to loan a fixed sum of money it is necessary to check if he is able to get the money using every ATM at most once. If so, numbers of ATMs he has to use should be determined. It is also necessary to check if the client can return the money in a similar way, and if so, to determine numbers of ATMs he has to use.

Example

A client who is going to loan 7 ducats gets 16 ducats from the ATM No 4 and 1 ducat from the ATM No 0 and then he returns 8 ducats in the ATM No 3 and 2 ducats in the ATM No 1. In order to return the amount of 7 ducats he receives 1 ducat from the ATM No 0 and then he returns 8 ducats in ATM No 3.

Task

Write a program that:

  • reads the number of clients n from the text file BAN.IN and then, for every client reads from the same file the amount of money he is going to loan;
  • checks for every client if he is able to get the money using every ATM at most once and if so, determines the numbers of ATMs he has to use;
  • writes the results to the text file BAN.OUT.

Input

In the first line of the input file BAN.IN there is one positive integer n <= 1000, which equals the number of clients.
In each of the following n lines there is one positive integer less than 1030 (at most 30 decimal digits). The number in the i-th line describes the amount which the client i is going to loan.

Output

In each of 2n lines of the output file BAN.OUT there should be written a decreasing sequence of positive integers from the range [0..99] separated by single spaces, or one word NIE (which means NO in Polish):

  • In the first line of the i-th pair of lines there should be numbers of ATMs (in decreasing order) that the client i should use to get his loan or one word NIE if the loan cannot be received according to the rules;
  • In the second line of the i-th pair there should be numbers of ATMs (in decreasing order) which the client i should use to return his loan or the word NIE.

Example

For the text file BAN.IN:

2
7
633825300114114700748351602698

the correct answer is the output file BAN.OUT:
4 3 1 0
3 0
NIE
99 3 1



Print friendly version