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

Секретная последовательность#43349

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

первым числом слева записано число a₁;
первым числом справа записано число a₂;
вторым числом слева (после a₁) записано число a₃;
вторым числом справа (то есть перед числом a₂) записано число a₄;
все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.

Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел a_i (1 <= a_i <= 10⁹) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.

Примеры

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

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

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

Сортировщик Томми#43034

У Томми есть детская игрушка «cортировщик», с расположенными подряд n колышками. На каждом колышке сейчас не более одного диска (то есть на каком-то колышке диск есть, а на каком-то его нет). Томми хочет переложить имеющиеся диски на колышках таким образом, чтобы они образовывали неубывающую последовательность при просмотре слева направо. То есть на каждом следующем колышке количество дисков должно быть не меньше, чем на предыдущем. Какое минимальное количество дисков Томми необходимо переложить?

Обратите внимание, что какие- то колышки по окончанию сортировки могут быть пустыми. Какие-то колышки могут содержать более 1 диска.

Входные данные
Программа получает на вход в первой строке целое число n (1 <= n <= 10⁵), количество колышек на «cортировщике». Следующая строка содержит n целых чисел a₁, a₂, ... a_n – наличие диска на соответствующем колышке (0 <= a_i <= 1). число 0 означает, что на i-м колышке нет диска, 1 – диск есть.

Выходные данные
Выведите ответ на задачу.

Примеры

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

"Два указателя"Жадный алгоритм Конструктив

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

Межрегиональная олимпиада#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лёгкаяВойти и решать

Подпоследовательность длиной L#39482

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. В ответе укажите сумму найденной подпоследовательности.

Входные данные
В первой строке записаны 3 числа: количество чисел N (1 <= N <= 1 000 000), L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3 1 -1 2 -2 3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3.
Ответ (для С = 3 и L = 3): 3.

"Два указателя"Префиксные суммы(минимумы, ...)

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

Найдите последовательность#38342

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

Напомним, что если мы сравниваем две последовательности, и у них первые K символов совпадают, а (K+1)-е символы отличаются, то раньше будет идти по алфавиту та, в которой (K+1)-й символ идет раньше по алфавиту. Если же одна последовательность является началом другой, то раньше по алфавиту идет более короткая из них.

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

Входные данные
В первой строке входного файла записано число N — длина исходной последовательности (1≤N≤1000). Во второй строке идет сама последовательность. Последовательность состоит только из заглавных латинских букв.

Выходные данные
В выходной файл выведите выигрышную последовательность.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 MAMA	A	Рассматриваются строки MAMA, AMA, MA, A. Выигрышная строка A
2	4 ALLO	ALLO	Выигрышной является исходная строка
3	5 BBABB	ABB

Линейный поиск

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

Поиск в строке#37856

Дана строка, в которой буква h встречается минимум два раза. Удалите из этой строки первое и последнее вхождение буквы h, а также все символы, находящиеся между ними.

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

Вводится строка.

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	In the hole in the ground there lived a hobbit	In tobbit

Поиск подстроки в строке Строки

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

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

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

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

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

Примеры

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

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

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

Провода#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,
все числа целые.

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

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

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

Управляющий совет#34775

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

Формат входных данных
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N), записанные в отдельных строках, — текущее число членов совета и число родителей в совете.

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

Пояснение к примеру
В примере совет состоит из 27 человек, из которых родители составляют 7 человек. Если в совет ввести ещё 3 родителей, то в совете станет 30 человек, из которых родителей будет 10.

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

✓ 246✗ 1 068600лёгкаяВойти и решать

Количество чисел, равное искомому#33591

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

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

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

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

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

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

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

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

Если в массиве нет такого числа, выведите 0.

Примеры

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

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

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

Ослабление флота#33252

Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из

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

Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного

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

в следующем порядке: каждый раз Кэрол будет атаковать тот корабль из неатакованных ранее,

мощность которого является медианой мощностей оставшихся кораблей.

Медиану ряда чисел Кэрол вычисляет следующим образом:

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

• Если количество чисел в ряду чётно, то медианой ряда является:

– Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.

– Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда,

если два средних равны.

Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

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

В первой строке дано одно натуральное число n — число кораблей во флоте Скруллов (1 <= n <= 10⁵).

Во второй строке содержатся n натуральных чисел ai — мощность i-го корабля (1 <= a_i <=10⁹).

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

Выведите n чисел — мощности кораблей в том порядке, в котором Кэрол будет их атаковать.

Ввод	Вывод
3 8 3 19	8 3 19
4 4 2 2 1	2 2 1 4

"Два указателя"

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

Провода#33094

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

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= L_i <= 10 000 000, все числа целые.

Программа должна работать быстрее, чем за линейный поиск

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

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

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

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

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

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

Коровы - в стойла#30709

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

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

- в первой строке вводятся числа N (\(2 < N < 10001\)) – количество стойл, и K (\(1 < K < N \)) – количество коров;
- во второй строке задаются N натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят \(10^9\)).

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

Примеры

№	Входные данные	Выходные данные
1	6 3 2 5 7 11 15 20	9

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

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

Очень легкая задача#30703

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y.
Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии. Помогите ему выяснить, какое минимальное время для этого потребуется.

Входные данные: на входе задается три натуральных числа N, x и y, разделенные пробелом (\(1 <= N <= 2 \cdot 10^8,\ 1 <= x, y <= 10\)).

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

Примеры

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

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

✓ 1 167✗ 3 112500лёгкаяВойти и решать

Дремучий лес#29481

Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.

- Судиславль находится в точке с координатами (0, 1).

- «Берендеевы поляны» находятся в точке с координатами (1, 0).

- Граница между лесом и полем — горизонтальная прямая y=a, где a — некоторое число (0 ≤ a ≤ 1).

- Скорость передвижения СЭС по полю составляет V_p, скорость передвижения по лесу — V_f. Вдоль границы можно двигаться как по лесу, так и по полю.

Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.

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

В первой строке входного файла содержатся два положительных целых числа V_p и V_f (1≤ V_p, V_f ≤ 10⁵) . Во второй строке содержится единственное вещественное число — координата по оси Oy границы между лесом и полем a (0 ≤ a ≤ 1) .

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

В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой инспекция СЭС должна войти в лес.

Ввод	Вывод
5 3 0.4	0.783310604
5 5 0.5	0.500000000

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

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

Самый младший#29446

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

Входные данные
В первой строке задается число N - число человек (0<N<=50). Во второй строке задаются года рождения N человек (N чисел).

Выходные данные
Выведите наибольший номер самого младшего человека.

Пример

№	Входные данные	Выходные данные
1	5 1904 1903 1905 1905 1903	4

Алгоритмы обработки Линейный поиск Одномерные массивы

✓ 5 314✗ 16 008300лёгкаяВойти и решать

Проверка подпоследовательности#28420

Проверить, является ли последовательность подпоследовательностью заданного массива.

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

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

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

Выходные данные
Вывести "YES" если последовательность заданная в 4-ой строке является подпоследовательность заданного массива и "NO", если не является.

Ввод	Вывод
10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 5 4 6 7 8 9 10	NO
10 1 2 3 4 5 6 7 8 9 10 9 1 2 3 5 6 7 8 9 10	YES

Пояснение.
Не путать "подпоследовательность" с "подстрокой".

"Два указателя"

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

Точки на прямой#28417

Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.

Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

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

Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 10⁹ — x-координаты точек, подаренных Пете.

Гарантируется, что координаты точек во входных данных строго возрастают.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Ввод	Вывод
4 3 1 2 3 4	4
4 2 -3 -2 -1 0	2
5 19 1 10 20 30 50	1

В первом примере нам подходит любая тройка различных точек.

Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.

В третьем примере нам подходит одна тройка: {1, 10, 20}.

"Два указателя"Комбинаторика

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

Два одинаковых массива#28345

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

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно, (1 <= N, M <= 10⁸). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 10¹⁸.

Выходные данные
Выведите ответ на задачу.

Примеры

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

"Два указателя"Хеш

✓ 815✗ 1 981500лёгкаяВойти и решать