1. Послідовність

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

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

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

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

2
4
99
23
77
1
2
1
10101


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

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

0

1

2. Автобус.

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

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

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

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

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


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

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

4

3. Головоломка.

На планеті Олімпія дуже популярною є наступна головоломка. На столі послідовно лежать 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. Електронна пошта

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

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

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

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

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

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

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