0099. AntiGray Codes

Input file name:	antigray.in
Output file name:	antigray.out
Time limit:	1 s
Memory limit:	64 megabytes

Peter Q. Perverse is tired of Gray codes. So he has developed his own codes, called AntiGray codes. The AntiGray codes consist of all ternary numbers of length n. The only conditions are that each number differs from previous in all positions and every number occurs exactly once. Your task is to say whether the AntiGray codes for a given n exist, and if the answer is positive, to sample example AntiGray codes.

Input file

The input file consists of one integer number n (1 ≤ n ≤ 11).

Output file

If AntiGray codes for a given n do not exist, output a single word IMPOSSIBLE. Otherwise output all ternary numbers of length n in AntiGray order. Output file must not contain any spaces, each ternary number must consist of exactly n digits.

Examples:

antigray.in	antigray.out
1	1 0 2

Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version