Сайт відділу інформаційних технологій та дистанційної роботи ВІППО

2 тур - з 27.10 по 02.11.2014

точка входу для відправлення розв'язків http://176.31.28.231/cgi-bin/new-client?contest_id=16

Задача 1. Ремонт кораблів (20 балів)

Ім’я вхідного файлу: input.txt       

Ім’я вхідного файлу: output.txt

Ліміт часу: 1с.

На судноремонтний завод для докового ремонту одночасно прийшло N кораблів. В док на ремонт може зайти тільки одне судно. Необхідний час стоянки в доці для кожного судна різний. Після ремонту судно одразу йде в рейс.

Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний

Вхідні дані.

У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1≤N≤10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).

Вихідні дані.

Вихідний файл повинен містити послідовність чисел – номери кораблів, у тому порядку, в якому вони заходять у док.

Приклад.

Задача 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, якщо піймає.

Приклад.