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

Программа для Громозеки#42243

Когда Громозека держит в руках сразу две печеньки с числами, он сразу пробует преобразовать большее число в меньшее. При преобразовании он использует только две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка. Громозека любит, чтобы преобразование происходило как можно быстрее. Помогите Громозеке составить последовательность команд, при которой из большего числа получится меньшее, причем за наименьшее количество команд.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке). A >= B.

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

Примеры

№	Входные данные	Выходные данные
1	`21 2`	`-1 :2 :2 -1 :2`

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

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

Короткий код#40164

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

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

Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 10⁵) — число переменных в коде Эвана.

Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 10⁵. Все названия переменных различны.

Выходные данные:
Выведите одно целое число — минимально возможную суммарную длину новых названий переменных.

Примеры:

Входные данные	Выходные данные
3 codeforces codehorses code	6
5 abba abb ab aa aacada	11
3 telegram digital resistance	3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

Бор Деревья Жадный алгоритм

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

Игра со строками#40161

Дана игра для двоих игроков со строками.

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

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

Входные данные:
Первая строка содержит целое число n (1 ≤ n ≤ 10⁵).
Каждая из n следующих строк содержит непустую строку из заданного набора. Суммарная длина всех строк из набора не превышает 10⁵. Все строки из набора состоят только из строчных латинских букв.

Выходные данные:
Если победит игрок, который ходит первым, то выведите «First», иначе выведите «Second» (кавычки выводить не нужно).

Примеры:

Входные данные	Выходные данные
3 a b c	First
1 ab	Second

Бор Игры и выигрышные стратегии Обход в глубину

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

Сжатие строки#39962

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

Сжатая версия строки s — последовательность строк c₁, s₁, c₂, s₂, ..., c_k, s_k, где c_i — десятичная запись числа a_i (без лидирующих нулей), а s_i — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s₁ ровно a₁ раз, потом s₂ ровно a₂ раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c₁| + |s₁| + |c₂| + |s₂|... |c_k| + |s_k|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.

Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).

Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.

Примеры:

Входные данные	Выходные данные
aaaaaaaaaa	3
abcab	6
cczabababab	7

Пояснения:
В первом примере Хлоя выберет следующую версию: c₁ — 10, s₁ — a.
Во втором примере Хлоя выберет следующую версию: c₁ — 1, s₁ — abcab.
В третьем примере Хлоя выберет следующую версию: c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — ab.

Z-функция. Префикс-функция Динамическое программирование

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

Xor-пути в матрице#39836

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел a_i,j, где j-й элемент i-й строки равен a_i,j (0 <= a_i,j <= 10¹⁸).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.

Примеры

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

meet in the middle Перебор

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

XOR#39625

Исключающим "или" (XOR) называется булева функция, а также логическая и битовая операция от двух аргументов, результат которой истинен тогда и только тогда, когда один из аргументов истинен, а второй - ложен.
Циклический побитовый сдвиг вправо - операция, при которой младший разряд переносится в начало числа и становится старшим, а все остальные сдвигаются вправо на одну позицию.
К двум 16-битовым числам A и B, записанным в 16-ричной системе счисления, была применена операция исключающего "или", а затем к результату - операция побитового циклического сдвига вправо на K разрядов. Одно из двух исходных чисел было забыто, требуется его восстановить.
Входные данные
в строку через пробел записаны числа A, K и результат X. Числа A и X заданы в 16-ричной системе счисления, K - в десятичной.
Выходные данные
число B.

Примеры

№	Входные данные	Выходные данные
1	1A2B 4 4E5D	FFFF
2	AB00 1 5C9A	1234

Разные системы счисления Системы счисления

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

Танцевальные движения#39575

Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10⁵) стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся K (1≤K≤2⋅10⁵) парами позиций (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Каждую минуту i=1…K танца коровы на позициях a_i и b_i меняются местами. Такие же K обменов делаются на минутах K+1…2K, затем опять на минутах 2K+1…3K, и т.д. Другими словами,

на минуте 1 меняются местами коровы на позициях a₁ и b₁.
на минуте 2 меняются местами коровы на позициях a₂ и b₂.
...
На минуте K меняются местами коровы на позициях a_K и b_K swap.
На минуте K+1, меняются местами коровы на позициях a₁ и b₁.
На минуте K+1, меняются местами коровы на позициях a₂ и b₂.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a₁,b₁)…(a_K,b_K) (1≤a_i<b_i≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 4 1 3 1 2 2 3 2 4	4 4 3 4 1	Корова 1 достигнет позиций {1,2,3,4}. Корова 2 достигнет позиций {1,2,3,4}. Корова 3 достигнет позиций {1,2,3}. Корова 4 достигнет позиций {1,2,3,4}. Корова 5 не будет двигаться, и не покинет позицию 5.

Обход в глубину Перестановки

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

Раз-два-три-четыре-пять корову поменять#39514

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

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

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

Прогулка Громозеки и Алисы#39392

Громозека и Алиса старые друзья. Встречаясь на какой-то планете, они постоянно заходят в кафе. Но Алиса не любит заходить в каждое a-ое кафе, а Громозека в каждое g-ое кафе. Чтобы никого не обидеть, они не заходят в те кафе, в которые не хотят заходить одновременно и Алиса и Громозека. На очередной прогулке у них на пути N кафе. Во сколько кафе они смогут зайти?

Входные данные
Единственная строка содержит три целых числа - a , g , N ( 1 <= a , g , N <= 10⁹ ).

Выходные данные
Выведите единственное число - количество кафе, в которые смогут зайти Громозека и Алиса.

Примеры

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

Алгоритмы НОД и алгоритм Евклида

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

Отслеживание контактов#39388

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

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

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.

Примеры

№	Входные данные	Выходные данные
1	`4 3 1100 7 1 2 5 2 3 6 2 4`	`1 1 Infinity`

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

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

Королевское путешествие#39387

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

Входные данные
Сначала вводится число N (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует N строк по N чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

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

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

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

Скупщик шоколада#39384

Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает купить M плиток шоколада. В городе есть N магазинов, которые продают различный шоколад. В i-м магазине Василий может купить не более B_iплиток шоколада по A_i рублей каждая. Помогите Василию определить, какую минимальную сумму денег ему необходимо накопить, чтобы купить M плиток шоколада?
Гарантируется, что располагая нужной суммой, Василий всегда сможет купить M плиток шоколада.

Входные данные
В первой строке заданы два числа: N и M (1 <= N, M <= 10⁵). Следующие N строк содержат по 2 числа: A_i (1 <= A_i<= 10⁹) и B_i (1 <= В_i <= 10⁵). \(B_1 + B_2 +... + B_N >= M\).

Выходные данные
Выведите минимальную сумму денег, необходимую Василию для покупки M плиток шоколада.

Примеры

№	Входные данные	Выходные данные
1	2 5 4 9 2 4	12
2	4 30 6 18 2 5 3 10 7 9	130
3	1 100000 1000000000 100000	100000000000000

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

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

Очередь в душ#39369

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

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (2*i - 1)-й человек в очереди (на текущий момент) общается с (2*i)-м.
Рассмотрим этот процесс подробнее. Обозначим людей цифрами от 1 до 5. Пусть изначально очередь имеет вид 23154 (человек 2 стоит в начале очереди). Тогда перед открытием душа 2 общается с 3, 1 общается с 5, 4 ни с кем не общается. Затем 2 заходит в душ. Пока 2 принимает душ, 3 и 1 общаются, а также 5 и 4 общаются. Затем 3 заходит в душ. Пока 3 принимает душ, 1 и 5 общаются, 4 ни с кем не общается. Затем 1 заходит в душ, а пока он принимает душ, 5 и 4 общаются. Затем 5 заходит в душ, а затем 4 заходит в душ.

Известно, что если студенты i и j общаются, то радость студента i увеличивается на g_i,j, а радость студента j увеличивается на g_j,i. Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

Сегодня возле душа выстроилась очередь ровно из 5 студентов. Найдите максимально возможную суммарную радость этих студентов.

Входные данные
Входные данные состоят из пяти строк, в каждой строке записано пять целых чисел разделенных пробелом: j-е число в i-й строке обозначает g_i,j (0 ≤ g_i,j≤ 10⁵). Гарантируется, что g_i,i = 0 для всех i.
Считайте, что студенты пронумерованы от 1 до 5.

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

Перестановки Рекурсивный перебор

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

Задача о назначениях lite#39368

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

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

Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

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

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

Все перестановки#39367

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

Входные данные
В первой строке дано натуральное число n (1 <= n <= 7).

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

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

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

Гость из прошлого#39059

Коля Герасимов очень любит кефир, и в своём 1984 году он освоил все тонкости покупки этого чудесного напитка. Но однажды, как вам, наверное, известно, он попал в далёкий 2084 год, где покупка кефира представляет собой более сложный процесс.

Будущее будущим, а кушать хочется всегда, поэтому Коля отправился в местную молочную лавку. В 2084 году кефир продают в литровых пластиковых бутылках по a копеек за штуку и в литровых бутылках из стекла по b копеек за штуку. При этом пустую стеклянную бутылку можно сдать и получить назад c (c < b) копеек, а пластиковую бутылку сдать нельзя.

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

Входные данные
В первой строке входных данных задаётся число n (1 <= n <= 10¹⁸)— количество копеек у Коли в кармане.
В строках со второй по четвертую по одному записаны числа a, b и c (1 <= a <= 10¹⁸, 1 <= c < b <= 10¹⁸) - стоимость пластиковой бутылки с кефиром, стоимость стеклянной бутылки с кефиром и сколько копеек можно получить, сдав пустую стеклянную бутылку, соответственно.

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

Пояснения к примерам

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

Примеры

№	Входные данные	Выходные данные
1	10 11 9 8	2
2	10 5 6 1	2

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

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

Наша Таня громко плачет#39057

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

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

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

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

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

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹) - количество копий документа в папке у Тани.
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение второй команды.

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

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

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

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

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Примеры

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

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

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

Новый аэропорт#38992

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

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

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

Если самолет прилетел в 12:00, а вылетел в 12:01, то считается, что он пробыл в аэропорту 2 минуты.

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

Примеры

№	Входные данные	Выходные данные
1	6 09:00 10:07 10:20 11:35 12:00 17:00 11:00 11:30 11:20 12:30 11:30 18:15	4 1

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

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

Реклама 2#38991

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

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

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

Входные данные
Во входных данных записано сначала число N — количество покупателей, посетивших супермаркет за день(1<N<3000). Затем идет N пар натуральных чисел A_i, B_i, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<A_i<B_i<106).

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

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

Примеры

№	Входные данные	Выходные данные
1	5 1 10 10 12 1 10 1 10 23 24	5 5 10 12 23 24

Быстрая сортировка Пересечение множеств

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

Счастливого Нового Года!#38924

В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:

Бургер нулевого уровня - это котлета.
Бургер с уровнем L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.

Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.

Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?

Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 7	4	В самых нижних 7 слоях бургера второго уровня ( `ББКККБКБКККББ`) находятся 4 котлеты.
2	1 1	0
3	50 4321098765432109	2160549382716056	Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число.

Перебор Рекурсивный перебор Рекурсия

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