Задачи олимпиады "Полуфинал X Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"

Задача A. Перестановка

Если Вы читали Гарри Поттера, то знаете, что повелитель зла, Лорд Волдеморт создал свое имя путем перестановки букв в своем настоящем имени. Так из имени «Tom Marvolo Riddle» он получил «I am Lord Voldemort».

Напишите программу, которая проверяет, можно ли получить из одного имени другое путем перестановки его букв. При этом регистром букв нужно пренебречь.

Входные данные

В первой строке входного файла INPUT.TXT записаны два слова, разделенные единственным в строке пробелом. Слова содержат только символы английского алфавита. Длина слов больше 0 и не превышает 50 символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите «Yes», если возможно получить из одного имени другое, и «No» в противном случае.

Примеры

Задача B. Лентяй

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен.

Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Входные данные

В первой строке входного файла INPUT.TXT содержится натуральное число N – количество предметов, которые нужно сдать Валере (N ≤ 100). Далее идет N строк, каждая из которых состоит из двух чисел A и B, задающих отрезок работы очередного преподавателя (1 ≤ A ≤ B ≤ 31).

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если возможно встретить всех преподавателей за один день, или «NO», если это сделать невозможно.

Примеры

Задача C. Мифические шахматы

Ваш друг Вася занимается разработкой компьютерной игры «Мифические шахматы». Он не укладывается в установленные сроки сдачи проекта.

Вася обратился к друзьям за помощью. Ему необходим модуль, вычисляющий оптимальные пути перемещения фигур из одной клетки в другую. Так как друзей у Васи много, то каждому досталась маленькая подзадача. Вам требуется написать программу, определяющую минимальное количество ходов, необходимое кентавру, чтобы добраться из одной клетки в другую.

В мифические шахматы играют на шахматной доске размером 9х9, угловые клетки которой окрашены в черный цвет. Кентавр – фигура мифических шахмат, объединяющая в себе свойства коня и слона. Когда кентавр стоит на белой клетке, он может ходить только как конь, а когда на черной – только как слон. На рисунках приведены варианты ходов для двух кентавров (буквой «K» отмечено местоположение кентавра, а звездочками – клетки, куда кентавр может сделать ход).

Входные данные

В первой строке входного файла INPUT.TXT содержатся координаты (большая английская буква и цифра) двух клеток доски для мифических шахмат, разделенные пробелом.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное число ходов, необходимое кентавру, чтобы добраться из первой клетки во вторую. Если добраться невозможно, то следует вывести число «-1» (без кавычек).

Примеры

Задача D. Сон

Любознательный школьник Петя очень любит программировать. Однажды он настолько увлекся этим делом, что уснул прямо за компьютером! Пете приснилось, что он попал в альтернативную реальность. Альтернативная реальность представляет собой прямоугольный лабиринт, который можно изобразить в виде таблицы размером R × C клеток. Чтобы не опоздать школу, Пете нужно найти выход из лабиринта. Начальная позиция Пети обозначается символом ‘S’, выход из альтернативной реальности – ‘E’. За один ход Петя перемещается в одну из четырех смежных клеток (влево, вправо, вниз, вверх). Если клетка занята стеной (символ ‘X’), то Петя пройти в нее не может. В некоторых клетках расположены двери с замками одного из четырех цветов (‘R’, ‘G’, ‘B’, ‘Y’). Для прохода в эту клетку, необходимо обладать ключом определенного цвета. Так как ключи многоразовые, то одним ключом можно открыть сколь угодно много соответствующих ему замков.

Властелин альтернативной реальности предлагает Пете купить ключи, чтобы пройти к выходу. У нашего героя совсем немного денег с собой, поэтому ему хочется потратить как можно меньше денег и при этом пройти к выходу. Помогите ему определить минимальную сумму денег, которую нужно потратить на ключи.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральные числа R и C (R,C ≤ 50). Вторая строка теста содержит 4 целых числа P_i, стоимости покупки ключей ‘R’, ‘G’, ‘B’ и ‘Y’ соответственно (P_i ≤ 100). Далее следуют R строк, в каждой из которых C символов, описывающих лабиринт. Каждый лабиринт содержит только один символ ‘S’ и один символ ‘E’.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальную сумму денег, необходимую для покупки набора ключей, позволяющего пройти к выходу. Если пути к выходу из альтернативной реальности не существует, и Петя обречен проспать уроки, выведите «Sleep».

Примеры

Задача E. Ремонт

Ваш любимый дядя – директор фирмы, которая делает евроремонты в офисах. В связи с финансово-экономическим кризисом, дядюшка решил оптимизировать свое предприятие.

Давно ходят слухи, что бригадир в дядюшкиной фирме покупает лишнее количество стройматериалов, а остатки использует для отделки своей новой дачи. Ваш дядя заинтересовался, сколько в действительности банок краски необходимо для покраски стен в офисе длиной L метров, шириной – W и высотой – H, если одной банки хватает на 16м², а размерами дверей и окон можно пренебречь? Заказов много, поэтому дядя попросил написать программу, которая будет все это считать.

Входные данные

Первая строка входного файла INPUT.TXT содержит три натуральных числа L, W, H через пробел – длину, ширину и высоту офиса в метрах соответственно. Каждое из них не превышает 1000.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество банок краски, необходимых для покраски стен в офисе.

Примеры

Задача F. Игра в дурака

Как Вам уже стало известно, Петя очень любит программировать. Недавно он решил реализовать популярную карточную игру «Дурак». Но у Пети пока маловато опыта, ему срочно нужна Ваша помощь.

Как известно, в «Дурака» играют колодой из 36 карт. В Петиной программе каждая карта представляется в виде строки из двух символов, где первый символ означает ранг (‘6’, ‘7’, ‘8’, ‘9’, ‘T’, ‘J’, ‘Q’, ‘K’, ‘A’) карты, а второй символ означает масть (‘S’, ‘C’, ‘D’, ‘H’). Ранги перечислены в порядке возрастания старшинства.

Пете необходимо решить следующую задачу: сможет ли игрок, обладая набором из N карт, отбить M карт, которыми под него сделан ход? Для того чтобы отбиться, игроку нужно покрыть каждую из карт, которыми под него сделан ход, картой из своей колоды. Карту можно покрыть либо старшей картой той же масти, либо картой козырной масти. Если кроющаяся карта сама является козырной, то её можно покрыть только старшим козырем. Одной картой можно покрыть только одну карту.

Входные данные

В первой строке входного файла INPUT.TXT находятся два натуральных числа N и M (N ≤ 35, M ≤ 4, M ≤ N), а также символ R, означающий козырную масть. Во второй строке перечислены N карт, находящихся на руках у игрока. В третьей строке перечислены M карт, которые необходимо отбить. Все карты отделены друг от друга одним пробелом.

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES» в случае, если отбиться можно, либо «NO» , если нельзя.

Примеры

Задача G. Грибной дождь

На лесной опушке растет дружная семейка грибов. Местоположение каждого гриба задается координатами X, Y, а шляпка гриба имеет радиус R. Когда идет дождь, радиус шляпки каждого гриба непрерывно и равномерно увеличивается cо скоростью 1 сантиметр в минуту. Когда дождь заканчивается (а он идет не более Т минут), шляпки прекращают расти. Если во время дождя шляпки двух грибов соприкоснулись, то они немедленно перестают расти, чтобы не навредить друг другу. Грибы очень дружные, поэтому если перестают расти два гриба, то и все остальные тоже не растут.

Требуется посчитать, на сколько сантиметров увеличился радиус шляпки каждого гриба после завершения дождя.

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа: количество грибов K (K ≤ 10) и длительность дождя T (T ≤ 100). Следующие К строк содержат описание грибов: целые координаты X и Y (0 ≤ X, Y ≤ 100) и радиус шляпки R (1 ≤ R ≤ 10). Координаты и радиус даны в сантиметрах.

Выходные данные

В выходной файл OUTPUT.TXT выведите величину в сантиметрах, на которую увеличится радиус всех грибов. Результат следует вывести с точностью, не меньшей, чем два знака после запятой.

Примеры

Задача H. Мёд

Все любят сладости и, в частности, мед. Винни-Пух тоже его любит. Каждый день он шел лакомиться медом, а по дороге домой заходил в гости к Кролику. Но приближалась зима, и Винни-Пух начал задумываться о запасах. Он решил в течении N дней не лакомиться медом, а собирать полный горшочек объемом V горстей и перекладывать его в бочку. В первый день своего собирательства он так и сделал. Терпения хватило на один день. А на следующий день он не смог устоять и по дороге домой съел K горстей меда из горшочка. В каждый следующий день из полного горшочка он съедал на K горстей больше.

Необходимо определить объем меда, собранного Винни-Пухом на зиму.

Входные данные

Входной файл INPUT.TXT содержит три натуральных числа N (N ≤ 300), V (V ≤ 10⁷) и K (K ≤ 1000). K – объем, на который Винни-Пух с каждым днем съедал больше меда.

Выходные данные

В выходной файл OUTPUT.TXT выведите два значения через пробел. Сначала идет строка «NO», если случилось, что Винни-Пух пришел к Кролику с пустым горшочком и «YES» в противном случае. Второе значение – объем меда, заготовленного Винни-Пухом на зиму.

Примеры