2 тур - з 27.10 по 02.11.2014
точка входу для відправлення розв'язків http://176.31.28.231/cgi-bin/new-client?contest_id=16
скачати умови задач першого туру (*.docx)
Задача 1. Ремонт кораблів (20 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
На судноремонтний завод для докового ремонту одночасно прийшло N кораблів. В док на ремонт може зайти тільки одне судно. Необхідний час стоянки в доці для кожного судна різний. Після ремонту судно одразу йде в рейс.
Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний
Вхідні дані.
У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1≤N≤10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).
Вихідні дані.
Вихідний файл повинен містити послідовність чисел – номери кораблів, у тому порядку, в якому вони заходять у док.
Приклад.
input.txt
|
output.txt
|
3
3 6
1 12
2 4
|
2 3 1
|
Задача 2. Погоня(100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 2с.
Дано N островів (пронумерованих від 1 до N) і N мостів, які сполучних острова. Відомо, що з будь-якого острова можна перейти на будь-який інший і що між двома островами може бути не більше одного моста. Також відомо, що на острові з номером X знаходиться кролик, а на острові Y знаходиться Аліса, яка хоче зловити кролика. Аліса і кролик постійно знають місце розташування один одного. Вони ходять по черзі (хід - переміщення з одного острова на другий, який з'єднаний мостом з першим), починаючи з кролика. Аліса зловить кролика, якщо вони разом знаходяться на одному острові. Вам необхідно дізнатися, чи зможе вона зловити кролика.
Формат вхідного файлу.
В першому рядку записано число K (1≤K≤10) - кількість тестів. Далі слідує K блоків. Формат блоку: в першому рядку числа N, X, Y (3≤N≤1000). У наступних N рядках по два числа - номери двох островів, з'єднаних одним мостом.
Формат вихідного файлу.
У вихідний файл вивести K рядків, в кожній з яких потрібно вивести відповідь на відповідний тест: 0, якщо Аліса не зловить кролика, або 1, якщо піймає.
Приклад.
input.txt
|
output.txt
|
1
4 1 3
1 2
2 3
3 4
4 2
|
1
|
|