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

Шлюзы#48931

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(n\) шлюзов, \(i\)-й из них имеет объем \(v_i\) литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по \(1\) литру воды в секунду. Исходно все трубы закрыты.

Шлюзовая система устроена так, что если доливать воду в \(i\)-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером \(i + 1\). Если шлюз c номером \(i + 1\) тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.

Рисунок показывает \(5\) шлюзов с открытыми трубами к шлюзам \(1\) и \(3\). Так как шлюзы \(1\), \(3\) и \(4\) уже заполнены, фактически вода идет в шлюзы \(2\) и \(5\).

Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует \(q\) независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для \(j\)-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через \(t_j\) секунд все шлюзы стали заполнены.

Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!

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

Во второй строке вводятся \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — объемы шлюзов.

В третьей строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — число запросов.

В следующих \(q\) строках вводится по одному целому числу \(t_i\) (\(1 \le t_j \le 10^9\)) — время, за которое нужно наполнить все шлюзы в \(j\)-м запросе.

Формат выходных данных
Выведите \(q\) чисел, \(j\)-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время \(t_j\). Если за это время наполнить всю шлюзы невозможно, выведите \(-1\).

В первом примере \(6\) запросов:

В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.

В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.

Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).

В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).

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

Рамка для рисунка#48041

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

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

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

Формат входных данных
Первая строка входных данных содержит целое число n - количество палочек длины 1 (1 ≤ n ≤ 10⁹).
Вторая строка входных данных содержит целое число m - количество палочек длины 2 (1 ≤ n ≤ 10⁹).

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

Замечание
В первом примере есть 5 палочек длины 1. Из них можно сложить квадрат со стороной 1, его площадь равна 1, при этом одна палочка останется.
Во втором примере есть 4 палочки длины 1 и 3 палочки длины 2. Из них можно сложить прямоугольник размера 2 x 3.
В третьем примере есть 3 палочки длины 1, из них невозможно сложить прямоугольник.

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

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

Улица#47203

По одну сторону улицы находятся дома с нечётными номерами (1, 3, 5, …), по другую сторону – с чётными (2, 4, 6, …). Дом № 1 находится напротив дома № 2, дом № 3 – напротив дома № 4 и т. д. До соседнего дома нужно идти вдоль по улице одну минуту, неважно, с какой стороны улицы он находится (то есть от дома № 1 нужно идти одну минуту как до дома № 3, так и до дома № 4). До дома, стоящего напротив, идти не нужно.

Громозека вышел на улицу из дома номер A и должен дойти до дома номер B. Определите, сколько минут ему нужно идти вдоль по улице.

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

Входные данные
Программа получает на вход два различных целых положительных числа A и B,не превосходящие 2×10⁹, – номера домов.

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

Примеры

№	Входные данные	Выходные данные
1	1 8	3

Вывод формулы Целые числа

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

Два массива#45674

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз.

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности.

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

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

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

Выведите i-е число новой последовательности.

Примеры

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

Вывод формулы Разбор случаев Сортировка слиянием

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

Олимпиада по выживанию#44362

В некоторой стране каждый год проходит олимпиада по выживанию. В финале участвуют по 4 человека от каждой из n провинций. По результатам соревнования составляется рейтинг, в который входят все 4n участников в порядке убывания баллов, равных баллов у участников не бывает. Дипломами награждаются ровно 50 % лучших участников (то есть если общее число участников было равно m, то награждаются m/2 первых участников из общего рейтинга).
После публикации предварительного рейтинга тренеры команд могут подавать апелляции против каких-то других провинций, обвинив участников из этой провинции в нарушении правил олимпиады. Каждый тренер может не подавать аппеляции или подать апелляцию на одну или несколько команд соперников.
Если жюри удовлетворит апелляцию против команды, то все участники из данной провинции будут дисквалифицированы и удалены из таблицы результатов. При этом общее число количество участников уменьшится на 4, а количество призёров олимпиады уменьшится на 2.
Тренеры команд каждой из провинций хотят улучшить результаты участников из своей провинции (то есть сделать так, чтобы количество участников олимпиады из этой провинции, которые стали призёрами, увеличилось хотя бы на одного). Для этого они планируют подать апелляции против команд других провинцией. Для каждой провинции определите, какое минимальное количество аппеляций должно удовлетворить жюри, чтобы количество участников из этой провинции, награждённых дипломами, увеличилось. Обратите внимание на то, что вы должны дать ответ для каждой провинции независимо, то есть без учёта возможных апелляций, поданных другими командами.

Входные данные
В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 25000) — количество провинций, участвовавших в олимпиаде. Следующие 4·n строк содержат рейтинг участников олимпиады, в порядке от лучшего участника к худшему. В i-й строке содержится число от 1 до n — номер команды i-го по рейтингу участника олимпиады. Гарантируется, что в списке участников каждое число от 1 до n встречается ровно 4 раза.
Выходные данные
Программа должна вывести n строк. В i-й строке необходимо вывести минимальное число апелляций, которое должно удовлетворить жюри, чтобы количество награждённых дипломами участников из i-й команды увеличилось. Если улучшить результаты i-й команды путём подачи апелляций нельзя, то в i-й строке должно быть записано число −1.

Примеры

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

Замечание
В первом примере из условия в олимпиаде участвовали две команды, и рейтинг участников выглядит так: 1, 1, 1, 2, 2, 2, 2, 1. По предварительному рейтингу дипломами награждаются три участника команды 1 и один участник команды 2. Команда 1 не может улучшить свои результаты, так как если команда 2 будет дисквалифицирована, то дипломы будут выданы всего 2 участникам из 4, но первоначально у команды 1 было 3 диплома. А вторая команда может увеличить количество призёров до 2, подав апелляцию против команды 1.
Во втором примере у обеих команд уже есть по 2 диплома, а при удалении одной из команд останется всего 2 призовых места, то есть при подаче апелляции против другой команды у каждой команды количество дипломов не изменится.
В третьем примере участвовали 3 команды и первоначально дипломами награждались участники из команд 3, 3, 2, 2, 1, 3. Команда 1 может улучшить свои результаты, если подаст две апелляции: против команд 2 и 3. Тогда останется только 4 участника (все они из команды 1), из них дипломами будет награждено двое. Команда 2 может улучшить свои результаты, если подаст одну апелляцию против команды 3. Тогда останется 8 участников и дипломами будут награждены 4 из них: 2, 2, 1, 2, — и у команды 2 станет 3 призёра вместо 2. Команда номер 3 не может улучшить свой результат при помощи апелляций.

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

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

Спираль#44287

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

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

Примеры

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

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

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

Заказ в магазине#44273

Решив запастись ручками на весь новый учебный год, Игорь подсчитал, что ему нужно M ручек.
В его любимом интернет-магазине есть удобная функция — он может сразу добавить в заказ упаковку из любого числа ручек от 1 до N. Правда, оказалось, что нельзя добавить в заказ две упаковки одного размера. Например, если Игорю нужно купить M = 12 ручек, а максимальное число ручек в упаковке N = 10, то Игорь может добавить в заказ упаковку из 7 ручек и упаковку из 5 ручек, но не сможет добавить две упаковки из 6 ручек.
Сформируйте заказ на M ручек, используя минимальное число различных упаковок.

Входные данные
Первая строка входных данных содержит число N — максимальный размер одной упаковки (1 ≤ N ≤ 10⁹ ). Вторая строка входных данных содержит целое число M — необходимое количество ручек в заказе (1 ≤ M ≤ 10⁹ ).

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

Примеры

№	Входные данные	Выходные данные
1	10 12	5 7
2	2 5	0

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

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

44199#44199

Математической моделью является:

1) модель автомобиля;
2) сборник правил дорожного движения;
3) формула закона всемирного тяготения;
4) номенклатура списка товаров на складе.

Вывод формулы

800лёгкаяВойти и решать

44198#44198

Сколько моделей может соответствовать одному объекту?

1) 1
2) 2
3) 10
4) много

Вывод формулы

800лёгкаяВойти и решать

Подарки#42937

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

Входные данные
Первая строка входных данных содержит целое положительное число N — количество конфет в одном подарке. Вторая строка входных данных содержит целое неотрицательное число A — количество упаковок из одной конфеты. Третья строка содержит целое неотрицательное число B — количество упаковок из трёх конфет.
Чиcло N и общее число конфет на складе не превосходят 2 × 10⁹.

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

Примеры

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

Замечание
В примере из условия на складе имеются 8 упаковок из одной конфеты и 2 упаковки из трёх конфет. В один подарок необходимо положить 4 конфеты. Два подарка можно собрать, используя 1 упаковку из одной конфеты и 1 упаковку из трёх конфет. Ещё один подарок можно собрать из 4 упаковок из одной конфеты. Всего было использовано 6 упаковок из одной конфеты и 2 упаковки из трёх конфет, осталось 2 упаковки из одной конфеты, которых не хватит на дополнительный подарок.

Вывод формулы Разбор случаев

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

Мощный массив#41227

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.

Примеры:

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

Алгоритм Мо Вывод формулы

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

Хэш двойной строки#39669

Вам дано t запросов, в каждом из которых вам дана строка s, состоящая из строчных латинских букв, число p и число mod.
Для каждого запроса вычислите полиномиальный хэш с основанием p по модулю mod от строки, являющейся строкой s, где каждая буква продублирована. То есть, если s = "isaac", то нужно посчитать хэш от строки "iissaaaacc".

Входные данные:
В первой строке дается число t - количество запросов.
Далее идет t строк, в каждой из которых через пробел даны s (1 <= |s| <= 20), p (1 <= p <= 10⁵) и mod (1 <= mod <= 10⁸).

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

Пример:

Входные данные	Выходные данные
2 isaac 12345 87654321 newton 54321 12345678	8829000 9632318

Вывод формулы Хеш

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

Еще больше странных фотографий#39560

Фермер Джон фотографирует N своих коров (2≤N≤1000).
Каждая корова имеет целое число - "ID породы" в интервале 1…100. ФД разбить всех коров на несвязные группы (другими словами, поместить каждую корову ровно в одну группу) и затем выставить группы так, чтобы сумма "ID породы" коров в первой группе была чётной, во второй - нечётной и т.д., чередуя чётные и нечётные.

Какое максимальное количество групп может сформировать ФД?

Входные данные
Первая строка ввода содержит число N. Следующая строка содержит N разделённых пробелом целых чисел, представляющих "ID породы".
Выходные данные
Максимально возможное количество групп на фото ФД. Можно доказать, что хотя бы одна группа будет всегда.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	7 1 3 5 7 9 11 13	3	В этом примере один из способов сформировать максимальное количество (3) групп так: 1 группа: 1 3 2 группа: 5 7 9 3 группа: 11 13
2	7 11 2 17 13 1 15 3	5	В этом примере один из способов сформировать максимальное число (5) групп так: 1 группа: 2 2 группа: 11 3 группа: 13 1 4 группа: 15 5 группа: 17 3.

Вывод формулы

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

Коровы в стойле#39551

У Фермера Джона есть N коров (1 ≤ N ≤ 20) с высотами a₁…a_N. Его амбар имеет N стойл с максимальными высотами b₁…b_N (поэтому например, b₅=17 означает, что коров с высотой не более 17 можно разместить в стойле 5). Сколькими различными способами ФД может разместить коров по стойлам, так чтобы ограничение по высоте было выполнено для каждого стойла.

Входные данные
Первая строка содержит N. Вторая строка содержит N разделённых одиночными пробелами чисел a₁, a₂,…,a_N. Третья строка содержит N разделённых одиночными пробелами чисел b₁,b₂,…,b_N. Все величины - целые числа в интервале [1,10⁹].

Выходные данные
Количество способов, которыми ФД может разместить коров в стойлах, так чтобы для каждого стойла был удовлетворён лимит по высоте. Заметьте, что ответ может быть очень большим, поэтому для него требуется использовать 64-битную целую переменную, такую как "long long" в C++.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 2 3 4 2 4 3 4	8	В этом примере мы не можем разместить третью корову в первое стойло, поскольку 3=a₃>b₁=2. Аналогично, мы не можем разместить 4-ую корову в 1-ое или 3 -е стойло. Один из 8 способов размещения: корову 1 в стойло 1, корову 2 в стойло 2, корову 3 в стойло 3 корову 4 в стойло 4.

Вывод формулы

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

Треугольники#39517

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 100) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 1 1 0 1 2	3	Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1. Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5. Поэтому ответ 2⋅(1+0.5)=3.

Вывод формулы Перебор

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

Часовое дерево#39505

Новый амбар Фермера Джона состоит из N комнат (2 ≤ N ≤ 2500), последовательно пронумерованных 1…N, и N−1 коридоров. Каждый коридор соединяет пару комнат таким образом, что возможно пройти из лбой комнаты в любую через серию коридоров.
Каждая комната в амбаре имеет круглые часы на стене со стандартным размещением цифр 1…12 на лицевой стороне. Однако на этих часах имеется только одна стрелка, которая всегда показывает точно на одно из целых чисел (она никогда не показывает между двумя из этих чисел).

Корова Беси хочет синхронизировать все часы в амбаре, чтобы они все показывали на число 12. Но со своим коровьим мышлением, каждый раз, когда она входит в комнату, она перемещает стрелку вперёд на одну позицию. Например, если стрека показывала на 5, Беси переводит стрелку на 6. Если часы указывали на 12, она переводит стрелку на 1. Если Беси входит в комнату несколько раз, она переводит стрелку при каждом входе.

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

Входные данные
Первая строка ввода содержит N. Следующая строка содержит N целых чисел, каждое в интервале 1…12, указывающих начальные положения стрелок в каждой комнате. Каждая из следующих N−1 строк описывает коридор двумя целыми числам a и b, каждое в интервале 1…N, и задающих номера комнат, соединённых этим коридором.

Выходные данные
Выведите номера комнат, в которых Беси может начинать, чтобы установить все часы на 12.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 11 10 11 11 1 2 2 3 2 4	1	В этом примере Беси может установить все стрелки на 12, тоько в том случае, если она начнёт в комнате 2 (например перемещаясь так: 1, 2, 3, 2, 4.

Вывод формулы Обход в глубину

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

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

Чтобы разнообразить игру «морской бой» Боря решил добавить в неё новый тип кораблей. Эти корабли состоят из двух прямоугольников. Первый прямоугольник имеет ширину w₁ и высоту h₁, а второй прямоугольник - w₂ и h₂ соответственно. Прямоугольники располагаются один над другим и выровнены по левому краю (см. рисунки примеров): введём на поле систему координат так, чтобы левая нижняя клеточка первого прямоугольника имела координаты (1,1). Тогда верхняя правая клеточка первого прямоугольника имеет координаты (w₁,h₁), левая нижняя клеточка второго прямоугольника имеет координаты (1,h₁+1), а правая верхняя клеточка второго прямоугольника имеет координаты (w₂,h₁+h₂).

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

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

Входные данные
В четырёх строках заданы четыре целых числа w₁,h₁,w₂ и h₂ (1<=w₁,h₁,w₂,h₂<=10⁸) - ширина первого прямоугольника, высота первого прямоугольника, ширина второго прямоугольника и высота второго прямоугольника, соответственно.

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

Примечание

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

Во втором примере поле выглядит так:

Примеры

№	Входные данные	Выходные данные
1	2 1 2 1	12
2	2 2 1 2	16

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

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

Порядочные числа#38953

У Миши развитое эстетическое чувство. Он считает, что не все числа одинаково порядочные. Когда ему грустно, он начинает придумывать числа и приводить их в порядок.

Миша очень любит рассматривать сумму цифр числа. Для того чтобы привести в порядок число A, он сначала записывает само число. Потом он пишет сумму цифр этого числа. Затем — сумму цифр суммы цифр и так далее, до тех пор, пока очередное число не станет однозначным. Он считает, что результатом приведения в порядок числа A является сумма всех выписанных чисел, включая само число A.

Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.

Входные данные
На ввод подаётся единственное целое число B (1 ≤ B ≤ 10⁹ )

Выходные данные
Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.

Примеры

№	Входные данные	Выходные данные
1	42	29
2	20	-1

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

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

Мегазорды#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средняяВойти и решать

Железная дорога#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средняяВойти и решать