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

Устранение массива#49028

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).
Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

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

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

Формат выходных данных
Выведите \(T\) целых чисел, каждое в своей строке — ответы на задачу для каждого набора входных данных в том порядке, в котором оны даны во вводе.

Задачи на моделирование реализация

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

Система контроля версий - 2#49027

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид дерева изменений состояния проекта.

Корень дерева — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.
Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.
Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.
Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину дерева. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.
Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример дерева можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершины номер \(8\) и \(9\) появляются после команды rebase между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально дерево состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

<<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда в файл были внесены одинаковые изменения.

Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.
<<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<FAILURE: no changes>>, при этом новая вершина не создается.
<<reset <номер>>> — переместить HEAD на вершину с данным номером.

Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.
<<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>, аналолгично операции reset.
<<rebase <имя ветки>>> — перенести изменения из ветки с указанным именем в текущую ветку. При этом находится ближайший общий предок двух веток и все коммиты в укзанной ветке после общего предка (то есть все вершины, которых нет в текущей ветке) копируются и вставляются в текущую ветку после HEAD в исходном порядке. HEAD при этом перемещается на последнюю из скопированных вершин, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<FAILURE: uncommitted changes>>.

Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<FAILURE: conflicts detected>>.

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

Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после rebase двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции rebase.

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<SUCCESS>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных, которые вам предстоит обработать (\(1 \le T \le 20\)). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<SUCCESS <HEAD>>>, либо формату <<FAILURE: <сообщение об ошибке>>>.

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

графы реализация

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

Генераторы квадратов#48941

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

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

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

Вывод формулы Перебор реализация

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

Следующий больший элемент#45812

Следующий больший элемент некоторого элемента x в массиве - это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива nums1 и nums2 с индексами 0, где nums1 является подмножеством nums2.

Для каждого 0 <= i < nums1.length найдите индекс j такой, что nums1[i] == nums2[j] и определите следующий больший элемент nums2[j] в nums2. Если следующего большего элемента нет, то ответом на этот запрос будет -1.

Выведите n чисел таких, что каждое из них будет являться следующим большим элементом, как описано выше.

Входные данные
В первой строке записано натуральное число n - размер массива nums1. Вторая строка содержит n чисел - элементы массива nums1. В третьей строке записано натуральное число m - размер массива nums2. Четвертая строка содержит m чисел - элементы массива nums2.

Ограничения на входные данные

1 <= nums1.length <= nums2.length <= 50000
0 <= nums1[i], nums2[i] <= 10⁹
Все числа в массивах nums1 и nums2 уникальны.
Все числа массива nums1 содержатся в nums2.

a.length - размер массива a

Выходные данные
Выведите ответ на задачу.

Примеры

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

реализация Стек

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

Максимальная ширина#44960

У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p₁, p₂, ..., pm, где 1<=p₁<p₂<…<p_m<=n, называется хорошей , если s_pi=t_i для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.

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

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

Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.

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

Гарантируется, что существует хотя бы одна хорошая последовательность индексов.

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

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

Примечание

В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.

Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.

В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.

В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.

Примеры

№	Входные данные	Выходные данные
1	5 3 abbbc abc	3
2	5 2 aaaaa aa	4
3	5 5 abcdf abcdf	1
4	2 2 ab ab	1

Алгоритмы на строках реализация

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

2022 - 2#44506

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных четверок индексов (индексы внутри одной четверки могут совпадать) таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует четверок 1 <= i,j,k,h <= n, для которых выполняется a_i+a_j+a_k+a_h=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.

Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - количество элементов массива. Во второй строке заданы n целых чисел a₁, a₂, ..., a_n (0 <= a_i<= 2022) - элементы массива Эвелины.

Выходные данные
Так как ответ может быть слишком большим, вам необходимо вывести остаток от деления количества подходящих четверок на 1000000007 (10⁹+7).

Примечание

В первом примере не существует четверок с суммой 2022.

Во втором подходят четверки (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2, 1, 2, 1), (2,2,1,1).

В третьем примере подходят все 24 четверки попарно различных индексов. Например, (1,2,3,4) или (4,1,3,2).

Примеры

№	Входные данные	Выходные данные
1	4 1 1 1 1	0
2	2 500 511	6
3	4 129 45 1000 848	24

реализация

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

Морской бой#44312

В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.
В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29.
Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед!
Подбейте все корабли, используя минимальное число торпед.

Входные данные
В первой строке содержится целое число N — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число M — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что 1 ≤ N + M ≤ 10⁵, N > 0 и M > 0.
Следующие N строк содержат по одному целому числу l_i — начальные координаты кораблей,двигающихся влево. Следующие M строк содержат по одному целому числу ri — начальные координаты кораблей, двигающихся вправо. Координаты l_i идут в порядке возрастания, координаты ri также заданы в порядке возрастания. Гарантируется, что все начальные координаты l_i и r_i чётные, различные и не превосходят по модулю 10⁹.
Выходные данные
Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом i-я строка должна содержать два целых числа t_i — время нанесения удара i-й торпедой и x_i — координату удара i-й торпедой. Все t_i и xi должны быть целыми, 0 ≤ t_i ≤ 10¹⁸ , −10¹⁸ ≤ x_i ≤ 10¹⁸. В один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени.

Примеры

№	Входные данные	Выходные данные
1	2 1 10 30 20	0 10 5 25

Замечание
В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны l₁ = 10 и l₂ = 30, а начальная координата корабля, двигающегося вправо, равна r₁ = 20. В момент времени t₁ = 5 в одной точке x₁ = 25 окажутся два корабля — двигающийся влево из точки 20 и двигающийся вправо из точки 30. Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени t₂ = 2 в точке x₂ = 8.

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

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

Минимальное максимальное#43135

Алексей Юрьевич и Михаил Леонидович отправились на поезде в Троицк. По дороге к ним подсели вахтовик и дембель. После знакомства и небольших историй о себе вахтовик и дембель решили устроить Алексею Юрьевичу и Михаилу Леонидовичу тест «на мужика»: нужно решить непростую задачку по программированию.
Помогите Алексею Юрьевичу и Михаилу Леонидовичу пройти тест «на мужика».
Задан массив целых чисел a₁,a₂,...,a_n.
Стоимостью подотрезка массива 1 <= l <= r <= n назовем величину f(l,r) = sum(l,r) − xor(l,r), где sum(l,r) = a_l +a_l+1+...+a_r, а xor(l,r) = a_l ⊕a_l+1 ⊕...⊕a_r (⊕ здесь обозначает операцию XOR, побитовое исключающее «ИЛИ» чисел, подробнее в разделе «Замечание»).
Требуется найти подотрезок заданного массива с максимальным значением f(l,r). Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением r − l +1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 10⁴) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 10⁵) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a₁,a₂,...,a_n (0 <= a_i <= 10⁹) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 · 10⁵.
Выходные данные
Для каждого набора входных данных выведите два числа 1 <= l <= r <= n таких, что значение f(l,r) максимально по всем подотрезкам массива a, а длина r −l +1 минимальна. Если существует несколько правильных ответов, выведите любой из них.

Примеры

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

Замечание
Операция XOR двух чисел a и b — это битовая операция, которая применяется независимо к каждой паре соответствующих битов a и b. Эта операция представляет собой сложение по модулю 2. Вот её таблица истинности для пары битов:

a	b	a⊕b
0	0	0
0	1	1
1	0	1
1	1	0

В первом наборе входных данных f(1,1) = 1 − 1 = 0.
Во втором наборе входных данных f(2,2) = 10 − 10 = 0. Заметим, что f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, но нам среди максимальных значений f(l,r) нужно найти подотрезок с минимальной длиной.
В четвертом наборе входных данных f(2,3) = (12+8) − (12 ⊕ 8) = 16.
В пятом наборе входных данных есть два правильных ответа, так как f(2,3) = f(3,4) и их длины равны.

математика реализация

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

K-mex#43131

Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•   + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•   - x — удалить число x из множества. Гарантируется, что это число там есть,
•   ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 10⁵) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 10¹⁸), если запрос удаления, то - x (1 <= x <= 10¹⁸), если же запрос поиска, то ? k (1 <= k <= 10¹⁸). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.

Примеры

№	Входные данные	Выходные данные
1	18 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 100000000 ? 100000000 - 4 ? 1 ? 2	3 6 3 3 10 3 200000000 3 4

Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6

реализация Хеш

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

Копейский рок#43129

Мало кто знает, но у Данилы Багрова и Татарина есть ещё один брат, неизвестный широкой публике. Проживает он тихо, мирно в Копейске, вдали от столичной суеты и назойливых папарацци.
Однажды Данила Багров и Татарин решили навестить своего брата. Приехав к нему домой в Копейск, Данила обнаружил в шкафу обширную коллекцию дисков различных рок-групп. На полках лежали диски «Nautilus Pompilius», «Би-2», «АукцЫона», «Смысловых галлюцинаций», «Агаты Кристи» и многих других. Однако Даниле не понравилось, как эти диски были разложены на полках.
Шкаф с полками можно представить в виде прямоугольника n×m, где в каждой клетке лежит один диск. Каждый диск описывается одним числом — некоторым номером группы, которая записала этот диск. Будем считать, что если два диска имеют одинаковое число, то их записала одна и та же группа, а если разные — то их записали разные группы.
Данила хочет добиться того, чтобы в каждом столбце все диски были записаны разными группами. Для этого он может сколько угодно раз переставлять диски произвольным образом на любой полке (то есть внутри любой строки), однако, запрещено менять местами диски с разных полок.
Помогите Даниле и скажите, можно ли такими действиями добиться того, чтобы в каждом столбце все диски были записаны разными группами.
Входных данные
В первой строке через пробел заданы два целых числа n и m — размеры шкафа (1 <= n,m <= 100).
В следующих n строках через пробел записаны m целых чисел a_i,j — номер группы, которая записала диск, лежащий на i-й полке в j-м столбце (1<= a_i,j <=10⁹).
Выходные данные
В первой строке выведите Impossible, если Данила не может расставить всё так, чтобы в каждом столбце диски были записаны разными группами, и Possible, если такая расстановка возможна.
В случае, если Данила может добиться желаемого, выведите финальную расстановку дисков в шкафу. Если таких расстановок несколько, выведите любую из них.

Примеры

№	Входные данные	Выходные данные
1	3 4 1 2 2 3 3 2 1 4 2 4 1 3	Possible 3 2 1 2 1 3 2 4 2 1 4 3
2	3 3 1 1 1 1 1 1 1 1 1	Impossible

математика реализация

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

Лес#42971

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).
Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов. Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 10⁹.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.
Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Примеры

№	Входные данные	Выходные данные
1	1 1 2 3 3	13

Замечание
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.

Задачи на моделирование реализация

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

Количество чисел на диапазоне#40066

Вам даны N целых чисел A₁, ..., A_N.
На каждый из Q запросов, заданных в формате L R X, выведите количество элементов среди A_L, ..., A_R, значения которых равны X.

Входные данные
В первой строке задано целое число N (1 <= N <= 2·10⁵).
Вторая строка содержит N целых чисел A_i (1 <= A_i <= N, 1 <= i <= N).
В третьей строке задано одно целое число Q (1 <= Q <= 2·10⁵).
Каждая из следующих Q строк содержит три целых числа L, R, X (1 <= L <= R <= N, 1 <= X <= N).

Выходные данные
Выведите на экран Q строк, i-я строка содержит ответ на i-й запрос.

Примеры

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

Префиксные суммы(минимумы, ...)реализация

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

Космолёт#39627

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:

звезда Беллатрикс (250 световых лет от Земли)
звезда Бетельгейзе (643 световых года от Земли)
парная звёздная система Ригель (773 световых года от Земли)

Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

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

Примеры

№	Входные данные	Выходные данные
1	3 10 10 10 20 20 20 30 30 30	3 51.962 1 2 3
2	5 20 0 0 10 0 0 40 0 0 30 0 0 50 0 0	4 40.000 2 1 4 3

графы кратчайшие пути реализация

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

Сын маминой подруги#39500

Вася уже в десятом классе. После месяца ежедневных заруб в доту со своими товарищами, он начал замечать, что его оценки начали проседать. Исправлять их он, конечно же не собирается, но есть один нюанс...
Вместе с Васей в классе учится сын маминой подруги — Петя. Вася очень не любит его, потому что мама Васи дружит с мамой Пети и знает про него почти всё. В конце триместра у васиной мамы есть традиция садиться и сравнивать оценки Васи с оценками Пети. За каждый случай, когда у Васи оценка ниже, чем у Пети, мама выдаёт ему наряд вне очереди! — мыть весь день посуду, пропылесосить во всём доме, помыть окна или отвести/забрать младшую сестру из детского сада.
Конечно же, эта ситуация Васе не очень нравится, потому что в среднем Вася умнее Пети. Вася хочет минимизировать количество штрафных нарядов, поэтому он собирается перемешать оценки.
Помимо оценок в журнале встречается метка n. Она означает, что ученика на уроке не было. Если кого-то из учеников не было на уроке, то мама Васи не может сравнить успехи своего сына и сына своей подруги, поэтому штрафной наряд выписан быть не может
Помогите Васе перемешать свои оценки и n-ки так, чтобы получить как можно меньше штрафных нарядов. Если существует несколько решений, выведите любое.
В школе N различных предметов, и по каждому из них Вася должен перемешать оценки.
В каждом тесте первое число N — это количество предметов, за которые получены оценки в этом триместре. В следующих 2N строках находятся N блоков по 2 строки. В каждом блоке в первой строке находятся оценки Васи, а во второй — оценки Пети. Для каждого блока в новой строчке нужно вывести такую перестановку номеров оценок и меток n, что a_iозначает, что Васина оценка под номером i должна занять позицию a_i.
В первом тесте N = 30. Оценка за этот тест: 30 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 1 балл. Проверка осуществляется в режиме online (результат виден сразу).
Во втором тесте N = 35. Оценка за этот тест: 70 баллов. За каждый предмет, за который получено больше штрафных нарядов, чем могло бы быть, снимается 2 балла. Во время тура проверяется, что по каждому предмету сдана корректная перестановка. Проверка правильности ответа осуществляется в режиме offline (результат виден после окончания тура).

Примеры

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

В первом примере Вася получит 4 наряда вне очереди. Во втором примере ничего никуда переставлять не надо, потому что на единственном уроке, на котором присутствовали оба ученика, они получили по 4 балла. В третьем примере Вася переставит оценки вот так: 4, 2, 1, 3 и получит один наряд вне очереди

жадные алгоритмы реализация

—Войти и решать

Пирамида#38837

Великий фараон Флатландии недавно взошёл на престол и озаботился вопросом строительства пирамиды для себя.
Флатландия — двумерная страна, у неё есть только длина и высота. Для строительства пирамиды был выделен участок длиной в N стандартных блоков. Каждый единичный отрезок был обследована геологами, которые выяснили количество стандартных блоков 1 на 1, которые могут быть уложены в столбик на эту клетку без угрозы проседания грунта.
Пирамидой называется фигура, состоящая из блоков 1 на 1, такая, что каждый горизонтальный слой представляет собой непрерывный отрезок. Под каждым блоком должен находится блок предыдущего слоя или земля (в нижнем слое). Количество блоков в каждом столбце не должно превосходить грузоподъёмности клетки, на которой находится этот столбец.
Фараон хочет, чтобы его пирамида состояла из как можно большего числа блоков. Помогите ему определить это число.

Формат входных данных
В первой строке входных данных задано целое число N (1 ≤ N ≤ 300000) — длина участка,
выделенного для строительства пирамиды.
Во второй строке задано N целых чисел Wi (0 ≤ Wi ≤ 10⁹) — грузоподъемности отрезков
единичной длины.

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

Примеры

№	Входные данные	Выходные данные
1	6 7 0 1 3 2 3	8

реализация

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

Страны мира#38782

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

Входные данные
Программа получает на вход количество стран N. Далее идет N строк словаря: каждая строка начинается с названия страны, затем идут названия городов этой страны. В следующей строке записано число M, далее идут M слов - названия M городов. Гарантируертся, что такой город есть в словаре.

Выходные данные
Для каждого города выведите название страны, в которой он находится.

Пример

№	Входные данные	Выходные данные
1	2 Russia Moscow Petersburg Novgorod Kaluga Ukraine Kiev Donetsk Odessa 3 Odessa Moscow Novgorod	Ukraine Russia Russia

реализация Словари

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

Джерримендеринг#38777

Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.

Входные данные
Первая строка входных данных содержит целое число N (3 <= N <= 10⁵ ) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 < |ai | <= 10⁴ ). Если ai > 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai < 0, то в i-м доме проживает |ai | избирателей, голосующих против кандидата от партии X.

Выходные данные
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести в одной строке три целых положительных числа N1, N2, N3, N1 + N2 + N3 = N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 -3 -5 3 -4 2 5 -3	4 1 2	На улице расположены 7 домов, избиратели в них распределены так: (−3, −5, 3, −4, 2, 5, −3). Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: (−3, −5, 3, −4). В этом округе за X голосует 3 избирателя, против — 12 избирателей и X разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за X, в этом округе X выиграет. В третьем округе два дома: (5, −3), и в этом округе X тоже выиграет. Итого X выигрывает в двух округах.

Префиксные суммы(минимумы, ...)реализация

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

Кольцевые гонки#38690

Участники кольцевых гонок на одноколесных велосипедах нумеруются числами от 1 до N. Им предстоит проехать K кругов и победителем является тот, кто проехал их раньше всех. Участники стартуют одновременно с некоторой линии, которая называется конец круга. Каждый раз, когда участник пересекает эту линию, его номер фиксируется автоматической системой с высокой точностью (то есть два участника не могут пересечь эту линию одновременно). После прохождения K кругов эта же линия является финишной прямой. К сожалению, некоторые участники сходят с дистанции и проезжают меньшее количество кругов.
Организаторы соревнования забыли число K и стесняются спросить его у участников. Помогите организаторам определить победителя соревнования, используя только записи с системы фиксации. Гарантируется, что хотя бы один из участников преодолел необходимые K кругов и никто из участников не проехал более K кругов. Первая фиксация номера участника происходит после
прохождения первого круга.

Формат входных данных
В первой строке задаются целые числа N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10000) — количество участников соревнования и записей с системы фиксации соответственно. Во второй строке задается M целых чисел от 1 до N – номера участников в том порядке, как
они фиксировались системой.

Формат выходных данных
Выведите одно число — номер победителя

Примеры

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

Алгоритмы обработки реализация

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

Раскраска Тюбика#38654

Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с H строками и W столбцами. Все клетки сетки изначально выкрашены в белый цвет. Тюбик попросил Незнайку закрасить N из этих ячеек в черный цвет. I-я (1<=i<=N) ячейка, которую закрасил Незнайка, является ячейкой в a_i-й строке и b_i -м столбце. Для каждого целого числа j (0<=j<=9), определите сколько в сетке подпрямоугольников размером 3×3 содержит ровно j черных ячеек после того, как Незнайка закрасил N ячеек?

Входные данные
В первой строке заданы 3 целых числа: H, W (3<=H,W<=10⁹) и N (0<=N<=min(10⁵,H×W)). Далее идут N строк по 2 числа в каждом a_i(1<=a_i<=H) и b_i (1<=b_i<=W), 1<=i<=N, (a_i,b_i)≠(a_j,b_j), i ≠ j.

Выходные данные
Выведите 10 строк. В (j + 1)-й (0<=j<=9) строке должно быть указано количество подпрямоугольников размером 3 × 3 сетки, содержащей ровно j черных ячеек.

Примеры

№	Входные данные	Выходные данные
1	4 5 8 1 1 1 4 1 5 2 3 3 1 3 2 3 4 4 4	0 0 0 2 4 0 0 0 0 0
2	10 10 20 1 1 1 4 1 9 2 5 3 10 4 2 4 7 5 9 6 4 6 6 6 7 7 1 7 3 7 7 8 1 8 5 8 10 9 2 10 4 10 9	4 26 22 10 2 0 0 0 0 0
3	1000000000 1000000000 0	999999996000000004 0 0 0 0 0 0 0 0 0

Задачи на моделирование реализация

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

Дипломы в папках#38547

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

Иван хочет принести в приемную комиссию выбранного вуза папку, в которой находится диплом Московской олимпиады по программированию (такой диплом у Ивана ровно один). Для того чтобы понять, что в данной папке нужного диплома нет, Ивану нужно просмотреть все дипломы из этой папки. Чтобы открыть одну папку Ивану нужно потратить одну секунду, просмотр одного диплома занимает у него также одну секунду, и он может мгновенно переходить к следующей папке после окончания просмотра предыдущей. Порядок просмотра папок Иван может выбирать. То, что в пустых папках диплом можно не искать, Ивану очевидно.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

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

Вывод формулы Жадный алгоритм реализация

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