Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
"Наш дом всегда отдаёт долги" - сказал Мастер над монетой и призадумался. Отдавать-то долги сейчас нечем. Для того, чтобы заработать денег, Казначей хочет продать кувшин дикого огня подороже и для этого узнал, сколько будет стоить кувшин в каждый из последующих n дней. По полученным данным, в i-ый (1 ≤ i ≤ n) день кувшин дикого огня будет стоить ci золотых монет.
К сожалению, сейчас у Мастера над монетой нет ни денег, ни дикого огня, однако, он в хороших отношениях с гильдией алхимиков. Поэтому Казначей решает одолжить кувшин дикого огня "в политических целях". Алхимики готовы уступить кувшин дикого огня за x золота ровно на один день. Мастер над монетой придумал план - он хочет выбрать некоторый день j (1 ≤ j ≤ n), одолжить кувшин дикого огня и в тот же день его продать за cj золотых. На следующий j + 1-ый день на вырученные деньги Казначей хочет купить новый кувшин дикого огня по цене текущего дня за cj + 1 монет и вернуть гильдии алхимиков как дикий огонь, так и x золота за аренду.
Помогите Мастеру над монетой и выясните, сколько золотых монет он сможет заработать, проведя описанную ранее схему. Также учтите, что если на каком-либо этапе у него не хватит золота, то такой план не будет осуществлён.
В первой строке подаётся два целых числа n и x (2 ≤ n ≤ 100, 0 ≤ x ≤ 1015)- количество дней и стоимость взятия дикого огня в аренду.
Во второй строке записано n целых чисел c1, c2, ... ,cn (0 ≤ ci ≤ 1015) - стоимость кувшина дикого огня в i-ый день.
Выведите одно единственное число - максимально возможный заработок при осуществлении плана. Если план не может быть осуществлен, выведите 0.
2 ≤ n ≤ 100
0 ≤ x ≤ 1015
0 ≤ ci ≤ 1015, при i = 1...n
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
x | ci | ||
1 | 10 | 1 ≤ x ≤ 100 | 1 ≤ ci ≤ 100 |
2 | 35 | 1 ≤ x ≤ 10000 | 1 ≤ ci ≤ 10000 |
3 | 55 | 1 ≤ x ≤ 1015 | 1 ≤ ci ≤ 1015 |
В первом примере оптимально арендовать и продать кувшин, когда он стоит 97 монет, и выкупить обратно на следующий день по цене в 3 монеты, за вычетом стоимости займа прибыль составила 84 зотолые монеты.
Аналогично первому примеру, арендуем кувшин в первый день, прибыль составляет 97 золотых монет.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Антона позвали на работу тестировщиком карт для одной популярной игры "Балорант". Антон уже давно играет в Балорант и знает всех персонажей. Тестировать карты он собирается на Даон - самом быстром персонаже в игре. Карта представляет собой клетчатое поле n * m, каждая клетка которого или свободна, или занята препятствием. Даон может передвигаться со скоростью до k клеток в секунду. Каждую секунду Антон может выбрать, в какую сторону будет бежать Даон (вверх, вниз, влево или вправо), после чего персонаж пробегает в этом направлении от 1 до k клеток. Разумеется, что Даон может передвигаться только по свободным клеткам карты.
Работа Антона заключается в проверке, сможет ли персонаж добраться из клетки с координатами (x1, y1) в клетку (x2, y2).
Антон очень ленивый и не собирается долго работать. Всё, что он хочет - сам поиграть в Балорант. Помогите Антону написать программу, которая будет определять, за какое минимальное количество секунд Даон сможет добежать из квадрата (x1, y1) в квадрат (x2, y2). Если геймдизайнеры продумали уровень плохо, и персонаж никак не может добраться до требуемой точки - программа должна вывести − 1
В первой строке подаются целые числа n, m, k(1 ≤ n,m,k ≤ 1000) - размеры карты и скорость Даон.
Во второй строке содержатся 4 целых числа x1, y1, x2, y2(1 ≤ x1,x2 ≤ n, 1 ≤ y1,y2≤m). В задаче гарантируется, что клетки (x1, y1) и (x2, y2) свободны.
Далее следует n строк, каждая длиной m символов. Каждая i-ая строка содержит на j-ой позиции символ "." для свободной клетки или символ "#", если клетка занята препятствием.
Выведите одно единственное число - минимальное время, за которое Даон добежит из клетки (x1, y1) в клетку (x2, y2). Если Даон не может добраться из (x1, y1) в (x2, y2) - выведите − 1.
(1 ≤ n,m,k ≤ 1000)
(1 ≤ x1,x2 ≤ n, 1 ≤ y1,y2≤m)
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
n | m | k | ||
1 | 10 | 1 ≤ n ≤ 10 | 1 ≤ m ≤ 10 | 1 ≤ k ≤ 10 |
2 | 35 | 1 ≤ n ≤ 100 | 1 ≤ m ≤ 100 | 1 ≤ k ≤ 100 |
3 | 55 | 1 ≤ n ≤ 1000 | 1 ≤ m ≤ 1000 | 1 ≤ k ≤ 1000 |
В первом примере Даон пробегает 3 клетки вправо, 2 клетки вниз и 3 клетки вправо. Ответ 3 секунды. Иллюстрация движения Даон в первом примере:
Д-→Д
###↓
Д←-Д
Во втором примере Даон не смогла дойти до требуемой точки, поэтому ответ -1
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
На космической станции зеленый код. Клоуну стало скучно, поэтому он начал искать, как же ему пошкодить, чтобы сотрудники службы безопасности не расслаблялись. Клуня раскидал n различных банановых кожурок на пол в холе отбытия. Почесав затылок, он придумал еще более гениальную идею для пранка.
Зная о Культе Магна'Триангулум, клуня хитро потер ручками и потянулся в карман за красным мелком. После этого он попарно соединил линией кроваво-красного мелка все кожурки и увидел, что у него получилось много треугольников с вершинами на банановых кожурках, что сильно напоминало руну культистов Магна'Триангулум.
Теперь клоуну нужно поднять шумихи, чтобы код подняли до красного в связи с угрозой культа. Но чтобы его показания были верны, ему нужно знать точное количество треугольников, ибо их количество отвечает за серьезность намерения культа.
Так как клоун бросил школу после 4го класса, он просит вас посчитать количество различных образовавшихся треугольников с НЕНУЛЕВОЙ площадью.
В первой строке задаётся единственное целое число n (1 ≤ n ≤ 2000) - количество банановых кожурок, раскиданных по холу отбытия.
Далее следует n строк, в каждой из которых содержится два целых числа xi и yi ( − 100 ≤ xi, yi ≤ 100) - координаты кожурки.
Одно единственное целое число - количество различных треугольников с ненулевой площадью.
1 ≤ n ≤ 2000
− 100 ≤ xi,yi ≤ 100
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | |||
1 | 10 | 1 ≤ n ≤ 100 | |
2 | 35 | 1 ≤ n ≤ 1000 | |
3 | 55 | 1 ≤ n ≤ 2000 |
В примере можно построить следующие треугольники:
(0,0) (1,1) (2,0)
(0,0) (2,0) (2,2)
(1,1) (2,2) (2,0)
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Кхалиси очень нравятся разводить питомцев, а именно драконов. Использует она их в различных целях и хочет, чтобы в этот момент они были ну уж очень могущественными.
Дотракийцы привыкли описывать силу живых существ натуральным числом - их примеру и последовала Кхалиси, начав оценивать своих драконов.
Также Кхалиси считает, что настоящее могущество заключается не только в силе, но и в ряде других факторов, поэтому она решила, что её дракон будет воистину могущественным, если разность значения силы дракона и суммы всех цифр в числе силы дракона не меньше параметра могущества p (1 ≤ p ≤ 1019).
Кхалиси занята взращиванием драконов и ей некогда отвлекаться на расчёты. Поэтому она просит у вас найти ответ на вопрос: "Сколько раз дракон становился по-настоящему могущественным повышая свою силу от 1 до текущей силы n (1 ≤ n ≤ 1019)"
В первой и единственной строке записано два натуральных числа n и p (1 ≤ n,p ≤ 1019) — текущая силы дракона и параметр могущества
Выведите одно число - сколько раз дракон становился могущественным
1 ≤ n,p ≤ 1019
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | p | ||
1 | 10 | 1 ≤ n ≤ 103 | 1 ≤ p ≤ 103 |
2 | 35 | 1 ≤ n ≤ 105 | 1 ≤ p ≤ 105 |
3 | 55 | 1 ≤ n ≤ 1019 | 1 ≤ p ≤ 1019 |
В первом примере, дракон с силой 22, 21, 20 являются могущественными, поэтому ответ 3.
Во втором примере не нашлось такой силы при заданном параметре, чтобы дракон являлся могущественным, поэтому ответ 0
При решении задачи на C++ пользуйтесь типом данных unsigned long long
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Денис проводит часы за компьютером, играя в видео-игры. Ему очень нравится игра "Балорант", но даже больше ему нравистся игра "Ига Игенд" - онлайн игра для десятерых человек. Игра представляет собой арену, на которой сражаются чемпионы. В игре есть n игровых чемпионов, и Денис хочет научиться играть на них всех.
В Иге Игенд есть одна особенность, что героев необходимо покупать, это сделано для того, чтобы новички не играли сразу на тяжелых чемпионах. Поэтому, чтобы не тратить время открытие всех чемпионов, Денис решает играть в особый режим "один против одного", потому что в этом режиме даётся случайный чемпион для игры. В начале каждой партии игра выбирает набор из трёх случайных чемпионов и показывает его оппонентам. Каждый игрок должен забанить чемпиона, после чего игра выдаёт случайного чемпиона обоим игрокам из тех, кто не был забанен (оба игрока играют на одном и том же случайном чемпионе).
Также Денис хочет поддерживать приемлемый уровень побед, чтобы не портить свою статистику, поэтому он хочет иногда играть на тех чемпионах, которые были им изучены. Но Денису нужно ходить на пары и на работу, поэтому у него не так много времени, чтобы изучить всех чемпионов. Денис не очень хорош в теории вероятности, поэтому просит у вас помощи в ответе на вопрос: "Какое минимальное количество чемпионов я должен изучить, чтобы вероятность сыграть на одном из них была не меньше p?".
Заметьте, в Иге Игенд не видно, какой попался противник, поэтому считается, что оппоненты Дениса будут банить персонажей случайным образом.
Первая строка содержит два числа n (3 ≤ n ≤ 106) и p (0 ≤ p ≤ 1) - количество чемпионов в игре и требуемая вероятность сыграть на изученном чемпионе. p будет иметь не более четырех цифр после запятой.
Выведите минимальное количество чемпионов, которое должен изучить Денис.
1 ≤ n ≤ 106
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | |||
1 | 10 | 1 ≤ n ≤ 100 | |
2 | 35 | 1 ≤ n ≤ 1000 | |
3 | 55 | 1 ≤ n ≤ 106 |
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Вы решили тряхнуть стариной и поиграть в вашу любимую игру 2000-ых годов - "Линейку". Одному вам было играть скучно и вы решили позвать с собой друга. Не найдя занятия лучше, вы с другом решили пофармить.
Ваш друг скаут нашёл t пар точек для фарма - Ai и Bi, таких, что на данный момент в точке Ai стоят xi мобов, а в точке Bi - yi. Дроп с каждого моба в точке Ai занимает si слотов инвентаря, а в точке Bi - wi. Также дроп с мобов для любой пары точек продаётся торговцу за одинаковую цену.
Вы придумали стратегию для фарма: вы со своим другом фармите поочередно каждую из t пар точек, до тех пор, пока не забьётся инвентарь, после чего вы сдаёте дроп и переходите к следующей паре точек. Вместимость вашего инвентаря - u слотов, а вашего друга v слотов.
Узнайте, максимальное количества дропа, которое вы можете вынести с каждой пары точек. Гарантируется, что суммарное количество дропа суммарно на всех парах точек не превосходит 106.
В первой строке подаётся единственное целое число t (1 ≤ t ≤ 104).
В первой строке каждого набора данных заданы два целых числа u и v (1 ≤ u,v ≤ 109) - количество слотов вашего инвентаря и вашего друга.
Во второй строке каждого набора данных заданы два целых числа x и y (1 ≤ x,y ≤ 2 ⋅ 105) - количество мобов на точках Ai и Bi.
В третьей строке каждого набора данных заданы два целых числа s и w (1 ≤ s,w ≤ 109) - количество слотов, который занимает дроп с точек Ai и Bi
Для каждой пары точек выведите суммарное максимальное количества лута, который можно зафармить и унести со своим другом.
1 ≤ t ≤ 104
1 ≤ u,v ≤ 109
1 ≤ x,y ≤ 2 ⋅ 105
1 ≤ s,w ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
t | u,v,s,w | x,y | ||
1 | 10 | 1 ≤ t ≤ 10 | 1 ≤ u,v,s,w ≤ 100 | 1 ≤ x,y ≤ 100 |
2 | 35 | 1 ≤ t ≤ 103 | 1 ≤ u,v,s,w ≤ 105 | 1 ≤ x,y ≤ 103 |
3 | 55 | 1 ≤ t ≤ 104 | 1 ≤ u,v,s,w ≤ 109 | 1 ≤ x,y ≤ 105 |
В первом наборе данных вы забираете 3-х мобов с первого кэмпа и 3-х со второго, а ваш друг 3-х с первого и 2-х со второго. Итого 11 единиц лута.
Во втором наборе данных вы фармите всех мобов, 20 единиц лута.
В третьем наборе в ваш инвентарь ничего не поместится, а вот напарник может забрать лут с трёх мобов на второй точке. Ответ 3.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Тимоше нравятся числа Фибоначчи настолько, что он решил называть последовательности, которое похожи на числа Фибоначчи, красивыми. Тимоша посчитает ряд красивым, если:
1. Последовательность состоит не менее чем из двух элементов.
2. Первое и второе число последовательности могут быть любыми.
3. Каждый последующий элемент последовательности равен сумме двух предыдущих (за исключением первых двух элементов).
Тимоша записал на доске ряд чисел f1,f2,...,fn. Тимоша хочет сделать ряд красивым и для этого может переставлять местами любые элементы. Однако, Тимоша знает, что случайно написанные числа вряд ли станут красивой последовательностью, поэтому он решает находить красивые подпоследовательности.
Помогите Тимоше и ответьте - какой максимальной длины может получится красивая подпоследовательность после перестановки элементов.
В первой строке записано единственное число n (2 ≤ n ≤ 1000) — длина последовательности fi.
В следующих n строках записано n целых чисел a1,a2,...,an (|ai| ≤ 109).
Выведите количество элементов в самой длинной красивой подпоследовательности после перестановки элементов.
2 ≤ n ≤ 1000
|ai| ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | ai | ||
1 | 10 | 2 ≤ n ≤ 10 | |ai| ≤ 100 |
2 | 35 | 2 ≤ n ≤ 100 | |ai| ≤ 105 |
3 | 55 | 2 ≤ n ≤ 1000 | |ai| ≤ 109 |
В примере если переставить как − 12135, то подпоследовательность − 1213 станет красивой
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Новогодня пора! Время веселья, отпусков и каникул! Но не для всех...
Дедушка Мороз много прокрастинировал, и у него горят дедлайны по созданию детских игрушек. Но, к счастью, его брат Санта Клаус отправил ему на стажировку своих лучших эльфов!
Получив новоприбывших помощников Дедушка Мороз начал разделять обязанности среди эльфов и сверять количество игрушек со временем, что им осталось до Нового Года.
У эльфов есть заказ на n игрушек, каждую из которых нужно сделать, покрасить и упаковать. В распоряжении Дедушки Мороза s1 эльфов мастеров, s2 эльфов художников и s3 эльфов упаковщиков. Каждый эльф может работать лишь с одной игрушкой в один момент времени. Эльфы работают согласно конвеерному производству. Сначала Мастер должен собрать игрушку из частей. После Художник раскрашивает собранную игрушку. Затем Упаковщику остаётся обернуть покрашенную игрушку подарочной бумагой.
Сбор одной игрушки занимает t1 минут, покраска - t2 минут, ну а упаковка - t3 минут. Найдите минимальное колличество минут, за которое эльфы смогут собрать, покрасить и упаковать все игрушки.
Первая строка содержит число необходимых игрушек: n (1 ≤ n ≤ 104).
Вторая строка содержит число эльфов каждой профессии: s1, s2, s3 (1 ≤ s1, s2, s3 ≤ 1000).
Третья строка содержит число времени работы эльфа каждой професии: t1, t2, t3 (1 ≤ t1, t2, t3 ≤ 1000).
Выведите одно целое число — минимальное количество минут, за которые можно собрать, покрасить и упаковать все игрушки.
1 ≤ k ≤ 104
1 ≤ s1, s2, s3 ≤ 1000
1 ≤ t1, t2, t3 ≤ 1000
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | ||
---|---|---|---|---|
n | s1, s2, s3 | t1, t2, t3 | ||
1 | 10 | 1 ≤ n ≤ 10 | 1 ≤ s1, s2, s3 ≤ 10 | 1 ≤ t1, t2, t3 ≤ 10 |
2 | 35 | 1 ≤ n ≤ 1000 | 1 ≤ s1, s2, s3 ≤ 100 | 1 ≤ t1, t2, t3 ≤ 100 |
3 | 55 | 1 ≤ n ≤ 104 | 1 ≤ s1, s2, s3 ≤ 1000 | 1 ≤ t1, t2, t3 ≤ 1000 |
В примере 3 подарка одновременно отправляются на сборку, после по очереди раскрашиваются и упаковываются. Ответ 5.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
В Найт-Сити близится Новогодняя пора. Власти города на последние деньги в этом году восстановили городское освещение в жилых районах из n фонарей нового класса. Модель уличного фонаря с выдвижной голограммой новогодней ели для понижения излишнего стресса у горожан. Каждый фонарь имеет нумерацию согласно их яркости от 1 до n, причем вся нумерация на фонарях идёт в произвольном порядке.
Но разве киберпанкам есть дело до такой мелочи? Конечно есть, при свете преступления заметнее. Поэтому несколько банд наемников оперативно перебили только что восстановленное освещение в нескольких точках города.Теперь городскому аппарату придется занимать средства у Арасаки для восстановления сети освещения. Мегакорпорация также поделилась с властями города информацией, что некоторая комбинация фонарей вызывает у некоторых людей короткое замыкание зрительных имплантов, поэтому деньги будут выданы в займы, если будут соблюдаться некоторые условия расположения фонарей.
Арасака называет причину воникновения короткого замыкания в зрительных имплантах - рядом стоящие фонари, имеющие разную чётность яркости освещения. Также мегакорпорация называет такую пару фонарей замыкающими.
Арасака прогнозирует, что избегание замыкающих фонарей перестанет так сильно выводить из себя уличный сброд, поэтому власти города хотят минимизировать количество замыкающих пар фонарей, чтобы их потом снова не разбили.
Найдите способ восстановить уничтоженные фонари на улицах, чтобы минимизировать количество замыкающих фонарей.
Первая строка содержит одно целое число n (1 ≤ n ≤ 100) — количество фонарей на улице.
Вторая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ n) — яркость i-го фонаря или 0, если киберпанки его уничтожили.
Выведите единственное число — минимальную сложность правильного освещения.
(1 ≤ n ≤ 100)
(0 ≤ ai ≤ n)
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | |||
1 | 10 | 1 ≤ n ≤ 10 | |
2 | 35 | 1 ≤ n ≤ 50 | |
3 | 55 | 1 ≤ n ≤ 100 |
В примере один из способов оптимального размещения фонарей выглядит следующим образом - 1 3 5 4 2 6. Ответ 1 пара замыкающих фонарей.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Автор: | Денис Лысенко | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Студенты дальнего востока прошли в межпланетный этап ICPC и готовились к вылету. Так как спонсорами выступили местные компании, им удалось собрать не так много денег, поэтому им придется лететь на межпланетной электричке, вместо нормального комического корабля. Проблема космических электричек в том, что в них стоит плазменный двигатель низкой мощности, что не позволяет тянуть обшивку большой массы, поэтому они обладают вытянутым узким корпусом.
В вагоне электрички есть n последовательных мест. Каждое место или пустое, или занято пассажиром.
Команда финалистов ICPC состоит из x олимпиадных программистов и y тренеров. Так как еще одна из проблем космических электричек - непрочная обшивка (чтобы максимально увеличить грузоподъёмность летательного аппарата), крайне не рекомендуется вести громких разговоров в вагоне. А наши финалисты очень любят пошуметь и поиграть в различные игры... Да и тренеры не прочь обсудить друг с другом методы обучения и новые типы задач. Поэтому компания-перевозчик обязала рассадить финалистов определенным способом для их же безопасности.
Была придумана следующая посадка - участников надо садить рядом с тренерами, но не рядом с другими участниками. Также было принято решение не садить тренеров рядом с другими тренерами.
Нужно определить наибольшее количество участников и тренеров из всех x + y, которых можно посадить в вагоне так, чтобы никакой участник не сидел рядом с другим участником и никакой тренер не сидел с другим тренером. Также изначально некоторые места заняты сумками участников, на эти места садится нельзя.
В первой строке следует три целых числа n, x и y (1 ≤ n ≤ 106, 0 ≤ x,y ≤ 106, x + y ≠ 0) — общее количество мест в вагоне, количество участников и тренеров.
Во второй строке следует строка длины n, состоящая из символов . и #. Точка означает, что соответствующее место свободно. Звездочка означает, что соответствующее место занято межпланетным путешественником.
Выведите наибольшее количество людей, которых можно посадить вышеописанным способом.
1 ≤ n ≤ 106
0 ≤ x,y ≤ 106
x + y > 0
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача | Баллы | Дополнительные ограничения | |
---|---|---|---|
n | a,b | ||
1 | 10 | 1 ≤ n ≤ 10 | 0 ≤ a,b ≤ 10 |
2 | 35 | 1 ≤ n ≤ 103 | 0 ≤ a,b ≤ 103 |
3 | 55 | 1 ≤ n ≤ 106 | 0 ≤ a,b ≤ 106 |
Далее воспринимаем X как участника и Y как тренера.
В примере можно посадить всех людей, например, следующим образом:
XY#YX
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|