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

Бесконечная Дженга#44658

Громозека и Алиса придумали правила игры в бесконечную Дженгу.
В бесконченой Дженге каждый ход заключается в одном из двух действий на выбор игрока:

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

Первым ходом всегда устанавливается один брусок в пустую башню. Формально говоря, после первого хода башня состоит из одного бруска. Если после какого-то хода башня оказалась пустая (не имеет ни одного бруска), то в такую башню можно только установить брусок. Брусков для установки на башню у Алисы и Громозеки бесконечное количество.

Например, можно выполнить такую последовательность действий при игре:

1) установить один брусок на башню;
2) установить два бруска на башню;
3) убрать один брусок из башни;
4) убрать один брусок из башни;
5) установить три бруска на башню;
6) убрать один брусок из башни;
7) установить четыре бруска на башню;
8) убрать один брусок из башни;
9) установить пять брусков на башню.

После 9 ходов, количество брусокв в башне в итоге будет равно 11, а по ходу игры из башни извлекли 4 бруска.

Известно, что Алиса и Громозека сделали n ходов в придуманной игре, при этом после всех выполненных ходов, количество брусков в башне равнялось k. Найдите суммарное количество убранных Алисой и Громозекой с башни брусков за все n ходов. Гарантируется, что для заданных n и k ответ существует.

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

В первой строке входных данных заданы два целых числа n и k (1<=n<=10⁹; 0<=k<=10⁹) - суммарное количество ходов и количество брусков в башне после n ходов. Гарантируется, что для заданных n и k ответ существует.

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

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

Примеры

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

Бинарный поиск по ответу

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

Номера равных заданному#44657

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

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

В первой строке вводится одно натуральное число N, не превосходящее 10⁵: количество чисел в массиве.

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

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

В четвертой строке вводится M натуральных чисел, не превосходящих 10⁹.

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

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

Если в массиве нет такого числа, выведите в соответствующей строке два нуля, разделенных пробелом.

Примеры

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

Бинарный поиск в массиве

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

2022#44582

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

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

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

Выходные данные
Выведите одно число - количество подходящих пар.

Примечание

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

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5).

Примеры

№	Входные данные	Выходные данные
1	2 1 2022	0
2	4 1000 1022 1001 1021	2
3	5 700 1 1 2021 2021	4

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

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

Автомобиль "Пантера"#44581

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, на проезде на парковку университета установлен шлагбаум, поэтому скорость автомобиля после того, как он проехал ровно d метров должна быть равна 0.

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

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

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

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

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.
Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

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

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

Примеры

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

Бинарный поиск по ответу

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

Автомобиль "Пантера" - 2#44505

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, у проезда на парковку университета установлен датчик движения: если скорость проезжающего транспортного средства будет превышать s, то администрация университета выпишет нарушителю дисциплинарное взыскание. Конечно, Глеб не хочет его получить, поэтому при въезде в университет, когда автомобиль проехал все d метров его скорость x должна быть не больше s.

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

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

В двух строках заданы два целых числа - d, s (1 <= d <= 10¹⁸, 0 <= s <= 10¹⁸), расстояние до университета и ограничение на конечную скорость.

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра.

Таким образом, он потратит 2 секунды, и его конечная скорость будет равно 1 м/с, что не превышает s.

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

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с, что не превышает s.

Примеры

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

Бинарный поиск по ответу

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

Подстрока#43798

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

Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

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

Примеры

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

"Два указателя"Бинарный поиск по ответу Строки

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

Книги Томми#43351

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге a_i страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

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

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·10⁵) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a₁, a₂, ... a_n (1 <= a₁<= 10¹⁰), где a_i равно количеству страниц в i-й книге. В третьей строке следует последовательность d₁, d₂, ... d_m (1 <= d_j<=a₁+ a₂+...+ a_n), где d_j равно общему числу страниц, прочитанных Томми к j-му дню. Все d_j заданы в порядке возрастания.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= a_k), на которой остановился Томми в текущий день.

Примеры

№	Входные данные	Выходные данные
1	3 6 10 15 12 1 9 12 13 15 17	1 1 1 9 2 2 2 3 2 5 2 7
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 2 9999999994

"Два указателя"Бинарный поиск Задача на реализацию

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

Межрегиональная олимпиада#40022

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает c_i баллов.

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

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

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

Последующие n строк содержат описания задач, по три числа на каждой строке: si момент появления i-й задачи в минутах, t_i время, отведенное на ее решение в минутах, и ci сколько баллов получит участник за решение этой задачи (1 ≤ s_i, t_i, c_i ≤ 10⁹).

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

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

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

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

Примеры

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

Бинарный поиск в массиве Динамическое программирование Жадный алгоритм

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

Ресторан#39963

Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета l_i и моментом конца r_i (l_i ≤ r_i).

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

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

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел l_i, r_i (0 ≤ l_i ≤ r_i ≤ 10⁹).

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

Примеры:

Входные данные	Выходные данные
2 7 11 4 7	1
5 1 2 2 3 3 4 4 5 5 6	3
6 4 8 1 5 4 7 2 5 1 3 6 8	2

Бинарный поиск в массиве Динамическое программирование Использование сортировки

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

Чтение вслух#39673

Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого.
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?

Входные данные:
В первой строке дана строка S (1 <= |S| <= 10⁵), состоящая из строчных латинских букв - надпись из газетной вырезки.
В следующей строке дано натуральное число q - количество запросов.
В следующих q строках дано по два натуральных числа i и j - позиции, с которых начинают читать Том Сойер и Гекльберри Финн соответственно.

Выходные данные:
Выведите q строк, в каждой из которых должно быть одно целое число - количество символов, совпадающих при чтении подстрок, начинающихся с i-ого и j-ого символа.

Примеры:

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

Бинарный поиск по ответу Префиксные суммы(минимумы, ...)Хеш

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

Гармоничная последовательность#39381

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

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

Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).

Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .

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

Примеры

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

Бинарный поиск Префиксные суммы(минимумы, ...)

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

Социальное дистанцирование#39380

Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10⁵) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10⁵), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10¹⁸. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.

Примеры

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

Бинарный поиск по ответу

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

Эльфы и олени#38920

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

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

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел a_i – строптивость оленей ( 0 ≤ a_i ≤ 10⁹). В третьей строке записаны n целых чисел b_i – темперамент эльфов ( 0 ≤ b_i ≤ 10⁹).

Выходные данные
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: d_i, e_i, 1, e_i, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

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

Примеры

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

Бинарный поиск по ответу Быстрая сортировка Жадный алгоритм Эвристические методы

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

Чет-нечет#38474

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Входные данные
Одно целое число N (1 ≤ N ≤ 10¹⁰⁰).

Выходные данные
Выведите одно целое число - N-й элемент последовательности.

Примеры

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

"Длинная" арифметика Бинарный поиск по ответу

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

Выбор цветов для букета#38384

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

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a_i, а от каждого следующего цветка
такого вида она становится счастливее на b_i. То есть, если в букете x_i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a_i + (x_i − 1) · b_i.

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — требуемое
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a_i и b_i (0 ≤ a_i , b_i ≤ 10⁹ ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

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

Примеры

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

Бинарный поиск в массиве Префиксные суммы(минимумы, ...)

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

Словарь#38196

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

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

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

Примеры

№	Входные данные	Выходные данные
1	whatcanido 6 a an can do i what	what can i do

Бинарный поиск в массиве Динамическое программирование: один параметр

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

Acowdemia#38128

Беси опубликовала N статей (1 <= N <= 10⁵). i-ая статья процитирована c_i раз (0 <= c_i<=10⁵).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

Чтобы повысить свой h-индекс, Беси планирует написать K обзорных статей (0 <= K <= 10⁵), каждая из которых цитирует несколько ее прошлых статей. Беси имеет право цитировать не более L статей в каждом обзоре (0 <= L <= 10⁵). Конечно, никакая статья не может цитироваться более одного раза в одном обзоре (однако статья может цитироваться в нескольких обзорах).

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

Входные данные
Первая строка содержит N, K, L. Вторая строка содержит N разделённых пробелом целых чисел c₁,...,c_N.

Выходные данные
Максимальный h-индекс.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 4 1 1 100 1 1	3	В этом примере Беси может написать 4 обзорные статьи, в каждой из которых можно процитировать не более 1 статьи. Если процитировать первую и третью статьи по 2 раза, её h-индекс станет 3.
2	4 1 4 1 100 1 1	2	В этом втором примере Беси может написать не более одной статьи. Если Беси процитирует любую из её 1,2 или 4 статью хоть раз, её h-индекс станет 2.

Алгоритмы сортировки Бинарный поиск по ответу

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

Жевательные ленты#34966

Громозека с планеты Чумороза впечатлителен, раним, легко приходит в уныние и начинает плакать, попутно выпуская из ноздрей едкий дым.
Громозека привез со своей родной планеты N штук жевательных лент, которую так любят земные дети. Он хочет поделить все ленты между K детьми. Но, оказывается, если у детей размер жевательной ленты будет различным, то они начнут ругаться и ссориться. В этот момент Громозека придёт в уныние.
Помогите Громозеке поделить все жевательные ленты таким образом, чтобы из них можно было набрать K штук одинаковых. Радость детей прямо пропорциональна длине жевательных лент. Громозека хочет, чтобы дети получили как можно больше радости.

Входные данные
В первой строке заданы два числа - N (1 <= N <= 10001) и K (1 <= K <= 10001). Далее, в каждой из последующих N строк, записано по одному числу - длина каждой привезенной жевательной ленты. Длина ленты задана в сантиметрах. Все длины лежат в интервале от 1 до 10⁷ сантиметров включительно.

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

Примеры

№	Входные данные	Выходные данные
1	4 11 802 743 457 539	200

Бинарный поиск по ответу

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

Интересные числа#34923

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 2₁₀ = 10₂, 24₁₀ = 11000₂.
Для того, чтобы пополнить свою коллекцию, Роман хочет найти n-ое в порядке возрастания такое число. Поскольку n он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Входные данные: Первая строка содержит два целых числа (1 <= n <=10¹⁵, 2 <= k <= 10).

Выходные данные: Выведите n-ое в порядке возрастания число, запись которого в системе счисления с основанием k заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.

Примеры

входные данные
1 2

выходные данные
2

входные данные
10 10

выходные данные
110

Бинарный поиск по ответу

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

Провода#34922

Дано N отрезков провода длиной L₁, L₂, ..., L_N сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Формат входных данных
В первой строке находятся числа N и K. В следующих N строках L₁, L₂, ..., L_N, по одному числу в строке.

Ограничения

1 <= N <= 10 000,
1 <= K <= 10 000,
100 <= L_i <= 10 000 000,
все числа целые.

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

Бинарный поиск по ответу

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