Студенческая олимпиада по программированию в Пензе
A. Буфет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Вити только что закончилась очередная пара. На перерыве между парами он решил сходить в буфет, чтобы купить булочку с корицей. Когда Витя подошел к буфету, он увидел огромную очередь из $$$n$$$ человек. Обслуживание одного человека занимает $$$k$$$ минут. Успеет ли Витя купить булочку с корицей до начала следующей пары, если она начнется через $$$t$$$ минут?

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

Первая и единственная строка содержит три числа: $$$n$$$, $$$k$$$ и $$$t$$$ — количество человек в очереди (не считая Вити), время обслуживания одного человека, время до начала следующей пары $$$(0 \le n \le 50, 1 \le k \le 10, 1 \le t \le 100)$$$.

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

Если Витя успеет купить булочку с корицей, выведите «YES» (без кавычек). В противном случае выведите «NO».

Примеры
Входные данные
5 3 25
Выходные данные
YES
Входные данные
3 4 16
Выходные данные
YES
Входные данные
3 4 15
Выходные данные
NO
Примечание

В первом примере, Вите, чтобы купить булочку с корицей, необходимо 18 минут: 15 минут, чтобы дождаться своей очереди и еще 3 минуты будут обслуживать Витю. Так как до начала пары 25 минут, Витя успевает сходить в буфет за булочкой.

Во втором примере Вите необходимо 16 минут. Витя успевает купить булочку, так как до начала пары ровно 16 минут.

В третьем примере Вите необходимо 16 минут. Но в этот раз Витя не успевает совершить покупку, так как до начала пары 15 минут.

B. PSU
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аня только что поступила в новый университет. На первом занятии по программированию ей выдали такую задачку на лабораторную работу.

Имеется строка длиной $$$s$$$, которая состоит только из букв 'P', 'S' или 'U'. Всего имеется $$$q$$$ изменений в этой строке. Каждое изменение меняет ровно одну букву в заданной позиции. Ане необходимо вычислить количество вхождений «PSU» в строке до изменений и после каждого ее изменения.

Задача показалась Ане сложной. Помогите ей с решением этой задачей и сдачей лабораторной, а то скоро сессия!

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

Первая строка входных данных содержит единственное число $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$ - длину строки $$$s$$$.

Вторая строка входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов 'P', 'S' или 'U'.

Третья строка содержит единственное число $$$q$$$ $$$(1 \le q \le 2\cdot10^5)$$$ - количество изменений в строке.

Далее идут $$$q$$$ строк. Каждая строка содержит позицию изменения $$$pos$$$ $$$(1 \le pos \le n)$$$ и символ $$$c$$$, равный 'P', 'S' или 'U'.

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

Выведите $$$q + 1$$$ число — количество вхождений «PSU» в строку $$$s$$$ до изменений и после каждого изменения.

Пример
Входные данные
6
SPSUSU
4
1 P
3 U
4 P
2 S
Выходные данные
1
1
0
1
2
Примечание

Изначально строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (со $$$2$$$-й позиции).

После первого изменения строка $$$s$$$ станет равна «PPSUSU». Строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (со $$$2$$$-й позиции).

После второго изменения строка $$$s$$$ станет равна «PPUUSU». Теперь, cтрока $$$s$$$ не содержит вхождений «PSU».

После третьего изменения строка $$$s$$$ станет равна «PPUPSU». Строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (с $$$4$$$-й позиции).

После четвертого изменения строка $$$s$$$ станет равна «PSUPSU». Строка $$$s$$$ содержит $$$2$$$ вхождения «PSU» (с $$$1$$$-й и $$$4$$$-й позиции).

C. Магазин дешевых вещей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рядом с ПГУ открылся магазин дешевых вещей. Магазин отличается тем, что в нем каждую неделю появляется только один товар, стоящий в разы дешевле, чем в других магазинах. Также в магазине имеется скидочная система – за каждую покупку человеку начисляется $$$k$$$ баллов, которыми можно оплатить только 100% следующей покупки ($$$1$$$ балл $$$=$$$ $$$1$$$ рубль).

Влад узнал по секрету, что на следующей неделе будут продавать очень красивые ручки. Он хочет купить себе всего $$$n$$$ ручек (ведь он не жадный, пусть и другие закупятся) по цене $$$m$$$ таким образом, чтобы потратить наименее возможное количество рублей.

Помогите Владу узнать, сколько он потратит рублей, если будет максимально экономить.

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

Первая и единственная строка содержит три числа: $$$n$$$, $$$m$$$ и $$$k$$$ — количество ручек, цена одной ручки и количество начисляемых баллов за одну покупку $$$(1 \le n \le 10^5, 1 \le m,k \le 10^4)$$$.

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

Выведите единственное число – наименьшее потраченное количество рублей.

Примеры
Входные данные
3 2 3
Выходные данные
4
Входные данные
5 4 3
Выходные данные
12
Примечание

В первом примере Влад покупает первую ручку за $$$2$$$ рубля. За эту покупку он получит $$$3$$$ балла. Вторую ручку, он может оплатить баллами. Таким образом, сейчас Влад купил 2 ручки, потратил $$$2$$$ рубля и у него остался $$$1$$$ балл. Третья ручку Владу придется купить за $$$2$$$ рубля (купить ручку за $$$1$$$ рубль и $$$1$$$ балл нельзя, так как баллами можно оплатить только 100% следующей покупки). Итого Влад потратит $$$4$$$ рубля.

D. Длинные руки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Артем как можно быстрее приехал к месту, где оказался Нурбек. После долгих раздумий как помочь другу, они оба сошлись на мысли, что самым логичным будет вынимать блоки из башни. Артем и Нурбек имеют руки длин $$$l_1$$$ и $$$l_2$$$ соответственно. Они собираются в каждый момент времени одновременно вынимать по одному блоку из башни каждый. Артем аккуратно достает блок башни и кладет его рядом с собой, а Нурбек скидывает блок с башни, что приводит к уничтожению блока. При этом достать из башни они могут только те блоки, до которых могут дотянуться, то есть для Артема это блоки, находящиеся на высоте не более $$$l_1$$$, а для Нурбека – находящиеся на высотах от $$$n-l_2+1$$$ до $$$n$$$. Спуститься с башни Нурбек сможет только тогда, когда руки друзей соприкоснутся, т.е когда $$$h \le l_1+l_2$$$, где $$$h$$$ - текущее количество блоков в башне

Для каждого блока также известны две величины: $$$c$$$ – стоимость и $$$m$$$ – масса. Артем и Нурбек не очень хотят ломать построенную кем-то башню, но и совсем без разрушений спустить друга не получится. Поэтому они хотят причинить башне минимальный ущерб, который вычисляется как сумма стоимостей сломанных блоков. В то же время, нужно помнить о показателе устойчивости башни, чтобы Нурбек случайно с нее не упал. Рассчитывается он как сумма масс всех блоков в башне, деленная на их количество. Например, если текущая башня состоит из $$$h$$$ блоков весом $$$m_1, m_2, \ldots, m_h$$$, то устойчивость башни вычисляется по формуле: $$$$$$\frac{\sum\limits_{i=1}^h m_i}{h}$$$$$$ Если у друзей имеется несколько способов минимизировать ущерб, нанесенный башне, то на каждом шаге они вынимают такой блок, чтобы устойчивость башни была наибольшей.

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

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

Первая строка содержит три числа: $$$n$$$, $$$l_1$$$, $$$l_2$$$ $$$(2 \le n \le 2\cdot10^5, 1 \le l_1,l_2 \le 10^5, l_1+l_2 \le n)$$$ – количество блоков в башне, длины рук Артема и Нурбека соответственно.

Вторая строка содержит $$$n$$$ чисел $$$c_1, c_2, \ldots, c_n$$$ $$$(1 \le c_i \le 10^9)$$$ – стоимости блоков.

Третья строка содержит $$$n$$$ чисел $$$m_1, m_2, \ldots, m_n$$$ $$$(1 \le m_i \le 10^9)$$$ – массы блоков.

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

В первой строке выведите два числа: $$$k$$$ – количество вынутых блоков и $$$sum$$$ – суммарный нанесенный ущерб. Вторая строка должна содержать $$$\frac{k}{2}$$$ чисел $$$p_1, p_2, \ldots, p_{k/2}$$$ – устойчивости башни после того, как Нурбек и Артем вынут по блоку. Значение устойчивости будет считаться правильным, если абсолютная или относительная погрешность числа не превышает $$$10^{-4}$$$.

Примеры
Входные данные
4 1 1
7 2 4 6
3 2 1 4
Выходные данные
2 6
1.5000
Входные данные
7 2 2
2 2 2 4 2 1 2
1 2 3 4 5 6 7
Выходные данные
4 3
4.2000 4.6667
Примечание

В первом тесте Артему и Нурбеку необходимо вынуть по одному блоку. Артем вынимает нижний блок с ценностью $$$7$$$ и массой $$$3$$$ и кладет его рядом с собой. Нурбек вынимает верхний блок со стоимостью $$$6$$$ и весом $$$4$$$ и разбивает его. Таким образом, суммарный нанесенный ущерб составит $$$6$$$. После этого в башне останется два блока с массой $$$2$$$ и $$$1$$$. Устойчивость башни составит $$$(2 + 1) / 2 = 1.5$$$.

Во втором тесте Артему и Нурбеку необходимо суммарно вынуть $$$4$$$ блока. Сначала Артем вытащит первый блок, а Нурбек предпоследний. После этого в башне останется $$$5$$$ блоков суммарной массой $$$21$$$ и показателем устойчивости $$$21/5 = 4.2$$$. Так как друзья еще не могут дотянуться друг до друга, им необходимо вынуть еще по одному блоку. Артем вынет второй блок, а Нурбек вынет пятый блок. После этого, в башне останется $$$3$$$ блока суммарной массой $$$14$$$ и показателем устойчивости $$$14/3 = 4.6667$$$. Друзья разрушили пятый и шестой блок, а значит суммарный ущерб составит $$$3$$$.

E. А зачем нужен калькулятор?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

А как вы видите программирование? Многие предполагают, что программисту необходимо работать не только с программами, но и с техникой. Вот и Артему не повезло – его начальник считает так же. Бедному программисту дали инженерный калькулятор, дисплей которого вмещает $$$n$$$ цифр. Калькулятор, понятное дело, имеет только одну рабочую кнопку – увеличить число на дисплее на единицу.

Изначально на дисплее экрана отображается число $$$1$$$. Артему требуется получить на дисплее калькулятора число $$$x$$$, которое удовлетворяет следующим условиям:

$$$1)$$$ $$$x$$$ является степенью числа $$$2$$$.

$$$2)$$$ В $$$k$$$–том разряде числа $$$x$$$ находится цифра $$$p$$$ (разряды у калькулятора нумеруются справа налево с 0).

$$$3)$$$ Из-за того, что дисплей калькулятора вмещает не более $$$n$$$ цифр, в числе $$$x$$$ также должно быть не более $$$n$$$ разрядов.

Артем боится, что и последняя кнопка на его калькуляторе скоро сломается, поэтому он хочет использовать ее минимальное количество раз, но и в тоже время попытаться найти число для начальства. Помогите Артему узнать сколько раз ему придется нажать на кнопку калькулятора, чтобы получить на дисплее требуемое число $$$x$$$.

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

Единственная строка входных данных содержит натуральные числа $$$n$$$, $$$k$$$ и $$$p$$$ ($$$1 \le n \le 18$$$, $$$0 \le k \lt n$$$, $$$0 \le p \le 9$$$) – количество цифр на дисплее калькулятора, номер разряда, в котором должна стоять цифра $$$p$$$, и сама эта цифра.

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

Выведите единственное число – количество нажатий на кнопку калькулятора. Если требуемое число на дисплее калькулятора получить невозможно, то выведите "$$$-1$$$".

Примеры
Входные данные
3 0 1
Выходные данные
0
Входные данные
5 3 7
Выходные данные
-1
Входные данные
5 2 0
Выходные данные
1023
Примечание

В первом примере минимальным числом является $$$1$$$. Оно удовлетворяет всем условиям: $$$2^0=1$$$, в нулевом разряде этого числа находится $$$1$$$ и в нем всего $$$1$$$ разряд.

Во втором примере не существует числа, удовлетворяющего условию, поэтому ответ: $$$-1$$$.

В третьем примере минимальным подходящим числом является $$$2^{10}=1024$$$, следовательно Артему необходимо нажать на кнопку 1023 раза.

F. Все дороги ведут в ПГУ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Женя очень любит шахматы. Он не пропускает ни одного турнира по шахматам, особенно в своем любимом университете. Женя узнал, находясь в Москве, что в ПГУ скоро стартует новый турнир по шахматам. «Это отличная возможность испытать мое изобретение!» — подумал изобретатель. Единственной проблемой оказались дороги...

Женя нашел карту со всеми дорогами, ведущими в ПГУ. Он очень расстроился, когда увидел большое количество разбитых дорог. Осознав, что в наших реалиях починить все дороги невозможно, он задался вопросом — «Сколько нужно починить дорог, чтобы из каждого города можно было попасть в ПГУ по целым дорогам, не используя разбитые?»

Помогите Жене посчитать число дорог, пока он не опоздал на турнир.

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

Первая строка содержит два числа: $$$n$$$ и $$$m$$$ $$$(1 \le n \le 2\cdot10^5, 1 \le m \le 2\cdot10^5)$$$ — количество объектов и количество дорог между ними соответственно.

Вершина с индексом $$$1$$$ всегда обозначает ПГУ.

Следующие $$$m$$$ строк содержат $$$t$$$ — качество дороги ($$$0$$$ — целая дорога, $$$1$$$ — разбитая дорога), $$$v$$$ и $$$u$$$ $$$(1 \le v \le n, 1 \le u \le n, v \ne u)$$$ — объекты, между которыми проложена дорога. Все дороги попарно различны. Гарантируется, что существует путь из любой вершины к вершине $$$1$$$.

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

В ответ выведите единственное число — минимальное количество дорог, которое надо отремонтировать

Примеры
Входные данные
4 3
0 1 2
1 2 3
0 3 4
Выходные данные
1
Входные данные
3 3
0 1 2
0 2 3
0 3 1
Выходные данные
0
Входные данные
6 7
0 1 2
0 2 3
1 3 1
1 3 4
1 4 5
1 5 6
0 6 4
Выходные данные
2
Примечание

Последний пример показан на рисунке ниже. Нужно обязательно починить дорогу $$$3-4$$$ и любую на выбор между $$$4-5$$$ и $$$5-6$$$.

G. Шахматный турнир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Женя приехал проверить работу своего нового изобретения — Аброахомудиях$$$^©$$$. С его помощью можно определить исход матча, играя за черные или белые фигуры. На экране изобретения отображается две строки — $$$s$$$ и $$$t$$$. Первая строка показывает исход матча, если пользователь изобретения будет играть за белые фигуры. Вторая строка — аналогично за черные фигуры. Женя никогда не будет поддаваться противнику: намерено проигрывать или делать ничью, если он мог добиться лучшего результата.

Женя может договориться с каждым из своих оппонентов и выбрать цвет фигур, которым он будет играть. Женя понимает, что судьи заподозрят его в нечестной игре, если он будет часто выигрывать. Поэтому Женя установил для себя правило — не играть за один и тот же цвет второй раз, если до этого он выиграл (т.е., если Женя играл за белые фигуры и выиграл, то следующую партию он не будет играть за белый цвет).Помогите юному изобретателю получить как можно больше рейтинга на турнире шахматистов.

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

Первая строка содержит единственное число $$$n$$$ — количество партий, которые предстоит сыграть $$$(1 \le n \le 200000)$$$.

Вторая строка содержит $$$n$$$ чисел: $$$a_1, a_2, \cdots, a_n$$$ — изменения рейтинга $$$(1 \le a_i \le 1000)$$$.

Третья строка входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую их символов 'W', 'L' и 'D'. Если $$$i$$$-й символ строки $$$s$$$ равен 'W', то $$$i$$$-я партия закончится победой при игре белым цветом, 'D' - ничьей, 'L' - поражением.

Четвертая строка входных данных содержит строку $$$t$$$ длины $$$n$$$, состоящую их символов 'W', 'L' и 'D'. Если $$$i$$$-й символ строки $$$t$$$ равен 'W', то $$$i$$$-я партия закончится победой при игре черным цветом, 'D' - ничьей, 'L' - поражением.

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

Выведете одно число — максимальное возможное изменение рейтинга.

Примеры
Входные данные
3
10 8 12
WDL
WWL
Выходные данные
6
Входные данные
4
1 10 12 7
WWDL
DLDW
Выходные данные
17
Примечание

В первом примере оптимальная стратегия следующая: выиграть первую партию за черный цвет, выиграть вторую партию белыми фигурами и проиграть третью партию черными. Изменение рейтинга составит $$$10 + 8 - 12 = 6$$$.

Во втором примере 1, 3 и 4 партию необходимо играть черными фигурами, 2 партию - белыми. Изменение рейтинга составит: $$$0 + 10 + 0 + 7 = 17$$$.

H. По тарелочкам
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Отвлечемся немного от программирования. Давайте постреляем по тарелкам!

Саша попал на тренировку по стендовой стрельбе среди профессионалов. У каждого на этой тренировке всего один выстрел. Выпускается две тарелки, которые стоят по очкам $$$b_1$$$ и $$$b_2$$$. Каждую тарелку можно представить как круг на плоскости с центром в точке $$$(x, y)$$$ и радиусом $$$r$$$.

Мы знаем, что Саша мастер высшего уровня по стрельбе. Он может попасть в любую точку. Нужно лишь набрать максимальное количество очков на тренировке.

Помогите Саше набрать максимальное количество за эту простую тренировку!

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

Первая строка содержит $$$4$$$ целых числа, описывающих первую тарелку. Координаты центра тарелки $$$x_1$$$ и $$$y_1$$$ $$$(|x_1| \le 10^9, |y_1| \le 10^9)$$$, ее радиус $$$ r_1$$$ $$$(1 \le r_1 \le 10^9)$$$ и количество очков, начисляемое за попадание $$$b_1$$$ $$$(-10^9 \le b_1 \le 10^9)$$$.

Вторая строка содержит 4 целых числа $$$x_2, y_2, r_2, b_2$$$, описывающих вторую тарелку аналогично.

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

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

Выведите единственное число — максимальное количество очков, котороe можно набрать, совершив один выстрел.

Примеры
Входные данные
2 3 2 6
5 5 1 5
Выходные данные
6
Входные данные
2 2 2 5
2 2 1 -3
Выходные данные
5
Входные данные
1 1 1 7
3 1 1 3
Выходные данные
10
Примечание

В первом примере наиболее выгодная стратегия — сделать выстрел по первой тарелке, таким образом можно набрать $$$6$$$ очков.

Во втором примере необходимо стрельнуть в первую тарелке, но при этом не попасть во вторую. Например, можно стрельнуть в точку $$$(2, 0.5)$$$. Таким образом, во втором примере можно набрать $$$5$$$ очков. При выстреле в точку $$$(2, 2)$$$ Саша получит $$$2$$$ очка, так как за попадание по второй тарелке начисляется отрицательное количество очков.

В третьем примере можно выстрелить в точку $$$(2, 1)$$$ и получить очки за обе тарелки. Обратите внимание, что очки за попадание начисляются даже в том случае, если выстрел был произведен в край тарелки.

I. Разделение труда
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Осталось всего неделя до конца учебы, а Гена и Антон еще даже не приступали к лабораторным работам.

В этом семестре у ребят всего $$$5$$$ дисциплин. По каждой из $$$5$$$ дисциплин необходимо сдать $$$a_1, a_2, a_3, a_4, a_5$$$ лабораторных работ. Ребятам повезло, все лабораторные работы можно сдавать бригадой. Гена и Антон решили разделить обязанности: лабораторные работы по одним дисциплинам будет делать Гена, по другим — Антон.

Смогут ли Гена и Антон распределить обязанности так, чтобы каждый из них сделал одинаковое количество лабораторных работ. Обратите внимание, что ребята распределяют между собой дисциплины, а не сами лабораторные работы. Изучите примеры и примечание для лучшего понимания.

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

Первая и единственная строка содержит пять целых чисел: $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ и $$$a_5$$$ — количество лабораторных работ, по $$$1$$$-й, $$$2$$$-й, $$$3$$$-й, $$$4$$$-й и $$$5$$$-й дисциплине соответственно $$$(1 \le a_i \le 100, 1 \le i \le 5)$$$.

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

Если Гена и Антон смогут распределить дисциплины так, чтобы каждый их них сделал одинаковое количество лабораторных работ, выведите «YES» (без кавычек). В противном случае выведите «NO».

Примеры
Входные данные
5 4 20 5 6
Выходные данные
YES
Входные данные
2 6 12 4 10
Выходные данные
NO
Входные данные
1 1 1 1 1
Выходные данные
NO
Примечание

В первом примере ребята могут распределить обязанности следующим образом: Гена сделает лабораторные работы по $$$3$$$-й дисциплине, остальные дисциплины достанутся Антону. Таким образом, каждый из ребят сделает по $$$20$$$ лабораторных работ.

Во втором и третьем примере Гена и Антон не могут распределить дисциплины между собой так, чтобы ребятам досталось одинаковое количество лабораторных работ.