Информатика

Тренер школьной команды программистов готовится к турниру. В школе всего \(n\) учеников, у каждого есть свой рейтинг \(p_i\) — количество очков, набранных на тренировках.

На турнир нужно отправить ровно \(k\) учеников. Сила команды оценивается как суммарный рейтинг её участников. Тренер хочет, чтобы суммарный рейтинг был максимально возможным.

Помогите тренеру определить, чему равен этот максимальный суммарный рейтинг.

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

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — общее количество учеников и размер команды.

Во второй строке — \(n\) целых чисел \(p_i\) (\(0 \le p_i \le 10^9\)), разделённых пробелами, — рейтинг каждого ученика.

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

Одно целое число — максимальный суммарный рейтинг команды.

Примечание

В первом примере нужно выбрать трёх учеников из пяти. Лучше всего взять с рейтингами 8, 5 и 3 — в сумме 16.

Во втором примере в команду идут все четверо учеников, поэтому ответ — сумма всех рейтингов.

Библиотекарь расставляет книги на полке длиной \(W\) сантиметров. У него есть \(n\) книг; \(i\)-я книга имеет размеры \(a_i \times b_i\) сантиметров.

Каждую книгу можно поставить на полку двумя способами: одной стороной к соседней книге (тогда она занимает вдоль полки \(a_i\) сантиметров) или другой стороной (тогда \(b_i\) сантиметров). Способ расстановки выбирается для каждой книги независимо.

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

Помогите ему определить это максимальное число книг.

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le W \le 10^{14}\)) — количество книг и длина полки.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры \(i\)-й книги.

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

Одно целое число — максимальное количество книг, которые можно расставить на полке.

На стройплощадку нужно перевезти доски. У бригадира есть грузовик с длинным узким кузовом длиной \(L\) сантиметров — доски укладываются в кузов в один ряд вдоль кузова. На складе лежат \(n\) досок; каждая доска имеет две стороны: толщину \(a_i\) и ширину \(b_i\) сантиметров.

Каждую доску можно положить в кузов двумя способами: плашмя (тогда она занимает вдоль кузова \(a_i\) сантиметров) или на ребро (тогда \(b_i\) сантиметров). Способ укладки выбирается для каждой доски независимо.

Бригадир хочет за один рейс увезти максимальное количество досок. Какие именно — неважно: нужно лишь максимизировать число досок в кузове. Суммарная длина уложенных досок не должна превышать длины кузова.

Определите это максимальное число.

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

В первой строке — два целых числа \(n\) и \(L\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le L \le 10^{14}\)) — количество досок на складе и длина кузова в сантиметрах.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры сторон \(i\)-й доски в сантиметрах.

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

Одно целое число — максимальное количество досок, которые можно увезти за один рейс.

Примечание

В первом примере выгодно каждую доску укладывать той стороной, которая короче. Тогда доски займут 2, 4, 3 и 1 см — всего 10 см, помещаются все 4.

Во втором примере даже самая тонкая доска толще кузова, ни одну доску положить нельзя.

Школьник Тимур участвует в серии онлайн-соревнований по программированию. За весь год проходит \(n\) соревнований, и Тимур заранее знает, сколько очков он может набрать в каждом из них: за \(i\)-е соревнование он получит \(s_i\) очков.

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

Помогите ему вычислить эту максимальную сумму.

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

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 10^5\)) — общее количество соревнований и сколько из них идут в зачёт.

Во второй строке — \(n\) целых чисел \(s_i\) (\(0 \le s_i \le 10^9\)), разделённых пробелами, — количество очков за каждое соревнование.

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

Одно целое число — максимальная суммарная сумма очков за \(k\) выбранных соревнований.

Примечание

В первом примере из пяти соревнований с очками \(1, 5, 3, 8, 2\) надо выбрать три. Лучше всего взять соревнования с очками 8, 5 и 3 — в сумме 16.

Во втором примере в зачёт идут все соревнования, так что ответ — сумма всех очков.

Вдоль прямой трассы расположено \(n\) посёлков. У каждого посёлка известна его координата на трассе — целое число \(p_i\). Связисты хотят покрыть все посёлки радиосигналом, установив на трассе несколько радиовышек.

Каждая вышка имеет радиус покрытия 1 километр: она покрывает всё, что находится на расстоянии не более 1 от её координаты. То есть вышка, установленная в точке \(x\), покрывает отрезок \([x - 1; \, x + 1]\). Посёлок считается покрытым, если его координата попадает в покрытие хотя бы одной вышки (граничная точка тоже считается покрытой).

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

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество посёлков.

Во второй строке — \(n\) целых чисел \(p_i\) (\(-10^9 \le p_i \le 10^9\)), разделённых пробелами, — координаты посёлков. Координаты могут повторяться (несколько посёлков в одной точке).

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

Одно целое число — минимальное количество радиовышек, необходимое для покрытия всех посёлков.

Примечание

В первом примере посёлки находятся в точках 1, 3, 5. Одна вышка, установленная в точке 2, покроет отрезок \([1; 3]\) и захватит посёлки в точках 1 и 3. Для посёлка в точке 5 нужна ещё одна вышка, например в точке 4 или в точке 5. Итого 2 вышки.

Во втором примере все посёлки близко друг к другу и покрываются одной вышкой.

Центр управления отправляет на Марс грузовую капсулу. Она может поднять не более \(W\) килограммов полезной нагрузки. Учёные отобрали \(n\) научных приборов, которые хотят отправить в этой миссии; масса каждого прибора равна \(w_i\) килограммов.

Каждый прибор можно либо отправить целиком, либо оставить на Земле — разбирать их на части нельзя. Место в капсуле есть: ограничение только по массе. Цель миссии — отправить максимальное количество разных приборов, чтобы провести как можно больше экспериментов (какие именно приборы полетят — неважно, лишь бы число было максимальным).

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

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

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 10^5\), \(1 \le W \le 10^9\)) — количество приборов и грузоподъёмность капсулы в килограммах.

Во второй строке — \(n\) целых чисел \(w_i\) (\(1 \le w_i \le 10^4\)), разделённых пробелами, — масса каждого прибора в килограммах.

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

Одно целое число — максимальное количество приборов, которые можно отправить на Марс.

Примечание

В первом примере лучше всего отправить приборы массами \(1 + 2 + 3 + 4 = 10\) кг — ровно помещаются в капсулу, итого 4 прибора. Прибор массой 7 кг остаётся на Земле.

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

В актовом зале школы может проходить только одно мероприятие в каждый момент времени. На проведение актового зала подано \(n\) заявок от разных кружков. Каждая заявка — это интервал времени \([l_i; r_i]\): кружок хочет занять зал с минуты \(l_i\) по минуту \(r_i\) включительно.

Два кружка не могут проходить в зале одновременно: если один занимает время \([l_1; r_1]\), а другой — \([l_2; r_2]\), эти интервалы не должны пересекаться. Если один кружок заканчивается ровно в ту минуту, когда начинается другой, это тоже считается пересечением.

Директор хочет одобрить как можно больше заявок. Какое максимальное количество кружков можно разместить в зале за день?

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество заявок.

В следующих \(n\) строках — по два целых числа \(l_i\) и \(r_i\) (\(0 \le l_i < r_i \le 10^9\)) — время начала и время окончания каждой заявки.

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

Одно целое число — максимальное количество заявок, которые можно одобрить.

Примечание

В первом примере можно одобрить заявки \([1; 3]\) и \([4; 7]\) — они не пересекаются.

Во втором примере оптимально взять \([2; 3]\) и \([5; 7]\).

На столе лежит n верёвок разной длины. Вам нужно связать их все в одну длинную верёвку. За одну операцию можно взять любые две верёвки и связать их в одну — стоимость такой операции равна сумме длин этих двух верёвок.

Например, если связать верёвки длиной 3 и 5, получится одна верёвка длиной 8, а стоимость операции — 8. Эту новую верёвку можно затем связывать с другими.

Требуется найти минимальную суммарную стоимость, за которую можно связать все n верёвок в одну.
 

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

В первой строке записано натуральное число n (1 ≤ n ≤ 50 000) — количество верёвок.

Во второй строке через пробел записаны n натуральных чисел a₁, a₂, …, a_n (1 ≤ a_i ≤ 10 000) — длины верёвок.
 

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

Выведите одно целое число — минимальную суммарную стоимость связывания всех верёвок в одну. Если верёвка одна (n = 1), выведите 0.

Внимание: ответ может не помещаться в 32-битный целочисленный тип. В языке C++ используйте тип long long; в Python ограничений нет.
 

Пояснение к первому примеру

Оптимальная последовательность: связываем 2 и 3 (стоимость 5), получаем набор {4, 5, 6}. Связываем 4 и 5 (стоимость 9), получаем {6, 9}. Связываем 6 и 9 (стоимость 15). Итого: 5 + 9 + 15 = 29.

Ты копишь на подержанный велосипед и мониторишь Авито. Скопировал тексты объявлений в один файл и хочешь посчитать статистику по ценам.

Цены написаны по-разному: 15 000 ₽, 15000 руб, 15.000 р., от 14000 до 16000 рублей.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Цена — число от 1000 до 1 000 000 с возможными разделителями тысяч (пробел или точка), сразу за которым стоит обозначение рубля: ₽, р, р., руб, руб., рубль, рублей, рубля или рубли.

Числа вне диапазона \([1000, 1\,000\,000]\) при статистике игнорируются.

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

Ровно четыре строки:

min: <минимум>
max: <максимум>
avg: <среднее>
count: <количество>

Среднее — округлить до целого. Если цен не найдено, в первых трёх строках вместо чисел поставить дефис -, а в последней — 0.

Учительница литературы просит помечать тавтологии — когда одно и то же слово стоит подряд два раза: «был был», «очень очень».

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

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Слово — это последовательность букв (кириллица или латиница), цифр и подчёркиваний.

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

Тот же текст, но каждое повторение подряд двух одинаковых слов обёрнуто в квадратные скобки: [слово слово]. Пунктуация и все остальные символы сохраняются.

Примечание

Регистр при сравнении слов не учитывается: Очень очень — тоже повтор. В выводе регистр оригинала сохраняется.

В заметках на телефоне ты ведёшь дневник тренировок. Даты писали по-разному: 17.04.2026, 17/04/2026, 17-04-2026, 17 апреля 2026.

Приведи все найденные даты к ISO-формату YYYY-MM-DD.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Формат даты: день (1–2 цифры), разделитель (., /, - или пробел), месяц (2 цифры или слово на русском), разделитель, год (4 цифры).

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

Каждая найденная дата в формате YYYY-MM-DD на отдельной строке в порядке появления.

Примечание

Поддерживаются названия всех 12 месяцев: январь, февраль, ..., декабрь в любой форме (январь, января, январём — достаточно, чтобы начало совпало с основой).

Ты готовишь скриншот переписки с репетитором для публикации в Instagram-сторис и хочешь замаскировать номера телефонов: оставить префикс (+7 или 8) и последние 2 цифры, а между ними поставить ровно 8 звёздочек.

Например: +7 (903) 123-45-67 превращается в +7********67.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Телефоны — российские мобильные в любом из форматов задачи 3.

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

Тот же текст, но с заменёнными телефонами. Весь остальной текст (пунктуация, пробелы, переносы строк) сохраняется.

Мама выгрузила из электронного дневника текстовую выписку. Каждая строка выглядит так: название предмета, двоеточие, оценки через запятую или пробел.

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

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

Одна или несколько строк вида Название предмета: оценки. Название предмета — одно или несколько русских слов (только буквы и пробелы). Оценки — целые числа от 2 до 5, разделённые запятыми и/или пробелами.

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

Для каждого предмета в том же порядке, в котором они встретились во входе, выведи строку вида Предмет: X.XX — название, двоеточие, пробел, средний балл с двумя знаками после точки.

Примечание

Используй округление Python по умолчанию (функция round). Предметы без оценок (если такие попадутся) в выводе пропускай.

В Telegram-чате класса ребята обращаются друг к другу через @никнейм. Ты — староста и хочешь понять, кого упоминают чаще всех.

Никнейм — это символ @, за которым идут от 5 до 32 символов: латинские буквы, цифры и подчёркивания. Короткие последовательности (меньше 5 символов) никнеймами не считаются.

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

В первой строке — число \(N\) (\(1 \le N \le 100\)) — сколько самых упоминаемых никнеймов нужно вывести.
Далее — произвольный текст чата до 10 000 символов.

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

Топ-\(N\) никнеймов в нижнем регистре, каждый на отдельной строке. Порядок — по убыванию частоты упоминаний; при равенстве частот раньше идёт тот, кто первым встретился в тексте.

Если уникальных никнеймов меньше \(N\), выведи все, что есть.

Примечание

Регистр при подсчёте игнорируется: @Katya и @katya — один человек.

Классный руководитель попросил собрать все email-адреса из чата родителей в один список: без дубликатов, в едином регистре и в алфавитном порядке.

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

Произвольный текст до 10 000 символов, возможно в несколько строк.

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

Каждый уникальный email-адрес на отдельной строке в нижнем регистре, отсортированный лексикографически.

Примечание

Упрощённый формат email: имя@домен.зона, где имя — буквы, цифры, точки, дефисы, подчёркивания; домен — буквы, цифры, дефисы (без точек); зона — 2–6 латинских букв.

В родительском чате прислали текст с контактами репетиторов. Телефоны записаны в разных форматах:

• +7 (999) 123-45-67
• 8 999 123 45 67
• 89991234567
• +7-999-123-45-67

Нужно привести все найденные в тексте телефоны к единому виду +7XXXXXXXXXX (знак плюс, цифра 7, потом 10 цифр номера).

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

Произвольный текст до 10 000 символов. Все телефоны — российские мобильные: код оператора (3 цифры), потом 3-2-2 цифры с произвольными разделителями (пробелы, дефисы, скобки).

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

Каждый телефон в формате +7XXXXXXXXXX на отдельной строке в порядке появления в тексте.

На сайте школьного кружка робототехники при регистрации нужно валидировать пароль.

Напиши программу, которая считывает одну строку — пароль — и выводит YES, если пароль удовлетворяет всем условиям, и NO иначе.

Пароль считается надёжным, если:

• длина от 8 до 20 символов включительно;
• состоит только из латинских букв, цифр и символов _ - ! @ #;
• содержит хотя бы одну заглавную букву;
• содержит хотя бы одну строчную букву;
• содержит хотя бы одну цифру.

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

Одна строка — пароль (длиной до 100 символов).

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

Строка YES или NO.

Ты ведёшь паблик класса во ВКонтакте и хочешь собирать статистику по хештегам.

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

Хештег — это символ #, за которым идут один или более символов: буквы (латиница или кириллица), цифры или подчёркивания.

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

Произвольный текст от одной до 100 строк, общей длиной не более 10 000 символов.

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

Каждый найденный хештег на отдельной строке в порядке появления в исходном тексте.