Перший тур
Конвейєр
Для транспортування матеріалів з цеху А до
цеху В використовується конвейєр.
Матеріали пакуються в однакові контейнери та розміщуються на стрічці
один за одним в порядку виготовлення в цеху А. Кожен контейнер має
ступінь терміновості обробки в цеху В. Для впорядкування контейнерів
за ступенем терміновості використовують накопичувач, який знаходиться
в кінці конвейєра перед входом до цеху В. Накопичувач працює покроково,
на кожному кроці можливі такі дії:
- накопичувач переміщує перший контейнер зі стрічки до цеху В;
- накопичувач переміщує перший контейнер зі стрічки у сховище (у сховищі кожен наступний контейнер поміщується на попередній);
- накопичувач переміщує верхній контейнер зі сховища до цеху В.
Завдання: Написати програму PIPELINE, яка за послідовністю
контейнерів визначить, чи можна впорядкувати їх за ступенем
терміновості за допомогою описаного накопичувача.
Вхідні дані: Вхідний текстовий файл PIPELINE.DAT в першому
рядку містить кількість тестів N. Далі слідують N рядків,
кожен з яких описує окремий тест і містить ціле число K (1(K(10000)
- кількість контейнерів в послідовності та K дійсних чисел - ступенів
терміновості контейнерів в порядку їх надходження з цеху А.
Приклад вхідних даних
2
2 2.9 2.1
3 5.6 9.0 2.0
Вихідні дані: Кожен рядок текстового файлу PIPELINE.SOL
має містити відповідь для одного тесту. Необхідно вивести 1, якщо
необхідне впорядкування можливе, або 0 в іншому випадку.
Приклад вихідних даних
1
0
Новини
У місті введено рух автобусів. Усі автобуси мають циклічні маршрути.
Деякі маршрути мають спільні зупинки. Коли два або більше автобусів
зустрічаються на деякій зупинці, водії обмінюються усіма новинами,
які їм відомі на цей момент (після того як вони виїдуть із зупинки,
всі будуть знати однакові новини).
Водії починають рух своїх автобусів у однаковий час, і в цей час
кожен з водіїв знає одну новину, яку не знає жоден з інших.
Рух автобусів синхронізовано. Час, необхідний для переїзду з однієї
зупинки до іншої, однаковий для всіх автобусів.
Існує D водіїв (та, відповідно, D автобусів), які занумеровані від 1 до D,
та S зупинок, які мають номери від 1 до S.
Завдання: Написати програму BUS, яка визначить, чи може кожен
водій знати всі новини від своїх колег, якщо тривалість знаходження
на маршруті необмежена.
Вхідні дані: Вхідний текстовий файл BUS.DAT у першому рядку
містить кількість тестів N. Далі слідують N блоків інформації, кожен
з яких відповідає одному тесту. Перший рядок блоку містить два цілих
числа D (1(D(100) та S (1(S(250). Кожен з наступних D рядків описує
маршрут одного з автобусів таким чином: перше число - кількість зупинок
на даному маршруті Mi, після чого Mi різних цілих чисел, які задають
послідовність зупинок маршруту. Рух автобуса починається з зупинки,
що вказана першою.
Приклад вхідних даних
2
1 3
3 1 2 3
2 2
2 1 2
2 2 1
Вихідні дані: Кожен рядок текстового файлу BUS.SOL має
містити відповідь для одного тесту. Необхідно вивести 1, якщо
кожен з водіїв знатиме всі новини, або 0 в іншому випадку.
Приклад вихідних даних
1
0
Лото
Досить популярною є лотерея, що проводиться за такими правилами:
з набору N кульок випадково вибирається K кульок, які є виграшними.
Виграють гравці, які передбачили вибір саме цих кульок.
Неважко підрахувати кількість C варіантів вибору K кульок з
набору N кульок.
Завдання: Написати програму LOTO яка визначить, яку саме кількість кульок
треба брати з набору N кульок, якщо кількість варіантів вибору є C.
Вхідні дані: Вхідний текстовий файл LOTO.DAT містить в
єдиному рядку два числа - N та C (1(N(500000).
Приклад вхідних даних
15 5005
Вихідні дані: Єдиний рядок текстового файлу LOTO.SOL має
містити число K - кількість кульок, які треба брати.
Приклад вихідних даних
6
Другий тур
Парк
Напередодні виборів мер міста вирішив заснувати парк відпочинку.
В центрі міста з цією метою було звільнено майданчик, який має форму
рівнобічного трикутника. За перемогу у виборах змагаються N політичних
партій. Щоб підкреслити свою незалежність, мер наказав посадити в парку
дерева N різних кольорів. Дерева мають бути розташовані в вузлах
трикутної сітки (див. малюнок) на однаковій відстані одне від одного.
В кожному рядку, що паралельний одній із сторін трикутника, повинні
рости дерева попарно різних кольорів, зовнішні рядки майданчика мають
містити рівно N дерев, тобто дерева всіх кольорів.
Завдання: Написати програму PARK, яка буде знаходити одне з можливих розташувань
дерев у парку.
Вхідні дані: Вхідний текстовий файл PARK.DAT у першому рядку
містить кількість тестів. Кожен наступний рядок містить одне ціле число
N - кількість видів (кольорів) дерев, які необхідно посадити в парку
(3(N(100).
Приклад вхідних даних
2
3
4
Вихідні дані: Вихідний текстовий файл PARK.SOL має містити
відповіді для всіх тестів з вхідного файлу в тому ж порядку.
Для кожного тесту необхідно вивести або єдиний рядок з числом 0,
якщо розташування неможливе, або N рядків, перший з яких містить
одне число, другий - два числа, N-й - N чисел - номерів кольорів дерев
у розташуванні. Кольори нумеруються натуральними числами від 1 до N.
Приклад вихідних даних
2
3 1
1 2 3
0
Печера
Гном Торин знайшов план кинутої печери, в якій мешкав гірський король
Норус. На плані позначено місце, де знаходиться величезний скарб. Гірський король захистив
своє багатство від шукачів скарбів, для чого розташував в печері L кам'яних блоків, що
рухаються і можуть роздушити шукача, і які зупиняються коли скарб знайдено.
План подано у вигляді пpямокутної цілочисельної
матpиці MxN, елементами якої може бути:-2 (скарб), -1 (стіна), 0
(порожнє місце), додатнє число K (елемент K-го блока). K-ий блок
складається з усіх
елементів, які позначені числом K. Блок не обов'язково зв'язаний, але
всі його елементи рухаються синхронно. Нулі в крайніх рядках або
стовпчиках матpиці означають входи до печери. Окремо вказано початковий
напрямок руху кожного блоку (1 - вгору, 2 - праворуч, 3 - вниз, 4 -
ліворуч).
Гном займає клітину-вхід. Після цього він рухається за такими правилами:
на протязі кожної секунди пеpшим переміщується гном на пусту клітину з
4-х сусідніх (вгору, вниз, ліворуч чи праворуч) або залишається на місці.
Потім на протязі тієї ж секунди переміщується кожен блок на одну клітину
(вгору, праворуч, вниз, ліворуч): спочатку перший, за ним другий і т.д.
Якщо перед будь-яким із елементів блока у напрямку його руху знаходиться
стіна, край печери, скарб або інший блок, то на цьому ході блок не
рухається, а напpямок його руху змінюється на протилежний.
Якщо блок під час руху потрапив в клітину з гномом, то гном загине.
Завдання: Написати програму CAVE для пошуку безпечного шляху, який приведе
до скарбу за найменший час, вважаючи, що такий шлях існує.
Вхідні дані: Вхідний текстовий файл CAVE.DAT в першому рядку містить числа M, N
та L-кількість блоків (3(M(75, 3(N(75, 3(L(1000). В наступних M рядках міститься по
N цілих чисел - план печери. В наступних L рядках задано початкові напpямки руху
блоків у порядку зpостання їх номерів.
Приклад вхідних даних
4 5 1
-1 -1 -1 -1 -1
-1 0 1 0 -1
0 0 0 -2 -1
-1 -1 -1 -1 -1
1
Вихідні дані: Вихідний текстовий файл CAVE.SOL у першому рядку має містити
число K - час пpоходження шляху в секундах. В наступних K+1 рядках - координати положення
гнома в кожну секунду (починаючи з координат входу). Координати мають бути подані в порядку
"рядок стовпчик". Якщо існує кілька шляхів, досить вказати один із них.
Приклад вихідних даних
5
3 1
3 2
2 2
2 3
2 4
3 4
|
