Годинник | |
|
2000 год
|
| |
|
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 |
Анекдоты |
|
1 |
Анекдоты |
|
2 |
Веселые истории |
|
3 |
Спортивные новости |
|
3 |
Спортивные новости |
|
4 |
Прогноз погоды |
|
4 |
Прогноз погоды |
|
3 |
Спортивные новости |
|
|
|
|
2 |
Веселые истории |
|
|
|
|
2 |
Веселые истории |
|
|
|
|
3 |
Спортивные новости |
Переносить сообщения в папки он может следующим образом: сначала два сообщения на тему "Веселые истории". Тогда он получит следующий список: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Спортивные новости). Потом перенести сообщения о прогнозе погоды, после этого "Анекдоты", а потом, одновременно, все три сообщения о спортивных новостях. На это он потратит 4 "операции".
Задание Напишите программу EMAIL которая будет вычислять минимальное количество "операций", с помощью которых можно перенести все новые сообщения в папки. Для удобства каждой теме присваивается номер.
Входные данные Единственная строчка входного файла EMAIL.DAT содержит число N (0
Пример входных данных
7 1 3 4 3 2 2 3
Выходные данные
В первой строке выходного файла EMAIL.SOL должно находиться
минимальное число операций для данных, приведенных во входном файле.
Пример выходных данных
4
2. Виртуляндия
В стране Виртуляндии очень популярна следующая головоломка. Таблица состоит из
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
|
Полный архив олимпиады (1.2 Мb)
Фотоотчет о учебно-отборочных сборах
(Киев, май 2000 г.)
|
|
|
© Всеукраинский виртуальный центр олимпиад школьников
"ОЛІМП"
|
| |
