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

Регистрация на web-сайте#53642

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

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

Ограничения
Тестовые примеры, на которых проверяется решение, удовлетворяют следующим ограничениям.

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

Номер банковской карточки натуральное число, состоящее не менее, чем из 5, и не более, чем из 15 цифр.

Дата рождениязаписывается в формате ДД.ММ.ГГГГ (день и месяц вводятся ровно двумя цифрами каждый, год - ровно четырьмя)

Задача на реализацию

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

T2005#53605

Клавиатура сотового телефона выглядит так:

1 — пробел	2 — abc	3 — def
4 — ghi	5 — jkl	6 — mno
7 — pqrs	8 — tuv	9 — wxyz

Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.

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

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

Примечание: в тексте используются только маленькие латинские буквы и символ пробел.

Входные данные
Сначала на вход программы поступает число N — количество слов в словаре (2≤N≤100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.

Далее вводится число M — количество нажатий клавиш (1≤M≤20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".

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

Примечание:

2
a
z
2
5 1

Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел

Бор Задача на реализацию Конечные автоматы

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

Магнитные игры#51138

У Вовы есть любимый магнит. Вове очень нравится играть с ним на большой поляне, которую можно представить в виде прямоугольника \(n\) на \(m\) клеток.

Однажды он пришел играть на поляну с магнитом и потерял его в одной из клеток. Вова очень расстроился, но нашел решение — в каждую клетку поляны он положил компас, стрелка которого может принимать 8 положений: вверх, вверх-вправо, вправо, вниз-вправо, вниз, вниз-влево, влево и вверх-влево. Каждому положению стрелки соответствует его номер:

Стрелки принимают направление, близкое к направлению на магнит: если магнит лежит строго по диагонали от компаса, то его стрелка примет диагональное положение, иначе — более близкое к направлению на магнит из вертикального и горизонтального. Стрелка компаса в клетке с магнитом может быть направлена куда угодно.

Рисунок для примера из входных данных, стрелки всех компасов направлены на магнит.

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

Рисунок для примера из входных данных с учетом аномалии.

Теперь Вова не знает, как ему найти свой магнит, и просит помощи у вас.

Формат входных данных
В первой строке входных данных записаны два целых числа через пробел \(n\) и \(m\) — размеры поляны (\(2 \le n, m \le 1500, nm \ge 6\)).

В следующих \(n\) строках описываются компасы на поляне.

В \(i\)-й строке записаны \(m\) целых чисел \(a_{i,j}\) (\(1 \le a_{i,j} \le 8\)), \(j\)-е число в \(i\)-й строке обозначает направление стрелки компаса в \(j\)-й клетке \(i\)-й строки.

Формат выходных данных

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

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

Замечание

В данном тесте магнит лежит в клетке \((2, 1)\), инвертируется горизонталь номер \(3\) и вертикаль номер \(3\).

Задача на реализацию

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

Преобразование строки#50990

Даны две строки \(S\) и \(T\) из строчных букв английского алфавита.

Посмотрим на следующий процесс. Рассмотрим не более одного раза каждый символ, хотя бы где-то входящий в первую строку. После чего, для рассматриваемого символа \(x\) определим другой символ \(p(x) \neq x\) и заменим некоторые вхождения \(x\) в \(S\) на \(p(x)\). Определите, возможно ли в ходе такого процесса получить из строки \(S\) строку \(T\). При этом разные символы можно заменять на один и тот же символ или на символ, который заменяться не будет.

Например, пусть \(S =\) <<aabab>>, \(T =\) <<abbbc>>. Из \(S\) можно получить \(T\), если выбрать p(‘a’) = ‘b’, p(‘b’) = ‘c’ и заменить второе и третье вхождение ‘a’ на p(‘a’), второе вхождение ‘b’ на p(‘b’).

А если \(S =\) <<aabaс>>, \(T =\) <<bbbbb>>, то все вхождения ’a’ и ’c’ были заменены на ’b’.

Формат входных данных
В первой строке вам дано число \(n\) \((1 \leqslant n \leqslant 200\,000)\). Во второй строке задана \(S\). В третьей строке задана \(T\). Обе строки имеют длину \(n\) и состоят только из букв от ‘a’ до ‘z’.

Формат выходных данных
Если возможно осуществить описанный процесс так, чтобы из \(S\) получилась \(T\), выведите <<YES>>, на следующей строке выведите \(m\) – количество различных символов \(S\), которые хотя бы раз заменялись. Обозначим эти символы за \(c_1,\ c_2,\ \ldots \ c_m\). После чего выведите \(m\) строк. На \(i\)-й строке необходимо вывести символы \(c_i\) и \(p(c_i)\) через пробел. Если это сделать невозможно, выведите <<NO>>.

Задача на реализацию

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

Операнды - 2#50950

Алина выписала на доске \(n + 1\) цифру, каждая из которых от \(1\) до \(9\). Даша поставила между каждой парой соседних цифр знак одной из арифметических операций <<+>>, <<->>, <<*>> и <</>> (плюс, минус, умножить, целочисленное деление). Затем девочки отправились в столовую на обед.

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

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

Формат входных данных
В первой строке входного файла дано число \(n\), число знаков, которые написала Даша (\(1 \le n \le 1000\)).

Во второй строке находится \(n\) знаков арифметических операций <<+>>, <<->>, <<*>> и <</>> (без кавычек).

Формат выходных данных
Выведите в единственной строке файла последовательность из \(n + 1\) цифры, таким образом, чтобы при расстановке между ними знаков итоговый результат был минимальным.

Если возможных решений несколько, разрешается вывести любое.

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

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

1#50764

Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников.
Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD.
Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.

Задача на реализацию Элементарная геометрия

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

Баскетбол#50693

На физкультуре школьники 10-А класса играют в баскетбол. В классе учится \(n\) школьников, которые построились в ряд. Учитель физкультуры разделил их на две команды следующим образом: в первую команду пошли школьники, которые стоят на нечетных местах: первом, третьем, пятом, и т. д. Школьники, которые стоят на четных местах: втором, четвертом, шестом, и т. д. составили вторую команду.

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

Игрок, которые провел на поле больше всего минут к этому моменту (не обязательно подряд) отправляется на скамейку запасных. Если таких игроков несколько, отдыхать идет игрок с максимальным номером в исходном построении.

Запасной же игрок, которые провел к этому моменту на поле меньше всего минут, выходит на поле. Если таких игроков несколько, на поле выходит игрок с минимальным номером в исходном построении.

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

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

После первой минуты игры Сидоров и Андреев пойдут на скамейку запасных, а на поле появятся Казаков и Сергеев. После второй минуты отдыхать пойдут Иванов и Петров, а Сидоров и Андреев вернутся на поле. Наконец, после третьей минуты Казаков и Сергеев снова пойдут отдыхать, а на площадке появятся Сидоров и Андреев. Таким образом после трех смен на поле будут (в алфавитном порядке) Андреев, Иванов, Петров и Сидоров.

Формат входных данных
Первая строка содержит три целых числа: \(n\), \(m\) и \(p\) (\(2p \le n \le 50\), \(1 \le p \le 10\), \(0 \le m \le 100\)). Следующие с \(n\) строк содержат по одной фамилии — игроки в том порядке, в котором они исходно построились Каждая фамилия представляет собой непустую последовательность букв латинского алфавита не длиннее 50. Все фамилии различны.

Формат выходных данных
Выведите в алфавитном порядке фамилии игроков, которые будут на поле после \(m\) смен составов. Разделяйте фамилии пробелом.

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

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

Разноцветные диагонали#50399

Миша увлекается компьютерной графикой. Он хочет нарисовать на экране квадрат размером \(n\times n\) пикселей разными цветами.

Монитор Миши поддерживает 26 цветов. Для обозначения цветов будем использовать строчные буквы латинского алфавита от <<a>> до <<z>>. Миша хочет нарисовать каждый пиксель некоторым цветом, который зависит от расстояния от пикселя до ближайшей диагонали.

А именно, клетки на диагоналях квадрата он хочет нарисовать цветом <<a>>, соседние с ними клетки — цветом <<b>>, соседние с ними, но еще не покрашенные — цветом <<c>>, и так далее. После цвета <<z>> Миша снова переходит к цвету <<a>>.

По заданному \(n\) выведите картинку, которая получится у Миши.

Формат входных данных
Входные данные содержат одно целое число \(n\) (\(1 \le n \le 100\)).

Формат выходных данных
Выведите \(n\) строк по \(n\) символов — картинку, которая получится у Миши.

Вывод формулы Задача на реализацию

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

Пути Дика#50351

Одной из визуализаций правильных скобочных последовательностей являются пути Дика. Путь Дика — путь на клетчатой плоскости, составленный из диагональных отрезков, соединяющих противоположные углы единичных квадратов. Путь начинается из начала координат, открывающейся скобке соответствует отрезок, поднимающийся вправо вверх, а закрывающиейся — спускающийся вправо вниз. На рисунке показан путь Дика для скобочной последовательности <<(())()>>.

Требуется написать программу, которая изображает путь Дика для заданной правильной скобочной последовательности с использованием символов <<.>> (ASCII 46) для пустых единичных квадратов, <</>> (ASCII 47) для единичных квадратов, содержащих отрезок, поднимающийся вверх, и <<‘
>> (ASCII 97) для единичных квадратов, содержащих отрезок, спускающийся вниз.

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

Формат входных данных
На ввод подается правильная скобочная последовательность. Она непуста и имеет длину не более \(100\) символов.

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

Алгоритмы обработки Задача на реализацию

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

Новое слово#50350

В информатике иногда образуют новые слова, взяв начало одного слова и конец другого. Например, из слов <<tree>> и <<heap>> образовано слово <<treap>>.

Дано слово \(s\) и слово \(t\). Сколько различных слов можно образовать, добавив к непустому началу слова \(s\) непустой конец слова \(t\)?

Формат входных данных
Первая строка входных данных содержит слово \(s\).

Вторая строка входных данных содержит слово \(t\).

Каждое из слов непусто и состоит из строчных латинских букв. Длина каждого из слов не превышает \(100\,000\).

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

Задача на реализацию Пересечение множеств

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

Конфеты для первоклассников#50349

Старшеклассники Андрей и Аня планируют прийти на празднование 1 сентября у первоклассников. Они решили принести конфеты, чтобы раздать ребятам. Им известно, что на празднике будет \(n\) первоклассников. Каждый из старшеклассников готов купить от \(a\) до \(b\) конфет, включительно. Они хотели бы купить в сумме такое число конфет, чтобы их можно было поделить между всеми первоклассниками поровну. Если же такое число конфет купить не получается, то они хотят, чтобы после деления поровну между первоклассниками осталось как можно меньше конфет.

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

Формат входных данных
На ввод подаются три натуральных числа, по одному на строке: \(n\) — число первоклассников, \(a\) и \(b\) — минимальное и максимальное число конфет, которое согласен купить каждый из старшеклассников (\(1 \le n \le 10^9\), \(1 \le a \le b \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(x\) и \(y\) — число конфет, которые купят Андрей и Аня, соответственно.

Вывод формулы Задача на реализацию

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

Перекладывание ответственности#49858

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

Всего в команде разработчиков \(n\) человек. Также есть \(n\) задач, которые необходимо подготовить. Подготовка \(i\)-й задачи требует подготовки ровно \(c_i\) ее элементов, и разработка каждого элемента \(i\)-й задачи имеет сложность \(w_i\).

Было решено, что каждый разработчик будет отвечать за столько же элементов, за сколько он бы отвечал, если бы разрабатывал целиком соответствующую задачу. Иными словами, \(i\)-му разработчику будет назначено ровно \(c_i\) элементов из различных задач. Распределение элементов по разработчикам происходит следующим образом:

Сначала первому разработчику выдается \(c_1\) элементов, затем второму — \(c_2\), и так далее. Переход к \((i+1)\)-му разработчику происходит в тот момент, когда \(i\)-му назначается ровно \(c_i\) элементов.
Элементы, за которые будет отвечать каждый разработчик, выбираются по одному из всех еще не до конца распределенных задач по очереди. Сначала будет выбран один этап из первой задачи, затем — из второй, из третьей, и так далее по кругу. Если в какой-то задаче не осталось нераспределенных этапов, она пропускается.
Элементы, назначаемые очередному разработчику, выбираются начиная с той задачи, на которой остановился предыдущий разработчик. То есть, если последний элемент, назначенный предыдущему разработчику, был из \(x\)-й задачи, то первый элемент, назначенный следующему, будет из задачи \((x+1) \bmod n\) (если в ней еще остались нераспределенные элементы).

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

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

Формат входных данных
В первой строке дано целое число \(n\) — количество разработчиков (\(1 \le n \le 500\,000\)).

В \(i\)-й из следующих \(n\) строк через пробел даны два целых числа \(c_i\) и \(w_i\) — количество элементов в \(i\)-й задаче и сложность их разработки (\(1 \le c_i, w_i \le 10^9\)).

Формат выходных данных
В единственной строке выведите через пробел \(n\) чисел, \(i\)-е из которых равно суммарной сложности разработки элементов, доставшихся \(i\)-му разработчику.

Замечание
Иллюстрацию к третьему примеру можно видеть ниже. Слева показаны элементы, из которых состоят задачи, справа — элементы, назначенные каждому разработчику.

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

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

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

Биржа - 2#49776

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

Торги проходят в течении \(n\) дней, всего на рынке представлены акции \(m\) компаний, цены акций компании фиксированы в течении одного дня. Сделки бывают двух типов:

Купить \(x\) акций компании \(comp\)
Продать все акции компании \(comp\)

За каждую сделку надо заплатить 1% комиссии. Например, если купить 10 акций по 300 рублей, то суммарно заплатить придется 3030 рублей. Если же продавать 10 акций стоимостью 300 рублей каждая, то за них можно получить 2970 рублей.

Прибылью с продажи будем считать разность полученных при продаже денег и суммарно потраченных денег при покупках. Например, если 10 акций были куплены по 300 рублей, а затем еще 5 акций были куплены по 400 рублей, то в случае продажи по стоимости 500 прибыль составит: \(15 \cdot 500 \cdot 0.99 - (10 \cdot 300 \cdot 1.01 + 5 \cdot 400 \cdot 1.01) = 7425 - (3030 + 2020) = 2375\) рублей. При этом, акции могут быть проданы в убыток (за меньшую стоимость, чем были куплены), тогда прибыль с продажи будем считать отрицательной.

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

Вам даны \(k\) событий покупки/продажи. Необходимо найти минимальную суммарную прибыль среди всех моментов времени.

Входные данные
В первой строке входных данных содержится одно целое число \(t\) — число тестовых наборов (\(1 \le t \le 30\)).

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

В первой строке тестового набора содержатся три целых числа \(n\), \(m\) и \(k\) — число дней, в которые проходят торги, число компаний на рынке и число событий, соответственно (\(1 \le n, m \le 100\), \(1 \le k \le 1000\)).

В следующих \(m\) строках записаны названия компаний и \(n\) чисел — стоимости акций компании в рублях в каждый из дней торгов. Названия компаний состоят из не более чем \(10\) строчных букв латинского алфавита и попарно различны. Стоимости акций — целые числа в диапазоне от \(1\) до \(10^5\) включительно.

В следующих \(k\) строках заданы события покупки/продажи в хронологическом порядке. Событие покупки задается в формате <день> buy <число акций> <название компании>, а событие продажи задается в формате <день> sell <название компании>. При этом <день> — целое число от \(1\) до \(n\), а <число акций> — целое число от \(1\) до \(1000\). Гарантируется, что все события следуют в порядке неубывания дней и корректны, а именно нет продаж некупленных акций и покупок акций, которых нет на рынке.

Выходные данные
Для каждого тестового набора выведите в отдельной строке минимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).

Примечание

В первом тестовом наборе изначально до продаж суммарная прибыль равна \(0\), после первой продаже суммарная прибыль становится \(2375\) (случай разобран в примере).

Во втором тестовом наборе промежуточные прибыли равны \(0\), \(-11.11\) (акция продана дороже, но комиссия больше разницы) и \(1948.89\).

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

В четвертом тестовом наборе промежуточные прибыли равны \(0\) и \(979.9\), деньги потраченные на непроданные акции не учитываются.

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

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

Трансформация массива - 2#49774

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

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

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

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

Выходные данные
Для каждого пары массивов выведите одно число — минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или \(-1\), если для данной пары это невозможно.

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

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

Тестирование мессенджера - 2#49030

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

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

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

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

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.
События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.
События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

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

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

Задача на реализацию Сортировка событий Хеш

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

Горнолыжный курорт#43133

Саша Белый недавно устроился подрабатывать на горнолыжный курорт недалеко от Аши. Первым делом ему поручили установить ограждения для лыжной трассы.
Саше дали n ограждений, каждое длиной a_i. Любые два последовательных ограждения скреплены друг с другом, но при этом могут произвольно поворачиваться друг относительно друга.
Саша хочет сделать трассу интересной: по его мнению, трасса должна быть в форме спирали (ограждение под номером i +1 должно быть повернуто на 90 градусов по часовой стрелке относительно ограждения под номером i; при этом никакие ограждения, кроме смежных, не должны касаться друг друга и пересекаться).
К сожалению, не из любых наборов ограждений можно сложить спираль. Помогите Саше для заданного набора определить, возможно ли из него составить спираль.
Входные данные
В первой строке входных данных записано целое число n — количество ограждений (1 <= n <= 10⁵). Во второй строке через пробел заданы n целых чисел a_i — длина i-го ограждения (1 <= a_i <=10⁹).
Выходные данные
Выведите YES, если возможно из данных ограждений сложить спираль, или NO в противном случае.

Примеры

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

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

Задача на реализацию Разбор случаев

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

Ящики#43125

Саша Белый давно планировал переехать в Кыштым. И вот настал день X. Саша собрал все свои вещи в ящики и вынес их на улицу. Ящики были распределены на n стопок, расположенных вдоль одной прямой, следующим образом: a₁ ящиков в первой стопке стоят непосредственно у газели, a₂ ящиков во второй стопке – правее первой на метр, следующие a₃ еще через метр и т.д. Теперь Белому нужно переставить все ящики как можно ближе к газели, а именно, все ящики из второй, третьей и т.д. стопок должны быть переставлены в первую стопку к исходным a₁ ящикам.
Саша за этот день уже очень устал. Но, к счастью, мимо проходили n мальчишек. Ребята согласились перенести ящики. Каждый из них, ввиду своей выносливости, переносит грузы следующим образом:
1. i-й мальчик проходится по стопкам, номера которых делятся на i, справа налево.
2. Он берет из первой стопки на своем пути ровно один ящик (эта стопка обязана быть непустой).
3. Пройдя i метров налево (то есть до следующей стопки, номер которой делится на i), он снова берет один ящик со стопки, рядом с которой он стоит (исходя из этого, в стопке обязательно должен быть хотя бы один ящик), пройдя еще i метров налево он снова берет ящик и так далее.
4. Когда i-й мальчик доходит до стопки с номером i, он кладет все ранее взятые ящики в эту стопку.

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

Входные данные
В первой строке входных данных записано целое число n количество стопок ящиков (1 <= n <= 10⁵).
Во второй строке через пробел записаны n целых чисел di количество ящиков в i-й стопке (1 <= d_i <= 10⁹).
Выходные данные
Выведите YES, если существует способ, при котором ребята перенесут все ящики к газели в первую стопку, или NO, если такого способа нет.

Примеры

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

Замечание
В первом примере сначала второй мальчик пройдется два раза, таким образом перенеся два ящика из четвертой стопки во вторую. После этого шага d = (2,3,3,3,3). Потом первый мальчик пройдется 3 раза, перетащив все ящики в первую стопку.
Во втором примере мальчикам не удастся перенести все ящики в первую стопку.

Вывод формулы Задача на реализацию математика

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

Диадема Клеопатры#38955

Аня — страстный любитель ювелирных изделий. Ее коллекция насчитывает множество бриллиантов, изумрудов и алмазов.

...Срочная новость! Бесценный змеиный рубин Клеопатры был украден!

Три дня назад мир потрясло сенсационное известие: исследовательская экспедиция обнаружила в одном из храмов, построенных во времена великой египетской императрицы Клеопатры, потайную комнату. В ней кроме бронзовой статуи императрицы обнаружилась поразительной красоты диадема, ранее считавшаяся бесследно утерянной! Ученые сообщили, что диадема увенчана алым a-каратным рубином в форме змеиной головы. Однако буквально пару часов назад поступила новость, что бесценное украшение было изувечено: кто-то пробрался в камеру хранения диадемы и вырезал из нее рубин! Полиция устанавливает круг подозреваемых...

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

Купив все N камней, Глеб тут же провел несколько пробных измерений, взвесив некоторые наборы из них, и отправил результаты Ане по электронной почте. Тем временем она проконсультировалась с известным исследователем старины Андрэ Шесто-Мерта по поводу украденной драгоценности и узнала, что по всем имеющимся историческим источникам рубин весил не a карат, как утверждали журналисты, а b карат!

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

Входные данные
В первой строке находятся четыре целых числа N, a, b и K (1 ≤ N ≤ 200, 1 ≤ a, b ≤ 1 000 000, a ≠ b, 1 ≤ K ≤ 1 000).

Далее идут K строк, описывающих взвешивания, проведенные Глебом.

Первое число в i-ом описании — w_i (1 ≤ w_i ≤ 200 000 000), суммарный вес группы камней, участвовавших в i-ом взвешивании.

Второе число — m_i (1 ≤ m_i ≤ N) — количество камней, участвовавших в i-ом взвешивании.

Далее следуют m_i целых чисел, упорядоченных по возрастанию, — номера камней, участвовавших в i-ом взвешивании.

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

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

Если же Глеб в некоторый момент ошибся в расчетах, и присланная им информация о взвешиваниях не может соответствовать действительности, выведите строку "Impossible" (без кавычек).

Примеры

№	Входные данные	Выходные данные
1	4 15 17 2 30 2 1 3 47 3 2 3 4	2 2 4
2	3 15 17 3 30 2 1 2 30 2 2 3 47 3 1 2 3	Impossible
3	2 1 2 2 1 1 2 1 1 1	Fail

Примечание
В первом тесте из первого взвешивания мы делаем вывод, что первый и третий камни гарантированно поддельные. С другой стороны, среди второго, третьего и четвёртого камня точно есть настоящий. Значит настоящим может оказаться второй или четвёртый камень.

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

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

Задача на реализацию Разбор случаев

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

Построение#38517

N учащихся класса, удобно пронумеровали числами от 1 до N. На линейке 1 сентября они стояли в ряд, но теперь не уверены в том, в каком порядке они стояли. Однако каждый запомнил следующий факт: абсолютную разницу между количеством учащихся, стоявших слева от этого человека, и количеством учащихся, которые стояли справа от этого человека. Согласно их отчетам, разница для человека i равна A_i . На основании этих отчетов, найдите количество возможных расстановок, в которых они стояли. Поскольку ответ может быть очень большим, выведите его по модулю \(10^9+7\). Обратите внимание, что отчеты могут быть неправильными и, следовательно, не может быть согласованного порядка. В таком случае выведите 0.

Входные данные
В первой строке задается число N (\(1<=N<=10^5\)). Во второй строке N чисел A_i (\(0<=A_i<=N-1\)).

Выходные данные
Выведите количество возможных расстановок по модулю \(10^9+7\).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 2 4 4 0 2	4	Возможны 4 расстановки учащихся, а именно: 2 ,1 ,4 ,5 ,3 2 ,5 ,4 ,1 ,3 3 ,1 ,4 ,5 ,2 3 ,5 ,4 ,1 ,2
2	7 6 4 0 2 4 0 2	0	Любая расстановка не совместима с отчетами. Поэтому ответ 0.
3	8 7 5 1 1 7 3 5 3	16

Вывод формулы Задача на реализацию Разбор случаев

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

Робот#38460

Некоторый заводской цех представляет собой прямоугольник размером M на N метров (1 <= M, N <= 30). Инженер-конструктор Петя создал робота, который может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат.

У робота есть 4 регистра состояния, A, B, C и D. Каждый регистр может принимать одно из двух значений - TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо.

Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты X₀, Y₀ под начальным углом A0 (0,90,180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота - FALSE.

Аккумуляторных батарей робота хватит на K (0 < K <= 10⁹) перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос.

Оси координат направлены из левого верхнего угла - точки (1,1) - соответственно вправо и вниз. M - размер цеха по горизонтали, а N - по вертикали. Количество триггеров - P - не превосходит 10000, а радиомаяков - Q - 25.

Входные данные
На первой строке входного файла записаны 8 чисел - M,N,P,Q,K,X0,Y0,A0. Далее на Р строках записаны триггеры в формате "X Y R", где R - название регистра. Далее на Q строках записаны радиомаяки в формате "X Y F", где F - булева функция от переменных A..D длиной не более 250 символов, заданная корректной формулой, причем:

-   A, B, C, D, TRUE, FALSE – корректные формулы
-   Если F – корректная формула, то «(F)» и «NOT F» – корректные формулы
-   Если F и G – корректные формулы, то «F AND G», «F OR G» и «F XOR G» – корректные формулы
-   Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)
-   регистр букв не имеет значения
-   корректная формула не содержит лишних пробелов
Выходные данные
В случае успешного исхода вывести координаты плиты, где остановится робот. В случае краха эксперимента вывести в выходной файл единственное число «-1».

Примеры

№	Входные данные	Выходные данные
1	8 8 1 9 420000001 3 4 180 3 3 A 3 5 FALSE 6 5 FALSE 6 2 FALSE 3 2 A 3 1 FALSE 1 1 FALSE 1 8 FALSE 2 8 FALSE 2 2 TRUE	3 5

Примечание

В соответствии с рисунком, робот будет двигаться по «восьмерке» суммарной длиной 42 метра. Следовательно, прохождение 42n+1 метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами
«3 5».

Задача на реализацию Задачи на моделирование Разбор случаев

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