1. 2000 рік

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

Перший тур

 

Є послідовність, що складається з 2N натуральних чисел. Відомо, що всі числа з цієї послідовності можна поділити на пари таким чином, що сума чисел у всіх парах буде однакова. Наприклад, числа послідовності 99, 23, 77, 1 можна поділити на пари 1+99=77+23.

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

Вхідні дані Файл SEQ.DAT містить дані кількох тестів. Перший рядок містить натуральне число - кількість тестів у файлі. Перший рядок кожного тесту містить число 2N - кількість чисел у послідовності. У кожному з наступних 2N рядків міститься ціле число від 1 до 10⁹ - елементи послідовності (1Ј NЈ 50000).

Приклад вхідного файлу

 

Службовий автобус виконує один рейс за встановленим маршрутом і у випадку наявності вільних місць забирає працівників, що чекають на зупинках та відвозить їх на завод. Автобус також може чекати на зупинці працівників, які ще не прийшли. Відомо час приходу кожного працівника на свою зупинку та час прямування автобуса від кожної зупинки до наступної. Автобус з'являється на першій зупинці в нульовий момент часу. Тривалість посадки працівників в автобус вважається нульовою.

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

Вхідні дані Вхідний текстовий файл BUS.DAT в першому рядку кількість зупинок N і кількість місць в автобусі M. Кожен i-й рядок з наступних N рядків містить ціле число - час руху від зупинки і до зупинки i+1 (N+1-ша зупинка - завод), кількість працівників K, які прийдуть на i-ту зупинку, та час приходу кожного працівника на цю зупинку у порядку приходу (1Ј MЈ 2000, 1Ј N,KЈ 200000).

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

 

На планеті Олімпія дуже популярною є наступна головоломка. На столі послідовно лежать N стопок різнокольорових карток. За один хід можна зняти верхні картки одного кольору з довільної кількості розташованих поряд стопок.

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

Вхідні дані Вхідний текстовий файл CARDS.DAT в першому рядку містить кількість стопок Nі 2. Кожен i-й рядок із наступних N рядків містить кількість карток Kі 1 в і-й стопці і послідовність з K натуральних чисел, що визначають кольори карток в і-й стопці, починаючи з найнижчої (1Ј N*KЈ 10000).

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

2
2 1 2
3 3 1 2

Вихідні дані Єдиний рядок вихідного текстового файла CARDS.SOL має містити мінімальну кількість ходів T.

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

3

 

Другий тур

 

 

1. Послідовність
2. 2
   4
   99
   23
   77
   1
   2
   1
   10101

   Вихідні дані Файл SEQ.SOL повинен містити відповідь на кожен тест в окремому рядку. Відповіддю для тесту є символ 1, якщо вхідну послідовність можна розбити на пари, добутки в яких були б однакові, та 0 в іншому випадку.

   Приклад вихідного файлу

   0

   1

    

3. Автобус.
4. 3 5
   1 2 0 1
   1 1 2
   1 4 0 2 3 4

   Вихідні дані Єдиний рядок вихідного текстового файла BUS.SOL має містити мінімальний час що необхідно для перевезення максимальної кількості працівників.

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

   4

    

5. Головоломка.
6. Електронна пошта

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

Поштова програма, яка встановлена на комп'ютері користувача, дозволяє за одну "операцію" переносити з "списку нових повідомлень" у відповідну папку:

 

 

 

 

• Одне повідомлення з будь-якого місця списку
• Декілька повідомлень, які йдуть у списку підряд, та відносяться до однієї теми

Переносити можна не обов'язково починаючи з початку "списку нових повідомлень". Користувачу потрібно перенести усі нові повідомлення у відповідні їм папки за найменшу кількість операцій.

Приклад. Нехай користувач підписаний на розсилки анекдотів, веселих історій, спортивних новин то прогнозу погоди. Нехай "список нових повідомлень" при деякому входженні в поштову програму мав наступний вигляд: (Анекдоти, Спортивні новини, Прогноз погоди, Спортивні новини, Веселі історії, Веселі історії, Спортивні новини)

	Список папок			Список нових повідомлень
1	Анекдоти		1	Анекдоти
2	Веселі історії		3	Спортивні новини
3	Спортивні новини		4	Прогноз погоди
4	Прогноз погоди		3	Спортивні новини
			2	Веселі історії
			2	Веселі історії
			3	Спортивні новини

Переносити повідомлення у папки він може таким чином: спочатку два повідомлення на тему "Веселі історії". Тоді він отримає наступний список: (Анекдоти, Спортивні новини, Прогноз погоди, Спортивні новини, Спортивні новини). Потім перенести повідомлення про прогноз погоди, після цього "Анекдоти", а потім, одночасно, усі три повідомлення про спортивні новини. На це він вистачить 4 "операції".

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

Вхідні дані Єдиний рядок вхідного файлу EMAIL.DAT містить число N (0<N<200), яке відповідає кількості нових повідомлень та N цілих чисел, які відповідають повідомленням, та є номерами тем, до яких вони належать.

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

7 1 3 4 3 2 2 3

Вихідні дані У першому рядку вихідного файлу EMAIL.SOL повинно знаходитися мінімальне число операцій для даних, наведених у вхідному файлі.

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

4

 

 

1. Віртуляндія

В країні Віртуляндії дуже популярною є така головоломка. Таблиця складається з M+1 рядка. Перші M рядків є зеленими, а останній, M+1-ий, рядок - синій. Кожен рядок складається з N чисел, кожне з яких є цілим з діапазону 0..P-1 включно. Можлива дія при розв'язуванні головоломки - додати зелений рядок до синього по компонентно, при цьому кожне число у синьому рядку, яке більше P-1, зменшується на P. Головоломка вважається розв'язаною, якщо синій рядок складається тільки з нулів.

Задача Написати програму VIRT, яка буде розв'язувати описану головоломку.

Вхідні дані Перший рядок текстового файлу VIRT.DAT містить натуральне число - кількість тестів у файлі. Перший рядок кожного тесту містить числа P,N,M (1Ј N,MЈ 100, 2Ј PЈ 255). Наступні M рядків містять по N чисел - зелені рядки. Наступний рядок з N чисел - синій рядок.

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

2
4 2 2
2 2
2 2
3 3
3 2 4
1 0
2 0
0 0
0 1
2 1

Вихідні дані Текстовий файлу VIRT.SOL має містити відповідь на кожен тест в окремому рядку. Відповідь - це число 0, якщо не вдалося розв'язати головоломку. Якщо головоломку розв'язати вдалося, то відповідь - число 1 і в тому ж рядку N чисел - для кожного зеленого рядка скільки разів його треба додати до синього.

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

0
1 1 0 0 2

Повний архiв олiмпiади (1.2 Мb)

Фотозвiт з навчально-тренувальних зборiв
(м.Київ, травень 2000 р.)