На днях в России проходила школьная олимпиада по программированию.
На решение задач отводилось не три дня, не день, а всего три часа.
Кому как, а мне над осознанием формулировок некоторых задач
пришлось сидеть в задумчивости не менее получаса. Оставим в стороне
педагогический такт авторов олимпиады, травмирующих детскую душу
школьников-программистов такими олимпиадами. И все же - может кто
рискнет и вспомнит детство, представляя себя решившим (или хотя бы
решающем) эти задачи?
Тортики - 1 (10 баллов)
Сегодня у Маши Петровой день рождения. Она пригласила в гости своих друзей
и подруг - всего G человек. У нее есть Kтортиков разного размера,
которые она собирается разрезать так, чтобы все кусочки оказались
(по размеру) одинаковыми. Маша уже придумала, как это можно сделать красиво.
Осталось только выяснить, достанется ли хотя бы один кусочек какого-либо
торта каждому из присутствующих.
Формат входного файла input.txt
Первая строка - два целых числа G и K через пробел
(G - количество приглашенных гостей, 0<=G<=100, K - количество тортиков,
1<=K<=20)
Вторая строка - K целых чисел (1<=j1, j2, :, jK<=10) через пробел.
Каждое из чисел jP обозначает, на какое количество кусочков Маша
собирается разрезать тортик № P
Формат выходного файла output.txt
Первая строка: слово YES, если каждому из присутствующих достанется
хотя бы один кусочек какого-либо торта, и слово NO, если это не так
Пример входного файла
10 2
4 7
Пример выходного файла
YES
Пример входного файла
5 1
4
Пример выходного файла
NO
Фирменное блюдо (25 баллов)
Одно из <фирменных> блюд Маши - рыба в кляре. Готовится оно быстро,
поэтому Маша хочет оставить его приготовление напоследок -
чтобы к приходу гостей рыба была еще достаточно горячей.
Помогите ей посчитать, сколько времени ей потребуется на приготовление
<фирменного> блюда
Формат входного файла input.txt
Первая строка - целые числа N (0<=N<=50), M (1<=M<=10), K (1<=K<=50)
N - количество кусочков рыбы, которое надо обжарить
M - время (в минутах), которое требуется на обжаривание кусочка с одной стороны
K - количество кусочков рыбы, которое одновременно помещается на сковороду
Формат выходного файла output.txt
Первая строка - минимально возможное целое число минут,
которое потребуется на обжаривание с двух сторон всех кусочков рыбы.
Пример входного файла
3 1 2
Пример выходного файла
3
Примечание.
Жюри готово поделиться рецептом
Салатики (35 баллов)
Маша приготовила несколько разных салатов, и задумалась,
как же расставить их на праздничном столе? Ей хочется,
чтобы каждый из присутствующих мог самостоятельно дотянуться до
любого из салатов. При этом на столе не должно быть слишком много
посуды. Посчитайте, сколько минимально салатниц понадобится Маше,
если в каждую салатницу она накладывает только один вид салата
Расстояние до салатницы от гостя - это наиболее короткий отрезок,
которым можно соединить какую-либо точку края стола,
относящуюся к "посадочному месту" данного гостя и
какую-либо точку края салатницы. Все салатницы - квадратные
и имеют одинаковый размер.
Формат входного файла input.txt
Первая строка - шесть целых чисел S, R, K, M, N, D через пробел
S (0 <= S <= 5) - количество различных салатов, приготовленных Машей
R (0 <R <= 100) - максимально допустимое расстояние (в сантиметрах)
от гостя до салата
K (30 <= K <= 100) - длина фрагмента стола, занимаемого одним гостем
M и N (1 <= M, N <= 4) - задают размеры прямоугольного стола:
стол имеет длину M*K и ширину N*K сантиметров
D (10 <= D <= 30) - сторона салатницы (в сантиметрах)
Формат выходного файла output.txt
Первая строка - целое число - минимальное количество салатниц,
которое потребуется Маше
Примечание.
Данные во входном файле всегда допускают существование решения задачи
Пример входного файла
2 100 50 2 2 10
Пример выходного файла
2
Давайте потанцуем (25 баллов)
Салатики, которые приготовила Маша (и не только салатики),
гости съели с удовольствием. А перед чаем был объявлен перерыв на танцы.
Танцы предполагались разные - и быстрые, и медленные.
Медленный танец - парный, а все гости Маши непременно хотели,
чтобы "кавалер" был хотя бы чуть-чуть повыше своей "дамы".
Поэтому договорились, что партнеры должны меняться каждый медленный танец;
приглашать того, с кем уже танцевали хотя бы раз, можно,
только если нет других "подходящих" партнеров.
Сколько нужно медленных танцев, чтобы каждый из гостей хотя бы один раз
потанцевал?
Формат входного файла input.txt
Первая строка - два целых числа M и F (0 <= M, F <= 15)
через пробел - количество мальчиков и девочек соответственно
Вторая строка - M целых чисел через пробел
(100 <= h1, h2, :, hM <=200) - рост каждого из мальчиков в сантиметрах
Третья строка - F целых чисел через пробел
(100<= p1, p2, :, pF <= 200) - рост каждой из девочек в сантиметрах
Формат выходного файла output.txt
Первая строка - целое число - количество медленных танцев,
необходимое, чтобы каждый из гостей хотя бы один раз потанцевал,
или слово NO, если выполнить условие задачи невозможно
Пример входного файла
4 5
172 164 157 179
158 139 142 178 173
Пример выходного файла
2
Пример входного файла
3 2
164 157 169
158 169
Пример выходного файла
NO
Боулинг (20 баллов)
В квартире Маши длинный коридор, и пока остальные гости танцевали,
несколько ребят (Pчеловек) решили поиграть в <мини>-боулинг
(с сильно облегченными шарами, кеглями и правилами).
Для записи результатов они расчертили листок наP линий
(по количеству играющих) и Tстолбцов (по количеству туров).
Каждый играющий, бросив шар, подходил к листочку и записывал,
сколько кеглей (из 10) ему удалось сбить, в соответствующую клеточку таблицы.
После этого все кегли ставились на место, и шар бросал следующий игрок.
Однако по прошествии N туров к ним решили присоединиться еще несколько ребят
(Q человек). Они тоже стали бросать шары и записывать свои результаты
в очередные свободные клеточки имеющейся таблицы.
Когда последняя клеточка таблицы была заполнена, ребята остановили игру,
и захотели посчитать, сколько кеглей кто из них сбил.
Помогите им это выяснить.
Формат входного файла input.txt
Первая строка - четыре целых числа P (1 <= P <= 10),
T (1 <= T <= 100), Q (0 <= Q <= 10), N (1 <= N <T).
P - количество играющих, начиная с 1-го тура
T - количество запланированных игроками туров
Q - количество присоединившихся игроков по завершении тура № N
Первый игрок из присоединившихся бросал шар сразу же за игроком № P
(т.е. начинал тур № N+1), следующий - за ним, и так далее.
Когда все <новые> игроки бросили по шару и записали свои результаты так,
как это указано в условии задачи, наступила очередь первого игрока из тех,
кто начинал игру.
N - количество туров, которые P ребят успели сыграть до того, как к ним
присоединились еще Q человек
Следующие P строк содержат по T целых чисел (количества сбитых кеглей; каждое число не превосходит 10) в каждой соответственно условию задачи
Формат выходного файла output.txt
Первая строка - P+Q целых чисел через пробел, каждое число - количество кеглей, сбитых игроком с соответствующим номером
Пример входного файла
2 10 3 4
3 8 10 4 7 3 9 1 8 2
4 5 9 9 7 2 1 0 10 3
Пример выходного файла
35 46 10 11 3
Примечание.
Пояснение к примеру (в скобках указан номер игрока):
Тур 1 Тур 2 Тур 3 Тур 4 Тур 5 Тур 6 Тур 7 Тур 8 Тур 9 Тур 10
3 (1) 8 (1) 10 (1) 4 (1) 7 (3) 3 (5) 9 (2) 1 (4) 8 (1) 2 (3)
4 (2) 5 (2) 9 (2) 9 (2) 7 (4) 2 (1) 1 (3) 0 (5) 10 (2) 3 (4)
Подсчет очков:
1-ый игрок: 3 + 8 + 10 + 4 + 2 + 8 = 35
2-ой игрок: 4 + 5 + 9 + 9 + 9 + 10 = 46
3-ий игрок: 7 + 1 + 2 = 10
4-ый игрок: 7 + 1 + 3 = 11
5-ый игрок: 3 + 0 = 3
Чайная церемония (10 баллов)
Задача F. Чайная церемония - 1 (10 баллов)
Пока гости танцевали и играли, Маша и несколько ее подружек
готовили чай и кофе, стараясь выполнить пожелания всех гостей:
кто-то захотел черный чай с лимоном, кто-то - зеленый чай,
кто-то - кофе с парой ложечек сахара. Они принесли приготовленные
напитки и расставили их на столе. Но оказалось, что немного перепутали,
какой напиток перед кем именно следовало поставить.
Найдите минимальное количество перестановок чашек,
за которое можно поставить перед каждым из присутствующих тот напиток,
который он просил.
Чашки переставляют очень просто: Маша (или кто-то из ее помощниц)
должна забрать <неправильно поставленную> чашку и отнести ее на
<правильное> место. Таким образом,
перестановка - это перемещение одной чашки
Формат входного файла input.txt
Первая строка - целое число G (1 <= G <= 20) - количество присутствующих
Вторая строка - G целых чисел (1 <= c1, c2, :, cG <= 20)через пробел.
Каждое из чисел cK означает номер напитка, поставленного перед человеком № K.
Напиток поставлен правильно, если cK = K (т.е. считается, что человек № K
заказывал напиток № K).
Формат выходного файла output.txt
Первая строка - целое число - минимально необходимое
количество перестановок чашек.
Пример входного файла
6
4 2 3 5 1 6
Пример выходного файла
3
Чайная церемония - 2 (30 баллов)
Напомним, что произошло в предыдущей задаче
Маша и несколько ее подружек приготовили чай и кофе, стараясь выполнить
пожелания всех гостей: кто-то захотел черный чай с лимоном, кто-то - зеленый
чай, кто-то - кофе с парой ложечек сахара. Когда они расставили их на столе,
оказалось, что немного перепутали, какой напиток перед кем именно следовало
поставить.
Маша хотела сама переставить <неправильно> расставленные чашки.
Однако гости решили, что проблема с неправильно расставленными чашками
должна решаться иначе - чашки горячие, наполнены почти до краев, и
переносить их сложно и долго: носить придется по одной чашке, медленно и
осторожно. Будет проще, если чашки передавать от соседа к соседу.
Передача осуществляется следующим образом. Человек, перед которым стоит
<неправильно> поставленная чашка, берет ее в руки и ставит ее перед
одним из своих соседей (слева или справа). Такое перемещение чашки
занимает V секунд. Считая, что перед одним человеком не может одновременно
находиться более двух чашек, учитывая и ту, которую он держит в руках,
найдите минимальное время, за которое все чашки можно переместить
на <правильные> места.
Заметим, что любой человек может начать переносить чашку в любой момент,
когда он не занят переносом другой. В частности, это означает, что
несколько присутствующих одновременно могут переносить чашки.
Формат входного файла input.txt
Первая строка - целые числа G (1 <= G <= 20) - количество присутствующих
и V (1 <= V <= 10) - время (в секундах), которое требуется,
чтобы передать чашку соседу.
Вторая строка - G целых чисел (1 <= c1, c2, :, cG <= 20)через пробел.
Каждое из чисел cK означает номер напитка, поставленного перед человеком № K.
Напиток поставлен правильно, если cK = K (т.е. считается,
что человек № K заказывал напиток № K).
Примечание.
Два человека считаются соседями, если их номера отличаются на 1.
Также соседними считаются номера 1 и G.
Формат выходного файла output.txt
Первая строка - целое число - минимально необходимое время,
затраченное на перестановку чашек.
Пример входного файла
5 10
2 3 4 1 5
Пример выходного файла
20
Тортики-2 (15 баллов)
Когда гости увидели разрезанные торты, им стало понятно, что не все смогут
попробовать каждый торт. Поэтому они попросили Машу разрезать
имеющиеся кусочки на еще более мелкие - так, чтобы каждый из
присутствующих смог попробовать каждый торт.
Найдите, на какое минимальное количество еще более мелких кусочков надо
разрезать каждый из уже имеющихся кусочков торта.
Примечание.
<Лишние> кусочки могут оставаться - главное, чтобы всем досталось
хотя бы по одному
Формат входного файла input.txt
Первая строка - два целых числа G и K через пробел
(G - количество приглашенных гостей, 0<=G<=100,
K - количество тортиков, 0<=K<=20)
Вторая строка - K целых чисел (1<=j1, j2, :, jK<=10) через пробел.
Каждое из чисел jP обозначает, на какое количество кусочков тортик
№ P уже разрезан
Формат выходного файла output.txt
Первая строка - целое число - минимально возможное количество более
мелких кусочков, на которые надо разрезать каждый из уже имеющихся кусочков торта, чтобы все присутствующие смогли попробовать каждый торт.
Пример входного файла
10 2
4 7
Пример выходного файла
3
Подарки (20 баллов)
Проводив гостей, Маша стала раскладывать полученные подарки, и старалась
вспомнить, кто и что подарил. Однако вспомнить все и точно ей не удавалось:
гостей и, соответственно, подарков было много
Тогда Маша составила два списка. В одном списке напротив каждого подарка
она написала, кто, по ее мнению, мог бы его подарить.
В другом списке напротив каждого подарка она написала, кто, по ее мнению,
точно не мог бы его подарить.
Помогите Маше узнать, кто и какой подарок ей подарил
Примечание.
Каждый гость дарил только один подарок
Формат входного файла input.txt
Первая строка - целое число G - количество гостей и, соответственно,
подарков, 1 <= G <= 20
Следующие G строк содержат информацию из первого списка Маши
Строка № K (2 <= K <= G+1) соответствует описанию подарка № (K-1).
В ней через пробел записаны не более G чисел - номера гостей,
которые могли подарить этот подарок. Если Маша затрудняется предположить,
кто из гостей мог подарить этот подарок, строка остается пустой
Дальнейшие G строк содержат информацию из второго списка Маши
Строка № L (G+2 <= L <= 2*G+1) соответствует описанию подарка № (L-(G+1)).
В ней через пробел записаны не более G чисел - номера гостей,
которые точно не могли подарить этот подарок. Если, по мнению Маши,
любой из гостей мог подарить такой подарок, строка остается пустой
Формат выходного файла output.txt
Первая строка - слово YES, если имеющейся информации достаточно,
чтобы однозначно установить, кто и какой подарок подарил Маше, и слово NO,
если информации недостаточно
Если информации достаточно, в следующих G строках должны содержаться
сведения о дарителях. Строка № M (2 <= M <= G+1) соответствует подарку № М,
а в ней записывается целое число N (1 <= N <= G) - номер гостя,
который подарил этот подарок.
Пример входного файла
3
2 3
1
2 3
3
Пример выходного файла
YES
3
1
2
После праздника (30 баллов)
Гости разошлись, подарки разложены: Надо еще убрать со стола.
Маша сложила всю посуду в несколько стопок и собралась отнести их на кухню.
Однако при переноске посуды таким образом то, что лежит сверху, может
и разбиться.
Ваша задача - во-первых, определить, сколько посуды Маша точно донесет
до кухни, если понесет уже сложенные стопки, и, во-вторых,
сколько (минимально) нужно сформировать дополнительных стопок,
чтобы донести до кухни всю посуду в целости и сохранности.
Стопку можно донести до кухни целой, если высота, на которой находится
центр тяжести самого верхнего предмета, не превышает некоторой
заранее заданной <безопасной> высоты. Ради простоты будем считать,
что центр тяжести любого предмета расположен в плоскости,
разделяющей этот предмет по высоте точно пополам.
Формирование дополнительных стопок происходит так:
с существующих стопок снимаются верхние предметы до тех пор,
пока высота стопки не станет <безопасной>.
Снятые предметы складываются в новые стопки наиболее оптимальным образом.
Примечание.
Считайте, что, когда предметы складывают в стопки, то уменьшения
высоты за счет вложения предметов друг в друга не происходит,
и высота стопки в точности равна сумме высот предметов, ее составляющих.
Формат входного файла input.txt
Первая строка - три целых числа P, S и H через пробел.
P - количество видов посуды, 0<=P<=10;
S - количество уже сложенных стопок посуды 0 <= S <= 10;
H - <безопасная> высота в сантиметрах, 0<=H<=100;
Следующие Pстрок записаны в формате: символ
(прописная латинская буква, обозначающая предмет),
за которым через пробел указано целое число - высота предмета в сантиметрах.
Следующие за ними S строк описывают стопки посуды
(одна строка - описание одной стопки). Каждая строка содержит
прописные латинские буквы через пробел,
соответствующие предметам, сложенным в стопку.
Первая буква отвечает предмету, который находится в самом низу стопки.
Всего букв в каждой строке не более 100.
Формат выходного файла output.txt
Первая строка - два целых числа через пробел.
Первое число - количество предметов, которые будут принесены на кухню
в целости при существующей раскладке посуды по стопкам;
второе число - минимально возможное количество дополнительных стопок,
которые нужно сформировать, чтобы донести всю посуду до кухни целой
Пример входного файла
2 1 50
C 12
S 2
S S C S C C S C
Пример выходного файла
8 0
Пример входного файла
2 1 50
C 12
S 2
S S C S C C C S
Пример выходного файла
7 1
