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

Исследование зеркальных цветов#44936

Члены экипажа космического корабля «Пегас» приземлились на третьей планете Системы Медуза, для изучения зеркальных цветов. Их корабль приземлился в начале узкого поля фермы, на которой выращивают цветы. Зеркальные цветы начинают прорастать после полуночи. Любезные работники фермы предоставили экипажу план прорастания цветов в виде точки и времени прорастания. Экипажу корабля необходимо улетать с планеты в следующую полночь. Исследовательская группа корабля может передвигаться по планете с максимальной скоростью v_max. На исследование одного цветка группе необходимо время d. Исследовать цветок необходимо сразу весь, нельзя будет к нему вернуться позже. Цветы прорастают тем позже, чем дальше они расположены от начала поля. В одной точке прорастает только один цветок, и каждый цветок прорастает в свой момент времени. Нет двух цветков, которые бы проросли одновременно.
Команда экипажа хочет определить момент времени, когда исследовательская группа сможет вернуться на корабль, исследовав все цветы и затратив на исследование как можно меньше времени.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит 2 целых числа через один пробел: v_max (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Вторая строка содержит одно число N – количество цветов (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
Далее идут N строк, в каждой из которых записано по два числа через пробел: целое число x_i – расстояние от цветка до начала поля (в сантиметрах), 0 <= x_i <= 32767, и число t_i – момент прорастания цветка (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

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

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можно считать, что исследовательская группа не меняет направления движения до тех пор, пока не дойдет до последнего цветка.

Примеры

№	Входные данные	Выходные данные
1	3 1 1 100 00:01	01:08

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

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

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

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

✓ 23✗ 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средняяВойти и решать

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

Интересные числа#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✗ 99900средняяВойти и решать

K-квест#34879

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

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

Ввод	Вывод
5 3 -2 2 -1 2 4	2 4
7 1 1 -1 1 -1 1 -1 2	5 5
4 3 2 2 2 2	-1

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

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

*Рапорт#33253

Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из a_i букв, вторая — m слов, j-е из которых состоит из b_j букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.

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

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

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

Входные данные:
- в первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));

- в следующей строке дано n целых чисел a_i — длина i-го слова первой части рапорта \(1 <= a_i <= 10^9\);

- в следующей строке дано m целых чисел b_j — длина j-го слова второй части рапорта \(1 <= b_j <= 10^9\).

Гарантируется, что возможно провести черту так, что обе части рапорта возможно написать.

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

Примеры

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

Примечание

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

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

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

Калитка в заборе#33139

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали N столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум W. Теперь им придётся выкапывать некоторые столбы.

Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.

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

Первая строка содержит два целых числа N и W — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что 0<=N<=30000 и что 0<=W<=60000.

Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа L и R — координаты левого и правого конца этой стороны (LR). Далее следуют N чисел — координаты вкопанных столбов. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 30000. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.

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

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

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

Ввод	Вывод
3 2 2 6 3 4 5	1 2
3 2 1 6 4 3 5	0
3 5 1 7 5 3 4	3 2 1 3

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

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

Старая книга#33126

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

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

Книга содержит несколько страниц, каждая страница содержит либо текст, либо

иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги

пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма

номеров страниц с текстом равна s.

К сожалению, ни общее количество страниц в книге, ни количество иллюстраций

установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое

минимальное количество иллюстраций могло быть в книге.

Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание

(буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая

иллюстрацию):

- И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;

- И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;

- И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.

Минимальное количество иллюстраций равно 3.

Требуется написать программу, которая по заданным целым числам k и s определяет

минимальное количество иллюстраций, которое могло быть в книге.

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

Первая строка входных данных содержит целое число k (0 ≤ k ≤ 10⁹).

Вторая строка входных данных содержит целое число s (k + 1 ≤ s ≤ 10¹²).

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

Требуется вывести одно целое число — минимальное количество иллюстраций в

книге.

Ввод	Вывод
1 8	3

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

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

Улучшение успеваемости#33121

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

Примеры округления оценок приведены в таблице.

Оценки на уроках	Среднее арифметическое	Итоговая оценка
2, 3, 5	\({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\)	3
3, 3, 4, 4	\({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\)	4
5, 5, 5, 3, 5	\({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\)	5

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок.Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

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

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 10¹⁵, a + b + c ≥ 1).

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

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

Ввод	Вывод
2 0 0	2

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

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

Чет-нечет#33096

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

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

Одно целое число N (1 <= N <= 10⁹).

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

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

Ввод	Вывод
1	1
4	5

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

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

Очень легкая задача - 2#33092

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

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

Формат входных данных
В первой строке записаны да натуральных числа N, M разделенные пробелом (1 ≤ N, M ≤ 2•10⁸), во второй строке записаны скорости всех ксероксов - x (1 ≤ x ≤ 10 )

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

Ввод	Вывод
8 3 2 3 7	9

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

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

Двоичный поиск для монотонной функции (С++)#27283

Дано натуральное число x. Вычислите кубический корень из числа.

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

Число x – натуральное, не превосходящее \(10^6\).

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

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

№	Входные данные	Выходные данные
1	2	1.259921

Бинарный поиск значения функции

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