| Яндекс.Алгоритм 2011: Раунд 2 |
|---|
| Закончено |
Будем называть рекуррентной двоичной последовательностью бесконечную последовательность (a0, a1, ...) из нулей и единиц, задающуюся соотношением:
— заранее фиксированные коэффициенты и n ≥ k. Будем считать, что не все ci нули.Заметим, что такая последовательность однозначно восстанавливается из любого своего k-кортежа {as, as + 1, ..., as + k - 1}, поэтому в частности она является периодической. Более того, если в кортеже содержатся только нули, тогда и сама последовательность состоит лишь из нулей, что не очень-то интересно. В противном случае, период последовательности не превосходит 2k - 1, так как любой k-кортеж однозначно определяет следующий элемент, и существует всего 2k - 1 ненулевых k-кортежей. Будем называть последовательность длинной, если ее минимальный период в точности равен 2k - 1. Вам требуется по данному k предъявить длинную последовательность или определить, что ее не существует.
В единственной строке содержится одно целое число k (2 ≤ k ≤ 50).
Если для данного k не существует длинной последовательности, выведите одно число «-1» (без кавычек). Иначе первая строка вывода должна содержать коэффициенты: c1, c2, ..., ck. Вторая строка должна содержать первые k элементов последовательности: a0, a1, ..., ak - 1. Все числа (элементы и коэффициенты) должны быть 0 или 1, причем хотя бы один коэффициент должен быть 1.
Если решений несколько, выведите любое.
2
1 1
1 0
3
0 1 1
1 1 1
1. В первом случае: c1 = 1, c2 = 1, поэтому an = an - 1 + an - 2 (mod 2). Получается последовательность:
с периодом 3 = 22 - 1.
2. В втором случае: c1 = 0, c2 = 1, c3 = 1, поэтому an = an - 2 + an - 3 (mod 2). Последовательность имеет вид:
ее период равен 7 = 23 - 1.
Периоды окрашены в разные цвета.
