Написання програм PIPELINE, BUS і LOTO (Завдання першого туру XII Всеукраїнської олiмпiади з iнформатики)

XII Всеукраїнська олімпіада з інформатики

Перший тур

1.  Конвейєр

Для транспортування матеріалів з цеху А до цеху В використовується конвейєр. Матеріали пакуються в однакові контейнери та розміщуються на стрічці один за одним в порядку виготовлення в цеху А. Кожен контейнер має ступінь терміновості обробки в цеху В. Для впорядкування контейнерів за ступенем терміновості використовують накопичувач, який знаходиться в кінці конвейєра перед входом до цеху В. Накопичувач працює покроково, на кожному кроці можливі такі дії:

накопичувач переміщує перший контейнер зі стрічки до цеху В;

накопичувач переміщує перший контейнер зі стрічки у сховище (у сховищі кожен наступний контейнер поміщується на попередній);

накопичувач переміщує верхній контейнер зі сховища до цеху В.

Завдання Написати програму 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

2.  Новини

У місті введено рух автобусів. Усі автобуси мають циклічні маршрути. Деякі маршрути мають спільні зупинки. Коли два або більше автобусів зустрічаються на деякій зупинці, водії обмінюються усіма новинами, які їм відомі на цей момент (після того як вони виїдуть із зупинки, всі будуть знати однакові новини).

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

Рух автобусів синхронізовано в тому розумінні, що час, необхідний для переїзду з однієї зупинки до іншої, однаковий для всіх автобусів.

Існує D водіїв (та, відповідно, D автобусів), які занумеровані від 1 до D, та S зупинок, які мають номери від 1 до S.

Завдання Написати програму BUS, яка визначить, чи може кожен водій знати всі новини від своїх колег, якщо тривалість знаходження на маршруті необмежена.

Вхідні дані Вхідний текстовий файл BUS.DAT  у першому рядку містить кількість тестів N. Далі слідують N блоків інформації, кожен з яких відповідає одному тесту. Перший рядок блоку містить два цілих числа D (1£D£100) та S (1£S£250). Кожен з наступних D рядків описує маршрут одного з автобусів таким чином: перше число — кількість зупинок на даному маршруті M_i, після чого M_i різних цілих чисел, які задають послідовність зупинок маршруту. Рух автобуса починається з зупинки, що вказана першою.

Приклад вхідних даних

2

1 3

3 1 2 3

2 2

2 1 2

2 2 1

Вихідні дані Кожен рядок текстового файлу BUS.SOL має містити відповідь для одного тесту. Необхідно вивести 1, якщо кожен з водіїв знатиме всі новини, або 0 в іншому випадку.

Приклад вихідних даних

1

0

3.  Лото

Досить популярною є лотерея, що проводиться за такими правилами: з набору N кульок випадково вибирається K кульок, які є виграшними. Виграють гравці, які передбачили вибір саме цих кульок. Неважко підрахувати кількість C варіантів вибору K кульок з набору N кульок.

Завдання Написати програму LOTO яка визначить, яку саме кількість кульок треба брати з набору N кульок, якщо кількість варіантів вибору є C.

Вхідні дані Вхідний текстовий файл LOTO.DAT містить в єдиному рядку два числа — N та C (1£N£500000).

Приклад вхідних даних

15 5005

Вихідні дані Єдиний рядок текстового файлу LOTO.SOL має містити число K — кількість кульок, які треба брати.

Приклад вихідних даних

6