Перший тур

Розв’язки задач відправляти з 26.09 по 9.10.2011 р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

1. Задача Цегляна стіна (20 балів)

Ім’я вхідного файлу: BRICK.DAT

Ім’я вихідного файлу: BRICK.SOL

Максимальний час роботи на одному тесті: 1с

Щоб розділити царство царя Гороха необхідно побудувати цегляну стіну висотою 2 і завдовжки n (висота цеглини дорівнює 2, ширина – 1).

Ваше завдання - написати програму, яка визначає, скільки шаблонів, можливо отримати для стіни завдовжки n.

Вхідний файл містить одне ціле число N (1<=N<=32767).

Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне кількості шаблонів, які можна отримати для стіни завдовжки n.

Приклад

2. Задача Драбина навпаки(100 балів)

Ім’я вхідного файлу: STAIR.DAT

Ім’я вихідного файлу: STAIR.SOL

Максимальний час роботи на одному тесті: 10с

Васі було дано завдання розв’язати задачу про драбину.

Драбина складається із n сходинок. Знаходячись на першій з них, можна дістатися до останньої сходинки з номером n. При цьому за один хід можна піднятись тільки на одну або дві сходинки вперед. На жаль, деякі сходинки зламалися і на них не можна ступати. Знаючи, які сходинки зламалися і вважаючи, що перша і остання сходинки не зламані, можна знайти число шляхів якими можна перейти з першої сходинки до останньої. Вася швидко впорався з рішенням цієї задачі і придумав до неї зворотну.

Вам пропонується вирішити зворотне завдання. А саме, знайти такий опис сходинок драбини, для якої число різних шляхів дорівнює k.

Формат вхідного файлу

Вхідний файл містить два цілих числа n і k (2 ≤ n ≤ 1000, 0 ≤ k ≤ 10^¹⁸) — число сходинок та різних шляхів, відповідно.

Формат вихідного файлу

В єдиному рядку вихідного файлу виведіть через пробіл n чисел — опис сходинок.

Поломаній сходинці відповідає число 0, цілій — 1. Перша та остання сходинки повинні бути цілими. Якщо існує декілька відповідей то виведіть будь-яку.

Якщо відповіді не існує, то виведіть у вихідний файл єдине слово «Impossible».

Приклад