Начало
Лето 9
A. Результаты квалификации B. Развлечение с калькулятором C. Скорость воробьев D. Соединительная линия E. Самый острый угол F. Однокоренные слова G. Дробь в LATeX-е H. Brownie Points I I. Magic Bitstrings J. Brownie Points II
I. Magic Bitstrings
Задачи на идеюТехника программирования, моделирование
Олимпиадные задачи на английском языке
| 03/07/2008 | Лето 2008 дорешивание ( 9I) |
| 21/07/2008 | Лето 2008 - 9 (I) |
Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
A bitstring, whose length is one less than a prime, might be
magic. 1001 is one such string. In order to see the
magic in the string let us append a non-bit x to it,
regard the new thingy as a cyclic string, and make this
square matrix of bits
| each bit | 1001 |
| every 2nd bit | 0110 |
| every 3rd bit | 0110 |
| every 4th bit | 1001 |
This matrix has the same number of rows as the length of the original
bitstring. The `m`-th row of the matrix has every `m`-th
bit of the original string starting with the `m`-th bit. Because
the enlarged thingy has prime length, the appended x
never gets used.
If each row of the matrix is either the original bitstring or its complement,
the original bitstring is magic.
Each line of input (except last) contains a prime number
`p\ ≤\ 100\ 000`. The last line contains 0 and this
line should not be processed. For each prime number from the input
produce one line of output containing the lexicographically smallest,
non-constant magic bitstring of length `p-1`, if such a
string exists, otherwise output "Impossible".
Sample Input
5 3 17 47 2 79 0
Sample Output
0110 01 0010111001110100 0000100001101010001101100100111010100111101111 Impossible 001001100001011010000001001111001110101010100011000011011111101001011110011011
