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

Задача A. Али-Баба

Али-Баба стоял у входа в пещеру. «Сим-Сим, открой дверь!» – сказал он. И дверь распахнулась. Али-Баба зашел внутрь и обомлел – пещера была усыпана сокровищами. Золото, драгоценности, дорогое оружие и посуда, пещера буквально сверкала!

Но Али-Баба радовался недолго. Поразмыслив, он понял, что может унести с собой не более M предметов, в то время как в пещере находится целых N предметов. Али-Баба внимательно рассмотрел каждый предмет и оценил его стоимость. К своему удивлению Али-Баба обнаружил в пещере также бесполезные, и даже вредные вещи, ценность которых сомнительна. Естественно, что Али-Баба хочет взять с собой такие предметы, чтобы их суммарная ценность была максимальна. Помогите ему найти эту сумму.

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

В первой строке входного файла INPUT.TXT находятся два числа, разделенные пробелом: N – количество предметов в пещере (1 ≤ N ≤ 1000), M – максимальное количество предметов, которые Али-Баба может унести с собой (0 ≤ M ≤ N). Во второй строке располагаются N целых чисел, разделенных пробелами. Каждое такое число C_i означает стоимость i-го сокровища (1 ≤ i ≤ N, -1000 ≤ C_i ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите единственное целое число – максимальную суммарную стоимость сокровищ, которые Али-Баба может унести из пещеры.

Примеры

Задача B. Транспорт

Все автовладельцы рано или поздно встречаются с инспекторами ГИБДД. Ваша задача состоит в том, чтобы рассчитать минимальное время прохождения автомобилем прямого участка дороги, на котором стоят инспекторы. Известно, что на данном участке инспекторы останавливают все проезжающие мимо автомобили. Примем следующие допущения: автомобили являются материальными точками, которые могут мгновенно останавливаться или набирать максимальную скорость. Автомобиль начинает свой путь в точке 0 и заканчивает его в точке L.

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

Первая строка входного файла INPUT.TXT содержит три числа: N – количество инспекторов (0 ≤ N ≤ 30), V – максимальная скорость автомобиля (км/ч) и L – длина участка дороги (км) (1 ≤ V, L ≤ 200). Вторая строка содержит N пар чисел x_i – расстояние от точки 0 до инспектора (0 ≤ x_i ≤ L) и t_i – время (мин), на которое он останавливает машину (1 ≤ t_i ≤ 10). Все инспектора стоят в разных точках. Все числа во входных данных целые.

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

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

Примеры

Задача C. Ковбои

Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда считался опасным делом. Ковбой Джон, готовясь к очередному перегону, изучал план местности. Так как местность гористая, то добраться из одного поселения в другое можно только по дорогам, возможно через другие поселения. Главной опасностью на пути были бандиты, проживающие в разных населенных пунктах, и организующие группировки для нападения на ковбоев. Чтобы их разобщить, Джон разработал гениальный план полной изоляции поселений друг от друга.

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

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

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

В первой строке входного файла INPUT.TXT находятся два целых неотрицательных числа N (0 < N < 1000) – количество поселений и M (0 ≤ M ≤ 100 000) – количество дорог, их соединяющих. Далее следует M строк, содержащих описание дорог. В i-й строке находятся два натуральных числа V и U (1 ≤ V, U ≤ N) – номера поселений, которые соединяет i-я дорога. Между двумя различными поселениями существует не более одной дороги, но может существовать несколько маршрутов. Нет дорог, которые образуют петлю, исходящую из поселения и ведущую в него же, не заходя в другие поселения. Не гарантируется, что существует маршрут между любой парой поселений. Маршрутом называется такая последовательность поселений s₁-s₂- … -s_n, что любые два последовательных поселения s_i и s_i+1 соединены дорогой.

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

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

Примеры

Задача D. Взвешивание

Имеется N монет, не различимых на первый взгляд. Однако, одна из них фальшивая. Фальшивая монета чуть тяжелее, чем настоящая, но во всем остальном полностью идентична настоящим. Кроме того, есть чашечные весы без гирь и шкалы (по таким весам, можно определить, какая чаша тяжелее или легче, но нельзя сказать на сколько). Найти минимальное количество взвешиваний, за которое можно гарантированно определить фальшивку.

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

Входной файл INPUT.TXT содержит одно натуральное число N – количество монет (2 ≤ N ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите минимальное количество взвешиваний.

Примеры

Задача E. Игра с ладьей

На бесконечной вправо и вверх шахматной доске находится ладья. Два игрока передвигают ее по очереди. За один ход разрешено сдвинуть ладью вниз или влево на произвольное (ненулевое) количество клеток так, чтобы ладья не покинула доску. Цель игры – переместить ладью в левый нижний угол, то есть клетку с координатами (1,1). Известно, что оба игрока придерживаются оптимальной стратегии. Игрок №1 ходит первым, при этом он обязан совершить хотя бы один ход. Если первый ход сделать нельзя, то определить победителя также невозможно. Требуется написать программу, которая найдет номер победившего игрока, либо определит, что этого сделать нельзя.

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

Входной файл INPUT.TXT содержит два натуральных числа, разделенных пробелами: X и Y – координаты ладьи перед первым ходом (X,Y ≤ 10⁹).

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

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

Примеры

Задача F. Охотник

Сезон охоты очень не долог, и поэтому оставшуюся часть года заядлые охотники развлекают себя тем, что стреляют по мишеням в тире. Тир представляет собой плоскость, на которой расставлены мишени. Размерами мишеней можно пренебречь и считать их точками с координатами (x, y). Также известно, что мишени сделаны из картона, поэтому за один выстрел можно поразить сразу все мишени, стоящие на линии выстрела. В начале координат стоит охотник и у него остался последний патрон. Охотник хочет использовать его эффективно – то есть за один выстрел поразить как можно больше целей. Помогите ему в этом.

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

В первой строке входного файла INPUT.TXT находится натуральное число N (N ≤ 100) – количество мишеней в тире. Далее следует N строк – описание мишеней. В (i+1)-й строке находится два целых числа x и y (-100 ≤ x, y ≤ 100) – координаты i-й мишени. Не существует двух мишеней, стоящих в одной точке, и никакая мишень не стоит в начале координат.

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

В выходной файл OUTPUT.TXT выведите максимальное количество мишеней, которое может подстрелить охотник за один выстрел.

Примеры

Задача G. Го

Совсем недавно Али-Баба узнал от своего брата Касима об удивительной игре Го. В Го играют на прямоугольной доске – гобане, расчерченном вертикальными и горизонтальными линиями. Все линии пронумерованы. В игре участвуют два игрока, которые по очереди выставляют на гобан камни – специальные круглые фишки. Каждый камень ставится на незанятую точку пересечения линий доски (пересечения называют пунктами). У одного игрока – черные камни, у другого – белые. Камни одного цвета, смежные по вертикали, либо по горизонтали (но не диагонали), объединяются в группу. Одиночный камень также считается группой.

Один из способов набрать очки в Го – захватить камни противника. Каждый камень может иметь от двух до четырех смежных с ним пунктов (по вертикали и горизонтали, но не по диагонали). Если такой пункт не занят камнем, то он называется «дамэ». Дамэ группы – это все дамэ камней, составляющих группу. Как только оппонент своими камнями закрывает все дамэ чужой группы, то эта группа считается захваченной и снимается с доски. Если у группы осталось лишь одно дамэ, то говорят, что эта группа находится в «атари» т.е. на один шаг от захвата соперником.

Дамэ черных камней на рисунке отмечены крестиком. Группа черных из камней (1, 3) и (1, 4) имеет 4 дамэ. Группа (6, 1), (6, 2) и (6, 3) имеет одно дамэ и находится в атари. Черный камень (4, 5) также находится в атари. Помогите Али-Бабе, который всегда играет черными, определить, какие его группы находятся в атари.

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

Первая строка входного файла INPUT.TXT содержит целое число N – размерность игровой доски (6 ≤ N ≤ 19). Далее следует N строк по N символов каждая. Каждый символ описывает один пункт доски. «B» означает черный камень, «W» – белый, «.» означает пустой пункт. Все группы на доске имеют хотя бы одно дамэ.

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

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

Примеры

Задача H. Орешки

Белочка собрала в лесу N шишек c орешками. Белочка очень привередливо выбирала шишки, и брала только те, в которых ровно M орешков. Также известно, что для пропитания зимой ей необходимо не менее K орешков. Определите, хватит ли на зиму орешков белочке.

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

Первая строка входного файла INPUT.TXT содержит три натуральных числа через пробел: N, M и K (N, M ≤ 100, K ≤ 10 000).

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

В выходной файл OUTPUT.TXT выведите «YES» если белочке хватит орешков и «NO» в противном случае.

Примеры