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

Мегазорды#38866

Мегазорд — необходимая вещь для защиты Земли. Для сборки одного мегазорда, необходимо ровно три зорда: зеленый, красный и синий.
Зеленому, красному и синему рейнджеру стало интересно, сколько у них есть различных способов собрать мегазорд. Для каждого рейнджера известен набор зордов, которыми он обладает. У зеленого рейнджера есть зеленые зорды, у красного рейнджера — красные, а у синего — синие.
При сборке мегазорда необходимо соблюдать три правила:

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

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

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

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

Рейнджеры в автобусе#38865

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

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

Примеры

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

Замечание

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

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

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

Космический корабль#38864

На пути к спасению городка Энджел Гроув черный рейнджер Зак Тейлор столкнулся с очередным препятствием. Рейнджер оказался на инопланетном космическом корабле в окружении врагов, и теперь, чтобы освободиться, ему необходимо уничтожить всех врагов в определенном порядке.
Каждый из n врагов обладает силой f_i. Однако среди них имеется главный враг — босс, чья сила равняется сумме сил всех остальных врагов. Так как уничтожение босса требует полной концентрации и сосредоточенности, Зак сможет справиться с ним только после того, как уничтожит всех остальных врагов.
В запасе у рейнджера мало времени, так что он не успевает понять, кто босс. Ему необходима ваша помощь. Восстановите порядок, в котором Заку Тейлору необходимо уничтожать врагов, чтобы выбраться на свободу.

Входные данные
В первой строке находится натуральное число n — количество врагов (3 ≤ n ≤ 10⁵).
Во второй строке находятся n целых чисел f_i, задающих силу каждого врага (-10⁹ ≤ f_i ≤ 10⁹).
Силы врагов заданы в случайном порядке.

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

Примеры

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

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

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

Закупка болтов и гаек - 04#38863

Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 shim 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

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

Закупка болтов и гаек - 03#38862

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 nut 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

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

Закупка болтов и гаек - 02#38861

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

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода (1 <= N <= 10⁵) и M - сумма выделенных на закупку денег (в рублях) (1 <= M <= 10⁹). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 nut 500 nut 3500 bolt 3000 bolt 2500 nut 1000 bolt`	`2 500`

ЕГЭ_информатика Использование сортировки

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

Закупка болтов и гаек - 01#38860

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 bolt 500 bolt 3500 nut 3000 nut 2500 bolt 1000 nut`	`2 500`

ЕГЭ_информатика Использование сортировки

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

Переключение между окнами#38849

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

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

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

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

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

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

Число#38848

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

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

Формат входных данных
Входные данные состоят из одной или более строк, каждая из которых содержит последовательность цифр. Количество строк не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Последняя строка входного потока содержит число -1 - признак окончания данных.

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

Алгоритмы на строках Использование сортировки

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

Кинотеатр#38839

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

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

В ответе запишите два целых числа через пробел: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.

Пример входного файла:
10
14 5
14 10
14 7
15 10
15 4
15 7
22 23
22 19
22 55
22 40
В данном примере есть следующие свободные места, удовлетворяющие условию: в 14 ряду места 8 и 9, в ряду 15 месте 5 и 6. Выбираем наибольший номер ряда: 15 и наименьший номер места: 5. В ответе нужно указать: 15 5.

Файл к заданию

ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка

1 300труднаяВойти и решать

Удаление клеток#38830

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

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

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

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

Вывести одно число.

Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

Обход в глубину Обход в ширину

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

При каком наименьшем х?#38813

Значение выражения \( 27^7 - 3^{11} + 36 - x\) записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100). Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Задача на реализацию Системы счисления

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

Сколько таких цифр? Решаем программой#38811

Результат арифметического выражения \(9^9 – 3^9 + 9^{19} – 19 \) записали в троичной системе счисления. Напишите программу, которая определит количество цифр "2", "1" и "0"в результирующем числе. Выведите ответ в одной строке, через пробел, в указанном порядке.

Задача на реализацию Разные системы счисления

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

Breaking News#38805

Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.
В частности, давно известно, когда в течение дня пара сотрудников встречается между собой.
При встрече сотрудники делятся друг с другом новостями.
Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня.
Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

Входные данные
В первой строке входного файла задано два целых числа N (2 ≤ N ≤ 1000) и D (1 ≤ D ≤ 100000) — количество сотрудников и встреч соответственно. В следующих D строках заданы описания встреч. Каждое описание встречи состоит из трех
чисел A_i, B_i и T_i (1 ≤ A_i, B_i ≤ N, 1 ≤ T_i ≤ 10⁹) — пара номеров сотрудников и время встречи.

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

Примеры

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

Деревья Обход в глубину

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

Раздача конфет#38794

У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит A_i количество конфет. Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- A_l + A_l+1 + ... + A_r делится на M.

Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=10⁵) и M (2<=M<=10⁹). Вторая строка содержит N чисел A_i (1<=A_i<=10⁹, 1<=i<=N).

Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.

Примеры

№	Входные данные	Выходные данные
1	3 2 4 1 5	3
2	13 17 29 7 5 7 9 51 7 13 8 55 42 9 81	6

ЕГЭ - вычислительные задачи Остатки

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

Генеалогическое древо - 2. Потомки#38786

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

Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента, необходимо вывести число его потомков.

Пример

№	Входные данные	Выходные данные
1	9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I	Alexander_I 0 Alexei 1 Anna 4 Elizabeth 0 Nicholaus_I 0 Paul_I 2 Peter_I 8 Peter_II 0 Peter_III 3

№

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

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

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I

Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3

Деревья поиск в глубину и подобное Словари

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

Генеалогическое древо - 1. Высота#38785

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

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

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

Пример

№	Входные данные	Выходные данные
1	9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I	Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2

№

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

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

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I

Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2

Линейные алгоритмы Словари

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

Любимый фрукт#38781

У всех жителей Цветочного города спросили его любимый фрукт. Определите самый любимый фрукт среди всех жителей Цветочного города.

Входные данные
Программа получает на вход текст (количество строк может быть много). Текст заканчивается строкой END!.

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

Пример

№	Входные данные	Выходные данные
1	apple orange banana banana orange END!	banana

Использование сортировки Словари

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

Железная дорога#38776

Вите на день рождения подарили Очень Большую Игрушечную Железную Дорогу. Она представляет собой два параллельных пути, по которым движутся поезда во встречных направлениях. В центре находится станция, а железная дорога очень большая, поэтому можно считать пути бесконечными в обе стороны. Витя расставил поезда на железной дороге и одновременно запустил их, включив электропитание. Все поезда движутся с одинаковыми скоростями в одном из двух возможных направлений. Но когда-нибудь поезда придётся остановить и убрать игру, а поскольку поезд не может развернуться и начать движение в противоположном направлении, Вите придётся самому собирать поезда руками и переносить их на станцию. Витя хочет выбрать такой момент остановки всех поездов, чтобы ему пришлось потратить минимальное число усилий для того, чтобы собрать после этого все поезда на станции вместе, то есть в этот момент времени сумма расстояний всех поездов до станции была бы минимальной.

Входные данные
Введём на железной дороге координаты, считая, что станция находится в начале координат, а все поезда первоначально находятся в целочисленных точках координатной прямой. Сами поезда также будем считать точками. За одну секунду координаты всех поездов изменяются на +1 или на −1. Поезда движутся с равными скоростями, первоначально никакие два поезда, движущиеся в одном направлении, не находятся в одной точке. Первая строка входных данных содержит целое число N — количество поездов, движущихся в положительном направлении. Вторая строка входных данных содержит целое число M — количество поездов, движущихся в отрицательном направлении. Ограничения: N > 0, M > 0, 1 <= N + M <= 10⁵ . Следующие N строк содержат N чисел ai (|ai | <= 10⁹ ) — первоначальные координаты поездов, движущихся в положительном направлении. Все числа ai различны и заданы в порядке возрастания. Следующие M строк содержат M чисел bj (|bj | <= 10⁹ ) — первоначальные координаты поездов, движущихся в отрицательном направлении. Все числа bj различны и заданы в порядке возрастания.

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

Пример

№	Входные данные	Выходные данные	Пояснение
1	3 2 -5 -2 4 1 4	2	В примере из условия 3 поезда движутся в положительном направлении, 2 поезда движутся в отрицательном направлении. Начальные координаты поездов, движущихся в положительном направлении равны −5, −2, 4, движущихся в отрицательном направлении равны 1 и 4. Запишем, что при t = 0 координаты поездов (−5, −2, 4, 1, 4). Суммарное расстояние всех поездов до станции равно 16. В момент t = 1 координаты поездов будут (−4, −1, 5, 0, 3), суммарное расстояние до станции равно 13. В момент t = 2 координаты поездов будут (−3, 0, 6, −1, 2), суммарное расстояние до станции равно 12. В момент t = 3 координаты будут (−2, 1, 7, −2, 1), суммарное расстояние до станции равно 13. Ответ на этот тест t = 2.

Вывод формулы Порядковые статистики

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

Не был предателем ...#38775

Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то способах коммуницировать заранее. Таких людей называют заговорщиками.
Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками. Помогите Грише решить эту задачу.

Входные данные
В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования. Во второй строке записана строка S, её длина также не превосходит 300. В третьей строке записано целое число N, 1 <= N <= 5 × 10⁶ — количество повторений строки S. Все строки состоят только из заглавных английских букв.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	MON AMONGUS 3	3
2	ABA BABA 3	5	Если строку BABA повторить 3 раза, получится BABABABABABA. В полученной строке подстрока ABA встречается 5 раз: BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA

Вывод формулы Поиск подстроки в строке

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