Алгоритмы поиска

70 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Эльфы и олени#38920
Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.

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

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

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

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

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

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

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.
Примеры
№ Входные данные Выходные данные
1 4 6
2 3 4 5
1 3 2 2 5 2		 2
1 1 2
3 4 5
Бинарный поиск по ответуБыстрая сортировкаЖадный алгоритмЭвристические методы
✓ 18✗ 571 100средняяВойти и решать
Железная дорога#38776
Вите на день рождения подарили Очень Большую Игрушечную Железную Дорогу. Она представляет собой два параллельных пути, по которым движутся поезда во встречных направлениях. В центре находится станция, а железная дорога очень большая, поэтому можно считать пути бесконечными в обе стороны. Витя расставил поезда на железной дороге и одновременно запустил их, включив электропитание. Все поезда движутся с одинаковыми скоростями в одном из двух возможных направлений. Но когда-нибудь поезда придётся остановить и убрать игру, а поскольку поезд не может развернуться и начать движение в противоположном направлении, Вите придётся самому собирать поезда руками и переносить их на станцию. Витя хочет выбрать такой момент остановки всех поездов, чтобы ему пришлось потратить минимальное число усилий для того, чтобы собрать после этого все поезда на станции вместе, то есть в этот момент времени сумма расстояний всех поездов до станции была бы минимальной.

Входные данные
Введём на железной дороге координаты, считая, что станция находится в начале координат, а все поезда первоначально находятся в целочисленных точках координатной прямой. Сами поезда также будем считать точками. За одну секунду координаты всех поездов изменяются на +1 или на −1. Поезда движутся с равными скоростями, первоначально никакие два поезда, движущиеся в одном направлении, не находятся в одной точке. Первая строка входных данных содержит целое число N — количество поездов, движущихся в положительном направлении. Вторая строка входных данных содержит целое число M — количество поездов, движущихся в отрицательном направлении. Ограничения: N > 0, M > 0, 1 <= N + M <= 105 . Следующие N строк содержат N чисел ai (|ai | <= 109 ) — первоначальные координаты поездов, движущихся в положительном направлении. Все числа ai различны и заданы в порядке возрастания. Следующие M строк содержат M чисел bj (|bj | <= 109 ) — первоначальные координаты поездов, движущихся в отрицательном направлении. Все числа bj различны и заданы в порядке возрастания.

Выходные данные
Программа должна вывести единственное целое число t — момент времени в секундах после запуска игры, в который суммарное расстояние всех поездов до станции будет минимальным. Если возможных правильных ответов несколько, то программа должна вывести любой из них. Если после старта игры суммарное расстояние всех поездов до станции будет всегда больше, чем в момент запуска игры, то правильным ответом будет t = 0.
 
Пример
№ Входные данные Выходные данные Пояснение
1 3
2
-5
-2
4
1
4		 2 В примере из условия 3 поезда движутся в положительном направлении, 2 поезда движутся в отрицательном направлении. Начальные координаты поездов, движущихся в положительном направлении равны −5, −2, 4, движущихся в отрицательном направлении равны 1 и 4. Запишем, что при t = 0 координаты поездов (−5, −2, 4, 1, 4). Суммарное расстояние всех поездов до станции равно 16. В момент t = 1 координаты поездов будут (−4, −1, 5, 0, 3), суммарное расстояние до станции равно 13. В момент t = 2 координаты поездов будут (−3, 0, 6, −1, 2), суммарное расстояние до станции равно 12. В момент t = 3 координаты будут (−2, 1, 7, −2, 1), суммарное расстояние до станции равно 13. Ответ на этот тест t = 2.
Вывод формулыПорядковые статистики
✓ 37✗ 101900средняяВойти и решать
Не был предателем ...#38775
Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то способах коммуницировать заранее. Таких людей называют заговорщиками.
Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками. Помогите Грише решить эту задачу.

Входные данные
В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования. Во второй строке записана строка S, её длина также не превосходит 300. В третьей строке записано целое число N, 1 <= N <= 5 × 106 — количество повторений строки S. Все строки состоят только из заглавных английских букв.

Выходные данные
Программа должна вывести единственное целое число — количество вхождений строки T в строку S, повторённую N раз. Под одним вхождением подразумевается один способ выбрать подстроку, то есть несколько подряд идущих символов строки, совпадающих со строкой T, не меняя порядок следования этих символов.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 MON
AMONGUS
3		 3  
2 ABA
BABA
3		 5 Если строку BABA повторить 3 раза, получится BABABABABABA.
В полученной строке подстрока ABA встречается 5 раз:
BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA, BABABABABABA
Вывод формулыПоиск подстроки в строке
✓ 22✗ 2001 000средняяВойти и решать
Чет-нечет#38474
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

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

Выходные данные
Выведите одно целое число - N-й элемент последовательности.
Примеры
№ Входные данные Выходные данные
1 1 1
2 4 5
"Длинная" арифметикаБинарный поиск по ответу
✓ 19✗ 1021 000средняяВойти и решать
Выбор цветов для букета#38384
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.

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

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 109 , 1 ≤ m ≤ 100 000) — требуемое 
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа ai и bi (0 ≤ ai , bi ≤ 109 ) — увеличение счастья от первого цветка 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средняяВойти и решать
Сложите конфетки#38347
Васю угостили конфетами, а он решил частью конфет поделиться со своим младшим братом Петей. Однако он хочет разделить конфеты не поровну, а по-братски.

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

Если останется одна кучка, то Вася все конфеты съест сам, а если две — то конфеты из первой кучки он съест сам, а из второй кучки отдаст Пете.

Напишите программу, которая по исходному распределению конфет в кучках определит, чем закончится Васина игра.

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

Во входном файле задано сначала число K (1≤K≤105). Затем идет K пар чисел Ai, Ni (1≤Ai≤100, 1≤Ni≤108). Общее количество кучек так же не превысит 108.

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

 
2 1
1 7		 1
7		 Изначальноу нас 7 кучек по 1 конфете в каждой. После первого перекладывания получится следующая конфигурация:
2 1 1 1 1 2
После второго:
3 1 3
После третьего останется одна кучка с 7 конфетами.
3 5
1 1
2 1
3 1
4 1
5 2		 2
15 5		 Изначально имеется 6 кучек:
1 2 3 4 5 5
После первого перекладывания получим:
3 3 4 6 4
После второго:
6 4 9 1
После третьего:
5 5 10
Наконец, получим:
15 5
"Два указателя"
✓ 2✗ 561 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 <= 105). i-ая статья процитирована ci раз (0 <= ci <= 105).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

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

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

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

Выходные данные
Максимальный 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 такими числами являются 210 = 102, 2410 = 110002.
Для того, чтобы пополнить свою коллекцию, Роман хочет найти n-ое в порядке возрастания такое число. Поскольку n он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Входные данные: Первая строка содержит два целых числа (1 <= n <=1015, 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-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.
Обе части рапорта записываются аналогично, каждая на своей части рулона. Одна буква слова занимает ровно одну клетку. Первое слово записывается в первой строке рулона, начиная с самой левой клетки этой части рулона. Каждое следующее слово, если это возможно, должно быть записано в той же строке, что и предыдущее, и быть отделено от него ровно одной пустой клеткой.
Иначе, оно пишется в следующей строке, начиная с самой левой клетки. Если ширина части рулона меньше, чем длина какого-то слова, которое должно быть написано в этой части, написать эту часть рапорта на части рулона такой ширины невозможно.
Гарантируется, что можно провести вертикальную черту так, что обе части рапорта возможно написать. Верс хочет провести вертикальную черту так, чтобы длина рулона, которой хватит, чтобы написать рапорт, была минимальна. Помогите ей найти эту минимальную длину.
 
Входные данные: 
- в первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- в следующей строке дано n целых чисел ai — длина i-го слова первой части рапорта \(1 <= a_i <= 10^9\);
- в следующей строке дано m целых чисел bj — длина 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средняяВойти и решать
Имена#33141
На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.
 
Пусть отец по имени X и мать по имени Y выбирают имя своему новорожденному ребенку. Так как в таукитянских школах учеников часто вызывают к доске в лексикографическом порядке имен учеников, то есть в порядке следования имен в словаре, то они хотят выбрать своему ребенку такое имя, чтобы оно лексикографически следовало как можно позже.
 
- Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;
- первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

Требуется написать программу, которая по именам отца и матери находит лексикографически наибольшее имя для их ребенка.
 
Входные данные
Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более 105 букв.
 
Выходные данные
Выходной файл должен содержать искомое лексикографически наибольшее из возможных имен ребенка. В случае, если подходящего имени для ребенка не существует, выходной файл должен быть пустым.
 
Ввод Вывод
abcabca
abcda
 ca
ccba
accbbaa
 ccba
"Два указателя"
✓ 3✗ 231 100средняяВойти и решать
Кассы#33140
На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.
 
Входные данные
Сначала вводится одно целое число N (0<N<=10000).
 
В каждой из следующих N строк через пробел расположены 6 целых чисел, первые три из которых обозначают время открытия кассы в часах, минутах и секундах (часы — целое число от 0 до 23, минуты и секунды — целые числа от 0 до 59), оставшиеся три — время закрытия в том же формате. Числа разделены пробелами.
 
Время открытия означает, что в соответствующую ему секунду касса уже работает, а время закрытия — что в соответствующую секунду касса уже не работает. Например, касса, открытая с 10 ч 30 мин 30 с до 10 ч 35 мин 30 с, ежесуточно работает 300 секунд.
 
Если время открытия совпадает с временем закрытия, то касса работает круглосуточно. Если первое время больше второго, то касса начинает работу до полуночи, а заканчивает — на следующий день.
 
Выходные данные
Требуется вывести одно число — суммарное время за сутки (в секундах), на протяжении которого работают все N касс.
 
Ввод Вывод
3
1 0 0 23 0 0
12 0 0 12 0 0
22 0 0 2 0 0
 7200
2
9 30 0 14 0 0
14 15 0 21 0 0
 0
2
14 0 0 18 0 0
10 0 0 14 0 1
 1
"Два указателя"
✓ 17✗ 90800средняяВойти и решать
Квадраты и кубы#33122
В лаборатории теории чисел одного университета изучают связь между
распределением квадратов и кубов натуральных чисел.
Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных
чисел от a до b, включительно. Будем называть k-плотностью этого множества количество
пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2– y3| ≤ k.
Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как
подходят следующие пары:

 x = 1, y = 1, |x2– y3| = |1 – 1| = 0;
 x = 3, y = 2, |x2– y3| = |9 – 8| = 1;
 x = 5, y = 3, |x2– y3| = |25 – 27| = 2.
 
Требуется написать программу, которая по заданным натуральным числам a и b, а
также целому неотрицательному числу k, определяет k-плотность множества натуральных
чисел от a до b, включительно.
Формат входных данных
Входные данные содержат три строки. Первая строка содержит натуральное число a,
вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное
число k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).
Формат выходных данных
Выходные данные должны содержать одно целое число: искомую k-плотность
множества натуральных чисел от a до b, включительно.
 
Ввод Вывод
1
30
2		 3
Арифметические алгоритмы (Теория чисел)Вещественные числаЛинейный поиск
✓ 6✗ 661 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 ≤ 1015, a + b + c ≥ 1).

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






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

Программа должна работать быстрее, чем за линейный поиск
 
Входные данные
Одно целое число N (1 <= N <= 109).
 
Выходные данные
Выведите одно целое число - N-й элемент последовательности.
 
Ввод Вывод
1 1
4 5
Бинарный поиск по ответу
✓ 25✗ 221 000средняяВойти и решать
Очень легкая задача - 2#33092
Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются M ксероксов, каждый из которых копирует лист за х секунд. (Разрешается использовать все ксероксы одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

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


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


Формат выходных данных
Выведите одно число – минимальное время в секундах, необходимое для получения N копий.
 
Ввод Вывод
8 3
2 3 7		 9
Бинарный поиск по ответу
✓ 25✗ 20800средняяВойти и решать
Распродажа#32981
В магазине проходит новогодняя распродажа – цены всех товаров снижены на 25 %. Оказалось, что первоначально все цены делились на 4, поэтому после снижения цен все цены также выражаются целым числом. Товаровед вечером перед распродажей снял ценники со всех товаров и напечатал для каждого товара ещё один ценник со сниженной ценой. Он оставил все ценники на столе, рассчитывая утром их развесить. Но, придя утром в магазин, он обнаружил, что уборщица смешала все ценники вместе, и теперь ему нужно отделить старые ценники от новых.
Помогите ему решить эту задачу. 
 

Входные данные
Первая строка входных данных содержит общее количество ценников N, 2 <= N <= 105, N – чётное число. Следующие N строк содержат целые положительные числа, не превосходящие 109, идущие в порядке неубывания по одному в строке – числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны,то есть решение существует.

Выходные данные
Программа должна вывести N/2  целых чисел в порядке неубывания – стоимости товаров после понижения цен.

 
Примеры
№ Входные данные Выходные данные Примечание
1
6
30
40
42
45
56
60
30
42
45
До распродажи цены товаров были 40, 56, 60, после снижения цены
на эти товары стали равны 30, 42, 45.
"Два указателя"Словари
✓ 115✗ 595800средняяВойти и решать
Робот#31782
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
 
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из N операций.
 
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
 
Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.
 
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
 
Входные данные
В первой строке записано число K > 0 - количество операций, которые можно записать в память робота.
Вторая строка состоит из N > K строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой (N <= 200000).
 
Выходные данные
Выведите единственное целое число - количество экономически целесообразных способов использования робота.
 
Ввод Вывод
2
zabacabab
 5
2
abc		 0
"Два указателя"
✓ 54✗ 1331 000средняяВойти и решать
Тихий дон №2#29640

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с Григорием. 

Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.
 
Входные данные
В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).
Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

Входные данные
Требуется вывести ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 5 3 3
1 -1 2 -2 3		 3
"Два указателя"Префиксные суммы(минимумы, ...)
✓ 94✗ 501800средняяВойти и решать
Поделиться
Класснуть