Областная олимпиада по информатике 2001 года
Задача 1. «С Новым годом!» (30 баллов)
Человек рассеянный решил поздравить своих друзей с праздником и купил для этого конверты и открытки. При этом оказалось, что конверты и открытки были разного размера. Какое максимальное количество открыток в конвертах может быть отправлено, если в каждый конверт класть только одну открытку, не складывая её?
Ввод. В первой строке файла дано два числа К1 —количество типов конвертов и К2 — количество типов открыток (через пробел). Каждая следующая строка входного файла к этой задаче содержит три числа: N — показывающее количество конвертов или открыток каждого типа размера U на V, значения которых приводится в этой же строке. К1 строк описывают конверты. К2 строк — открытки.
Вывод. Результатом работы программы является информация об отправленных открытках (количество и размер каждого типа) и их общее максимальное количество.
Пример файла inpl .txt
2 2
9 110 60
8 100 75
13 110 50
5 90 75
Пример файла out1 .txt
9 110 50
5 90 75
14
Задача 2. «Генеалогическое дерево» (40 баллов)
Система родственных отношений у марсиан достаточно запугана. Собственно говоря, марсиане почкуются когда им угодно и как им угодно, собираясь для этого разными группами, так что у марсианина может быть и один родитель, и несколько десятков, а, сотней детей сложно кого-нибудь удивить. Марсиане привыкли к этому, и такой жизненный уклад кажется им естественным.
В Планетарном Совете запутанная генеалогическая система создает серьезные неудобства. Не всегда марсианин знает всех своих родителей, не говоря про бабушек и дедушек! Но когда по ошибке сначала высказывается праправнук, а потом только прапрадед - это настоящий скандал. Ваша цель — написать программу, проверяющую корректность данных (не является ли кто-то своим предком) и определяющую последовательность выступлений, который гарантировал бы, что каждый член Совета получает возможность высказаться раньше любого из своих потомков.
Ввод. В первой строке входного файла находится число N. 1<=N<=100 — количество членов Марсианского Планетарного Совета. По многовековой традиции все члены Совета нумеруются натуральными числами от 1 до N. Далее во входном файле следуют ровно N строк, причем i-ая строка содержит список детей члена Совета с порядковым номером i. Список детей представляет собой последовательность порядковых номеров детей, разделенных пробелами и следующих в произвольном порядке. Список детей может быть пустым. Список детей (даже пустой), оканчивается нулем.
Вывод. Выходной файл должен содержать одну единственную строку с последовательностью номеров выступающих. lie л и несколько последовательностей удовлетворяют условиям задачи, то можно вывести любую из них. Если данные некорректны (в примере 2 каждый является своим предком), то вывести соответствующее сообщение.
Пример файла inptl .txt
5
0
4 5 10
1 0
5 3 0
3 0
Файл outp1 .txt: 2453 1
Пример файла Inpt2.txt
3
20
30
10
Файл outp2.txt: данные некорректны
Задача 3. «Прыжки в высоту» (30 баллов)
Соревнования по прыжкам в высоту проводились по следующим правилам. Если спортсмен сбивал планку, то он выбывал из дальнейшей борьбы, в противном случае становился в конец очереди. Известно, что спортсменов было К и они прыгали в порядке своих номеров от 1 до К. По потом спортсмены начали ошибаться, при чем между двумя последовательными неудачами каждый раз было ровно М удачных прыжков. Последним сбил планку спортсмен с номером Т. Вывести номера прыгунов в том порядке, в котором они сбивали планку.
Пример. Если К=10, М=3, Т=8, то должны быть напечатаны числа: 7, 1,5, 10, 6. 3, 2, 4. 9, 8.
Задача 4. «Паспорт» (15 баллов)
В некотором государстве ввели компьютерный паспорт гражданина. При рождении ребенка туда заносили информацию о его половой принадлежности, то есть
|
1 |
1 |
1 |
1 |
1 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
|
1 |
|
|
|
1 |
|
-1 |
|
|
|
-1 |
|
1 |
|
|
|
1 |
|
-1 |
|
|
|
-1 |
|
1 |
|
|
|
1 |
|
-1 |
|
|
|
-1 |
|
1 |
1 |
1 |
1 |
1 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
для мальчиков для девочек
Гражданину, получившему образование, в паспорт заносили следующую информацию:
|
|
|
2 |
|
|
|
|
|
2 |
|
|
|
2 |
2 |
2 |
2 |
2 |
|
|
|
2 |
|
|
|
|
|
2 |
|
|
Гражданину, вступившему в брак, в паспорт заносили:
|
3 |
|
|
|
3 |
|
|
3 |
|
3 |
|
|
|
|
3 |
|
|
|
|
3 |
|
3 |
|
|
3 |
|
|
|
3 |
При получении водительских прав гражданину записывали следующее:
|
|
|
4 |
|
|
|
|
4 |
|
4 |
|
|
4 |
|
|
|
4 |
|
|
4 |
|
4 |
|
|
4 |
4 |
4 |
4 |
4 |
Ввод. По записям в паспорте укажите пол гражданина и последовательность произошедших в его жизни событий.
|
3 |
-1 |
2 |
-1 |
3 |
|
-1 |
3 |
2 |
3 |
-1 |
|
2 |
2 |
3 |
2 |
2 |
|
-1 |
3 |
2 |
3 |
-1 |
|
3 |
4 |
2 |
4 |
3 |
Вывод. Паспорт выдан женщине, имеющей водительские права, образование и состоящей в браке.
Test-the-Best.by соревнования по спортивному программированию
Сайт открыт 1 мая 2006г.
