Али–Баба попал в пещеру, в которой находятся \(N\) предметов. У каждого предмета есть стоимость, при этом предметы могут быть бесполезными и даже вредными — их стоимость отрицательна. Али–Баба может унести не более \(M\) предметов. Определите, какие предметы следует выбрать Али–Бабе так, чтобы их стоимость была максимально возможной.
Первая строка входных данных содержит два числа \(N\) и \(M\) (\(0\le N\le 10^5\), \(0\le M\le 10^5\)) — количество предметов в пещере и количество предметов, которое может унести Али–Баба.
В следующей строке записаны \(N\) целых чисел \(a_i\) (\(-10^9\le a_i\le 10^9\)) — стоимости предметов в пещере.
Программа должна вывести не более \(M\) различных чисел от \(1\) до \(N\) — номера предметов, которые выберет Али–Баба.
| Ввод | Вывод |
|---|---|
7 3 |
1 2 4 |
Дети в детском саду изучают английский алфавит. Они встают в круг и по очереди называют буквы. Первый ребенок в ряду громко называет первую букву алфавита — A. Второй должен назвать B, третий — C и так далее. Всего детей в группе, как и букв в английском алфавите, ровно 26.
Дети учат буквы подряд и каждый из них знает несколько первых букв алфавита. Кто-то, возможно, знает только букву A, кто-то буквы A, B, C, D, а кто-то может знать и весь алфавит. Ребёнок может назвать только ту букву, которую он знает.
Расставьте детей так, чтобы они могли назвать весь алфавит целиком, или определите, что это сделать нельзя.
Программа получает на вход строку из 26 заглавных букв английского алфавита. \(i\)-я буква этой строки обозначает, какую последнюю букву алфавита знает \(i\)-й ребёнок в группе.
Если можно расставить детей так, чтобы они назвали весь алфавит, выведите YES. В следующей строке выведите
перестановку чисел от 1 до 26 — порядковые номера детей в расстановке, позволяющей назвать им весь алфавит.
Если расставить детей невозможно, программа должна вывести одно слово NO.
| Ввод | Вывод |
|---|---|
ZYXWVUTSRQPONMLKJIHGFEDCBA |
YES |
YYYYYYYYYYYYYYYYYYYYYYYYYY |
NO |
Каждый из \(n\) выпускников магической школы получает посох силы \(a_i\) и кольцо силы \(b_i\). При этом уровень магической силы выпускника определяется отношением \(\frac{a_i}{b_i}\).
В распоряжении государственной экзаменационной комиссии есть \(s\) посохов и \(r\) колец. Комиссия хочет раздать выпускникам кольца и посохи так, чтобы суммарная магическая сила выпускников была бы максимальной.
Первая строка входных данных содержит три числа \(n\), \(s\), \(r\) (\(1\le n\le 10^5\), \(n\le s\le 10^5\), \(n\le r\le 10^5\)). Вторая строка содержит \(s\) чисел — магические силы посохов, третья строка содержит \(r\) чисел — магические силы колец. Все силы — целые, положительные, не превосходят \(10^6\).
Программа должна вывести \(n\) строк. \(i\)-я строка содержит два числа — номер посоха и номер кольца, которые получит \(i\)-й выпускник.
| Ввод | Вывод |
|---|---|
2 4 3 |
1 2 |
На очередном уровне неважно какой компьютерной игры вам противостоят \(n\) драконов. У каждого дракона есть его сила \(s_i\) и бонус \(b_i\). Чтобы победить дракона, ваша сила должна быть больше, чем \(s_i\), а после победы над драконом ваша сила увеличивается на \(b_i\).
Первоначально ваша сила равна \(s\). Вы сами можете выбирать, в каком порядке вы будете побеждать драконов. Определите максимальное количество драконов, которое вы можете победить.
Первая строка входных данных содержит два числа: количество драконов \(n\) и начальное значение вашей силы \(s\). Далее следует \(n\) строк, каждая строка содержит два целых положительных числа \(s_i\) и \(b_i\), не превосходящих \(10^9\).
Программа должна вывести одно целое число — максимальное число драконов, которое вы можете победить.
Пояснение. В примере из условия ваша сила равна 10. Сначала нужно победить третьего дракона, после этого ваша сила станет равна 15. Затем нужно победить первого дракона, после этого ваша сила станет равна 20. Победить второго дракона не получится, потому что его сила также равна 20.
| Ввод | Вывод |
|---|---|
3 10 |
2 |
На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Вам даны номера маршрутов автобусов, отправляющихся по порядку в течение \(n\) минут.
Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определенным маршрутом. При этом не учитываются пассажиры, которые приходят после отправления последнего автобуса данного маршрута, а также пассажиры, приходящие раньше отправления первого автобуса данного маршрута. То есть вам нужно найти самый длинный интервал между двумя автобусами одного маршрута.
Программа получает на вход число \(n\) (\(2\le n\le 10^5\)) . В следующей строке записаны \(n\) чисел \(a_i\) (\(1\le a_i\le 10^9\)) —номера автобусов в порядке отправления. Гарантируется, что любое значение в этом списке повторяется не менее двух раз.
Программа должна вывести одно число — максимальный интервал между двумя автобусами одного маршрута.
| Ввод | Вывод |
|---|---|
8 |
4 |
4 |
1 |
Есть распечатанный список имён, который забыли отсортировать перед печатью. Теперь мы хотим отсортировать его при помощи ножниц и скотча: можно разрезать список на несколько частей, переставить и склеить полученные части. Определите минимальное число разрезов, которое необходимо сделать для этого.
Список напечатан на одном листе бумаги, одно имя занимает одну строку.
Первая строка входных данных содержит одно целое число \(n\) (\(1\le n\le 10^5\)) — количество имён в списке. Следующие \(n\) строк содержат имена, по одному имени в строке. Имена могут состоять из заглавных и строчных английских букв, символов «.», «-» и пробела. Каждое имя содержит не более 20 символов. Имена сравниваются в лексикографическом порядке, символы сравниваются по ASCII-кодам.
Выведите одно число — минимальное число разрезов, которое необходимо выполнить для сортировки списка.
Обратите внимание, что вам необходимо считывать строки при помощи getline, при этом после
считывания значения \(n\) нужно сделать дополнительный getline, чтобы считать конец строки после числа \(n\).
| Ввод | Вывод |
|---|---|
4 |
2 |
Вам дан массив из \(n\) целых различных чисел. Вам нужно его отсортировать, но вы можете выполнить один раз одну операцию: взять подотрезок этого массива и развернуть его в обратном порядке. Определите, сможете ли вы отсортировать массив при помощи такой операции.
Первая строка входных данных содержит целое число \(n\) (\(1\le n\le 10^5\)) — размер массива. Следующая строка содержит \(n\) различных целых положительных чисел \(a_i\), не превосходящих \(10^9\).
Если отсортировать массив при помощи одного разворота подотрезка можно, выведите слово YES.
В следующей строке выведите два числа \(l\) и \(r\) (\(1\le l\le r \le n\)) — индексы первого и последнего
элемента разворачиваемого подотрезка массива. Если отсортировать массив невозможно, выведите одно слово NO.
| Ввод | Вывод |
|---|---|
3 |
YES |
4 |
YES |
4 |
NO |
2 |
YES |
Вы хотите купить себе ноутбук. У вас есть выбор — купить ноутбук подороже и помощнее или подешевле и послабее. Для начала вы хотите составить список имеющихся в продаже интересных ноутбуков.
В продаже есть \(n\) моделей ноутбуков. Каждый ноутбук характеризуется двумя числами: ценой \(p_i\) и мощностью \(s_i\). Все стоимости различны, все мощности также различны.
Назовём \(i\)-й ноутбук неинтересным, если существует ноутбук \(j\) такой, что \(p_j\lt p_i\), а \(s_j\gt s_i\), то есть ноутбук \(j\) будет дешевле и мощнее. Все остальные ноутбуки назовём интересными. То есть для интересных ноутбуков выполнено правило, что чем больше мощность, тем выше цена. Определите, какие модели ноутбуков являются интересными.
Программа получает на вход количество моделей ноутбуков \(n\) (\(1\le n\le 10^5\)). Следующие \(n\) строк содержат по два целых положительных числа \(p_i\) и \(s_i\), не превосходящих \(10^9\).
Программа должна вывести номера интересных ноутбуков в порядке возрастания.
| Ввод | Вывод |
|---|---|
4 |
2 4 |