Перший тур
Розв’язки задач відправляти з 26.09 по 9.10.2011 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача Цегляна стіна (20 балів)
Ім’я вхідного файлу: BRICK.DAT
Ім’я вихідного файлу: BRICK.SOL
Максимальний час роботи на одному тесті: 1с
Щоб розділити царство царя Гороха необхідно побудувати цегляну стіну висотою 2 і завдовжки n (висота цеглини дорівнює 2, ширина – 1).
Ваше завдання - написати програму, яка визначає, скільки шаблонів, можливо отримати для стіни завдовжки n.
Вхідний файл містить одне ціле число N (1<=N<=32767).
Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне кількості шаблонів, які можна отримати для стіни завдовжки n.
Приклад
BRICK.DAT
|
BRICK.SOL
|
1
|
1
|
2
|
2
|
3
|
3
|
2. Задача Драбина навпаки(100 балів)
Ім’я вхідного файлу: STAIR.DAT
Ім’я вихідного файлу: STAIR.SOL
Максимальний час роботи на одному тесті: 10с
Васі було дано завдання розв’язати задачу про драбину.
Драбина складається із n сходинок. Знаходячись на першій з них, можна дістатися до останньої сходинки з номером n. При цьому за один хід можна піднятись тільки на одну або дві сходинки вперед. На жаль, деякі сходинки зламалися і на них не можна ступати. Знаючи, які сходинки зламалися і вважаючи, що перша і остання сходинки не зламані, можна знайти число шляхів якими можна перейти з першої сходинки до останньої. Вася швидко впорався з рішенням цієї задачі і придумав до неї зворотну.
Вам пропонується вирішити зворотне завдання. А саме, знайти такий опис сходинок драбини, для якої число різних шляхів дорівнює k.
Формат вхідного файлу
Вхідний файл містить два цілих числа n і k (2 ≤ n ≤ 1000, 0 ≤ k ≤ 10^18) — число сходинок та різних шляхів, відповідно.
Формат вихідного файлу
В єдиному рядку вихідного файлу виведіть через пробіл n чисел — опис сходинок.
Поломаній сходинці відповідає число 0, цілій — 1. Перша та остання сходинки повинні бути цілими. Якщо існує декілька відповідей то виведіть будь-яку.
Якщо відповіді не існує, то виведіть у вихідний файл єдине слово «Impossible».
Приклад
STAIR.DAT
|
STAIR.SOL
|
|
|
3 1
|
1 0 1
|
3 2
|
1 1 1
|
4 0
|
1 0 0 1
|
566 239
|
Impossible
|
|