Задання першого туру |
Написав Стеблевець Олександр Леонідович | ||||||||||||||||||||
Понеділок, 26 вересня 2011, 10:33 | ||||||||||||||||||||
Перший тур Розв’язки задач відправляти з 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^18) — число сходинок та різних шляхів, відповідно. Формат вихідного файлу В єдиному рядку вихідного файлу виведіть через пробіл n чисел — опис сходинок. Поломаній сходинці відповідає число 0, цілій — 1. Перша та остання сходинки повинні бути цілими. Якщо існує декілька відповідей то виведіть будь-яку. Якщо відповіді не існує, то виведіть у вихідний файл єдине слово «Impossible». Приклад
|
||||||||||||||||||||
Останнє оновлення на Вівторок, 27 вересня 2011, 19:07 |