Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Бургеры в McDuck's#38515

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.

Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени t_i, закажет x_i бургеров и будет готов заплатить за них c_i бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил x_i бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени t_i. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.

Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — t_i, x_i, c_i (1 ≤ t_i, x_i, c_i ≤ 10⁹) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что t_i−1 ≤ t_i.

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

Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.

Примеры

№	Входные данные	Выходные данные
1	2 1 1 1 1 5 1 1 7	12
2	3 2 2 1 6 8 2 5 10 3 4 4	12

Динамическое программирование Динамическое программирование: два параметра

✓ 2✗ 101 300средняяВойти и решать

Путешествие по строке#38511

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

sqrt декомпозиция Дерево отрезков, RSQ, RMQ Динамическое программирование Суффиксный массив Хеш Хеш

✓ 1✗ 7—Войти и решать

Подстроки подпоследовательностей#38509

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3] является попоследовательностью массива [1,2,3] , но [3,1] не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2] является подотрезком массива [1,2,3] , а [1,3] не является. Несложно заметить, что у массива длины n ровно \( {n(n+1) \over 2}\) подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

У массива [1] есть ровно один подотрезок и он является возрастающим.
У массива [2] есть ровно один подотрезок и он является возрастающим.
У массива [3] есть ровно один подотрезок и он является возрастающим.
У массива [1,2] есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
У массива [1,3] есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
У массива [3,2] есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3] и [2] ) являются возрастающими.
У массива [1,3,2] есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12

Дерево отрезков, RSQ, RMQ Дерево Фенвика Динамическое программирование Динамическое программирование: один параметр

✓ 1✗ 1—Войти и решать

Конфеты детям#38503

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.

Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.

Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.

Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.

Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 4 12	2	Любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету, будет четвёртый человек.
2	5 3 4 10	3	Сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте.
3	10 5 5 1	10	Только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты.
4	5 4 5 6	-1	Лена ошиблась и такой ситуации быть не могло.

Арифметические алгоритмы (Теория чисел)Остатки

✓ 2✗ 1—Войти и решать

LinkedList's Bizarre Adventure#38501

В двусвязном списке, он же LinkedList, каждый элемент может быть связан максимум с двумя другими элементами — с предыдущим элементом (если он есть) и со следующим элементом (если он есть).

Билли и Рикардо проходят стажировку в компании FlexDex в группе поддержки внутреннего анонимного форума с возможностью деанонимизации. Для представления последовательных сообщений в теме необходимо использовать список, где элементами будут являться эти сообщения, и два товарища решили написать свою быструю реализацию двусвязного списка FlexList.

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

Если представить каждое сообщение как вершину графа, а связи между сообщениями как ребра графа, то гарантируется, что этот граф будет неориентированным, связным и ацикличным.

Говорится, что граф является корректным графом, если в этом графе у каждой вершины не более двух вершин, связанных с ней ребром. Изначально же FlexList связи между сообщениями могут выглядеть в виде любого связного ацикличного графа, не обязательно корректного.

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

Это выглядит так — сначала Билли проверяет, что граф корректный. Если это не так, то он выбирает и удаляет некоторый лист (вершина, у которой есть ровно одна связь с другими вершинами), и отдает граф Рикардо, затем Рикардо делает то же самое и отдает граф Билли, и так продолжается до тех пор, пока кто-то не получит от товарища корректный граф. Как только один из двух друзей получает такой граф, то тут же показывает его тимлиду, с надеждой на похвалу и повышение в должности.

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

Входные данные
В первой строке содержится одно целое число n (1 ≤ n ≤ 300000) — число сообщений в примере тимлида. Следующие n−1 строк задают связи между сообщениями. Каждая из них содержит два целых числа a_i и b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), которые показывают, что сообщения с номерами a_i и b_i связаны.

Выходные данные
Выведите "Billy" (без кавычек), если первым попадет к тимлиду Билли, иначе выведите "Ricardo" (без кавычек).

Примечание
В первом примере Билли первым ходом может удалить одну из вершин с номерами 2, 4 или 5, так как они являются листьями. Он не будет удалять вершину с номером 4 или 5, так как в таком случае он передаст Рикардо корректный граф и проиграет. Значит, он удалит вершину 2. В свою очередь, Рикардо может удалить вершины 1, 4 или 5, и, в любом случае, Билли получит от него корректный граф.

Во втором примере у Билли сразу есть корректный граф.

В третьем примере можно показать, что вне зависимости от ходов Билли, Рикардо получит корректный граф первым.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 1 3 3 4 3 5	Billy
2	7 1 2 2 3 3 4 4 5 5 6 6 7	Billy
3	6 1 2 1 3 1 4 1 5 1 6	Ricardo

Древовидные структуры данных Игры и выигрышные стратегии Простые игры

✓ 2✗ 81 400средняяВойти и решать

Чет-нечет#38474

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Входные данные
Одно целое число N (1 ≤ N ≤ 10¹⁰⁰).

Выходные данные
Выведите одно целое число - N-й элемент последовательности.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	4	5

"Длинная" арифметика Бинарный поиск по ответу

✓ 19✗ 1021 000средняяВойти и решать

Взвешивание камней#38473

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

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

Входные данные
Первая строка содержит целое число N (1 N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк - по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

Алгоритмы сортировки Дерево отрезков, RSQ, RMQ Жадный алгоритм

✓ 1✗ 121 100средняяВойти и решать

Agar.io#38466

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

Бинарный поиск Бинарный поиск по ответу

✓ 68✗ 266900средняяВойти и решать

Таблица#38370

В новой математической игре для одного игрока «Таблица чисел» используется таблица размером n строк на m столбцов, заполненная целыми числами. За один ход игрок выбирает одну из строк или один из столбцов и меняет знак на противоположный у всех чисел этой строки или столбца.

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

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

Входные данные
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n, m ≤ 100). Каждая из последующих n строк содержит по m целых чисел a_i,j (|a_i,j| ≤ 100).

Выходные данные
В первой строке выходного файла выведите k — число ходов, которые необходимо выполнить, или «-1», если цели игры добиться невозможно. В первом случае в последующих k строках выведите описание этих ходов.

Описание каждого хода должно быть выведено в отдельной строке, которые должны содержать: тип хода («R» — на этом ходе выбирается строка или «C» — на этом ходе выбирается столбец) и номер соответствующей строки или столбца. Строки и столбцы нумеруются натуральными числами начиная с единицы, строки нумеруются сверху вниз, а столбцы — слева направо.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 -1 -3 1 -2	1 C 2
2	3 2 -1 -1 -1 -1 -1 -1	3 R 1 R 2 R 3

Жадный алгоритм Задачи на моделирование

✓ 7✗ 8800средняяВойти и решать

Схема игры#38369

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

Например, схема игры 5-3-2 означает, что в команде пять защитников, три полузащитника и два нападающих. В соответствии с современными представлениями на схему игры накладываются следующие ограничения: должно быть не менее одного и не более пяти защитников, не менее одного и не более пяти полузащитников и не более трех нападающих. Отметим, что нападающих может в команде и не быть совсем. Будем рассматривать только такие схемы.

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

Будем также считать, что игрок в некоторый момент времени находится в линии полузащиты, если он находится на расстоянии не более 20 метров от центральной линии. Соответственно, игрок находится в линии защиты, если он находится не более чем в 40 метрах от «своей» лицевой линии, и в линии нападения, если находится не более чем в 40 метрах от «чужой» лицевой линии.

Например, в ситуации, изображенной на рисунке, в линии защиты находятся четыре игрока, в линии полузащиты — три, в линии нападения — также три.

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

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

Входные данные
Входной файл содержит десять строк, содержащих по два целых числа x_i и y_i каждая, — координаты каждого из игроков команды (0 ≤ x_i ≤ 120, x_i ≠ 40, x_i ≠ 80, 0 ≤ y_i ≤ 80).

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

Примеры

№	Входные данные	Выходные данные
1	97 0 13 18 2 6 119 11 42 21 72 80 75 78 106 45 22 67 28 47	9 2-5-3 3-5-2 3-4-3 4-5-1 4-4-2 4-3-3 5-4-1 5-3-2 5-2-3

Перебор Разбиения

✓ 10✗ 4600лёгкаяВойти и решать

Определите победителя#38350

Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по 18 карт.

Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну карточку по следующим правилам. Карточку с цифрой 5 можно выкладывать на стол в любой момент. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной карточке (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если игрок может выложить хоть какую-то карточку, он обязан делать ход. Если ни одну карточку игрок выложить не может, он пропускает ход.

Выигрывает тот, кто первым выложит все свои карточки на стол.

Напишите программу, которая по информации о том, кому какие карточки достались, определяет, кто выиграет при оптимальной игре обоих игроков.

Входные данные
Во входном файле записаны 18 пар чисел, описывающих карточки, которые достались первому игроку. Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9). Второму игроку, соответственно, достались все остальные карточки.

Выходные данные
В выходной файл выведите одно число (1 или 2) — номер игрока, который выиграет при оптимальной игре обоих игроков.

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9	1

Динамическое программирование на таблицах Простые игры

✓ 1✗ 1—Войти и решать

Рассадка участников#38335

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

Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

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

Если задача не имеет решения, необходимо вывести одно число 0.

Числа можно выводить как в отдельных строках, так и в одной строке через пробел. Если есть несколько вариантов рассадки, то необходимо вывести любой из них (но только один).

Примеры

№	Входные данные	Выходные данные
1	4 1005 1005 5 2005	1005 5 1005 2005
2	4 1005 1005 2005 1005	0

Алгоритмы сортировки Задачи на моделирование

✓ 26✗ 79800средняяВойти и решать

Простой квадрат#38334

У Пети имеется игровое поле размером 3x3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

Входные данные
Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

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

Ответ можно выводить не в виде числа, а в виде строки или в виде последовательности отдельных цифр (но не разделяя их пробелами).

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 5 6 7 8 9	987456321

Перебор Простые задачи на перебор

✓ 9✗ 231 000средняяВойти и решать

Квас#38313

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

Планируется построить всего один завод в каком-нибудь городе, и развозить продукцию по остальным городам. Перевозка одной бочки в соседний город стоит один тугрик (местная валюта).

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

Входные данные
Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 5 3 10	3
2	6 4 4 1 5 1 3	2	На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком. Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 52 + 32 (в 4-й и 6-й) + 13 (в 5-й см. рисунок). Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 32 + 42 + 43 = 28 тугриков.

Обход в ширину Перебор

✓ 59✗ 108900средняяВойти и решать

Пересадки#38310

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

Входные данные
Вводятся четыре числа, не превосходящие 100, задающие номера конечных остановок. Сначала для первого, потом второго автобуса (см. примеры и рисунок).

Выходные данные
Ваша программа должна выводить одно число – искомое количество остановок.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 6 4 2	2	первый автобус ходит с 3-й остановки по 6-ю и обратно, а второй с 2-й по 4-ю и обратно. Пересесть с одного автобуса на другой можно на 3-й и 4-й остановках. Их две.
2	3 1 5 10	0	автобусы не имеют общих остановок.

Отрезки Пересечение множеств

✓ 235✗ 607400лёгкаяВойти и решать

Выбор гурмана#38303

Гурман Яблочков работает редактором известного гастрономического издания. Он разъезжает по всему миру, дегустируя новые изыски именитых шеф-поваров самых фешенебельных ресторанов высокой кухни. У Яблочкова есть свой фирменный способ ревью: в каждом заведении Яблочков заказывает два набора блюд в разные дни. Все заказанные блюда разные, так как Яблочков не любит есть одно и то же. Для каждой пары блюд из разных наборов он точно помнит, какое из них лучше по его ощущениям, или что они одинаковы по вкусовым качествам. Затем гурман оценивает каждое блюдо положительным целым числом.

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

Гурман в первый день дегустировал набор из n блюд, во второй день набор из m блюд. Он составил таблицу ощущений a размером nm, в которой описал свои впечатления. Если по мнению эксперта блюдо i из первого набора лучше блюда j из второго набора, то a_ij равно « > », в противоположном случае a_ij равно « < ». Блюда также могут быть равны по уровню, тогда a_ij равно « = ».

Теперь Яблочков хочет, чтобы вы помогли ему оценить каждое блюдо в наборах целым положительным числом. Так как Яблочков очень строгий дегустатор, то постарается оценить блюда так, чтобы максимальная из оценок была как можно меньше. В то же время Яблочков очень справедливый, поэтому никогда не оценивает блюда так, чтобы это шло вразрез с его ощущениями. Другими словами, если a_ij равно « < », то оценка блюда i из первого набора должна быть меньше оценки блюда j из второго набора, если a_ij равно « > », то должна быть больше, а если a_ij равно « = », то должна совпадать.

Помогите Яблочкову выставить оценки каждому блюду из обоих наборов так, чтобы это согласовывалось с его ощущениями, или определите, что это невозможно.

Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количества блюд в каждый из двух дней.

Каждая из следующих n строк содержит строку из m символов. j-й символ в i-й строке задаёт значение aij. Все строки состоят только из символов « < », « > » и « = ».

Выходные данные
В первой строке выведите « Yes » (без кавычек), если можно сделать корректную оценку всем блюдам и « No » (без кавычек), если иначе.

В случае, если сделать корректную оценку можно, во второй строке выведите n целых чисел — оценки блюд первого набора, а в третьей строке m целых чисел — оценки блюд второго набора.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 4 >>>> >>>> >>>>	Yes 2 2 2 1 1 1 1	Все блюда первого дня лучше всех блюд второго дня. Значит, самой высокой оценкой будет 2 для всех блюд первого дня.
2	3 3 >>> <<< >>>	Yes 3 1 3 2 2 2
3	3 2 == =< ==	No	Таблица противоречива: нет ни одного набора оценок, который удовлетворял бы ей.

Динамическое программирование на графах Обход в глубину Система непересекающихся множеств

✓ 4✗ 71 000средняяВойти и решать

Сломанный робот#38297

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x₀, y₀). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.

Примеры

№	Входные данные	Выходные данные
1	2 1	5 DLULD

Замечание
Вы не обязаны выводить кратчайший маршрут. Например, в приведенном примере кратчайший
маршрут состоит из 3 передвижений: влево, вниз, влево.
Иллюстрация к тесту из примера:

Конструктив Элементарная геометрия

✓ 95✗ 236800средняяВойти и решать

Словарь#38196

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

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.

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

Примеры

№	Входные данные	Выходные данные
1	whatcanido 6 a an can do i what	what can i do

Бинарный поиск в массиве Динамическое программирование: один параметр

✓ 7✗ 17800средняяВойти и решать

Напитки и стаканы - 2#38157

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

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

Коля хочет своеобразно оценить сколько способов есть разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы. Так как число способов может быть довольно большим, Коля хочет знать его по модулю 1 000 000 007. Помогите Коле посчитать это число.

Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число стаканов и бутылок напитков в i-ом наборе (1≤n_i≤10⁵).
Во второй строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
В третьей строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
Гарантируется, что сумма n_i по всем тестовым наборам не превосходит 3⋅10⁵.

Выходные данные
Для каждого тестового набора выведите одно число - число способов разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы, взятое по модулю 1 000 000 007.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 1 1 1 2 1 5 1 2 3 4 5 1 2 3 4 5 3 2 2 2 2 1 2	0 1 6	В первом тестовом наборе второй напиток не помещается ни в один стакан, поэтому ответ будет ноль. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе любой напиток можно налить в любой стакан.

Использование сортировки Комбинаторика

✓ 0✗ 41 300средняяВойти и решать

Напитки и стаканы - 1#38154

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

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

Коля хочет своеобразно оценить сколько способов есть разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы. Так как число способов может быть довольно большим, Коля хочет знать его по модулю 1 000 000 007. Помогите Коле посчитать это число.
Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число бутылок напитков и стаканов в i-ом наборе (1≤n_i≤10⁵).
Во второй строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
В третьей строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
Гарантируется, что сумма ni по всем тестовым наборам не превосходит 3⋅10⁵.

Выходные данные
Для каждого тестового набора выведите одно число - число способов разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы, взятое по модулю 1 000 000 007.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 1 1 1 2 1 5 1 2 3 4 5 1 2 3 4 5 3 2 2 2 2 1 2	6 1 0	В первом тестовом наборе любой напиток помещается в любой стакан. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе ни один напиток не поместится во второй стакан, поэтому ответ будет ноль

Жадный алгоритм Использование сортировки

✓ 12✗ 11800средняяВойти и решать