|
XIII Всеукраинская олимпиада по информатике (г.Киев, март 2000г.) Первый тур 1. Последовательность Дана последовательность, состоящая из 2N натуральных чисел. Известно, что все числа этой последовательности можно разбить на пары таким образом, что сумма чисел во всех парах будет одинаковой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары 1+99=77+23.Задание Напишите программу SEQ, которая по такой последовательности определяет, можно ли эту последовательность разбить на пары таким образом, чтобы произведение чисел во всех парах было одинаковым. Входные данные Файл SEQ.DAT содержит данные нескольких тестов. Первая строка содержит натуральное число - количество тестов в файле. Первая строка каждого теста содержит число 2N - количество чисел в последовательности. В каждой из последующих 2N строчек содержится целое число от 1 до 109 - элементы последовательности (1< N< 500000). Пример входного файла 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. Электронная почта Пользователь сети Интернет подписан на несколько разных списков рассылки, которые высылают ему по электронной почте сообщения на определенные темы. Для удобства пользователь создал себе набор папок, каждая из которых соответствует одной из тем. Перед тем, как читать сообщения он копирует их в соответствующую папку. Почтовая программа, установленная на компьютере пользователя, позволяет за одну "операцию" переносить из "списка новых сообщений" в соответствующую папку:
|
Полный архив олимпиады (1.2 Мb)
Фотоотчет о учебно-отборочных сборах
(Киев, май 2000 г.)