05/12/2025 14:59:16

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1013. Magic Bitstrings

Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Sample Output

0110
01
0010111001110100
0000100001101010001101100100111010100111101111
Impossible
001001100001011010000001001111001110101010100011000011011111101001011110011011

Source: Don Reble, Waterloo/Alberta local contest, 2004

03/07/2008	Лето 2008 дорешивание ( 9I)
21/07/2008	Лето 2008 - 9 (I)