Информатика

На стройплощадку нужно перевезти доски. У бригадира есть грузовик с длинным узким кузовом длиной \(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 лампочек, пронумерованных от 1 до n. Каждая лампочка либо горит (обозначим «1»), либо не горит («0»). Текущее состояние гирлянды задано строкой a.

Монтажник Егор хочет, чтобы гирлянда выглядела по-праздничному — в виде строки b (тоже из нулей и единиц, той же длины n). Менять строку b нельзя — это «образец».

С гирляндой a Егор может выполнять две операции:

• Переключить одну лампочку. Выбрать позицию i (1 ≤ i ≤ n) и поменять её состояние (0 → 1 или 1 → 0). Стоимость такой операции — 1 рубль.
• Поменять местами две лампочки. Выбрать две позиции i и j (1 ≤ i, j ≤ n) и поменять состояния этих лампочек местами. Стоимость такой операции — |i - j| рублей, то есть расстояние между позициями.

Помогите Егору найти минимальную суммарную стоимость, с которой можно превратить гирлянду a в гирлянду b.
 

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

В первой строке — целое число n (1 ≤ n ≤ 106) — количество лампочек в гирлянде.

Во второй строке — строка a длины n, состоящая только из символов «0» и «1», — текущее состояние гирлянды.

В третьей строке — строка b длины n, состоящая только из символов «0» и «1», — желаемое состояние гирлянды.
 

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

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

На столе лежит 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.

Вам на вход подаётся JSON-ответ от API погоды с разделами current (текущая температура) и hourly (почасовой прогноз на 24 часа).

Составьте сводку погоды за сутки.

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

Одна строка — JSON-объект с разделами current и hourly.

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

Ровно 6 строк:

=== ПОГОДА НА СУТКИ ===
Сейчас: T°C
Максимум: X°C
Минимум: Y°C
Средняя: A°C
Размах: R°C

где T — текущая температура из current, X/Y/A — максимум, минимум и среднее по массиву hourly (среднее округлить до 1 знака), R — разница между максимумом и минимумом.

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом и пороговое значение температуры.

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

В разделе hourly время хранится как "2026-04-16T15:00". Возьмите только часть после T (получится 15:00).

Если таких часов нет, выведите Нет данных.

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

Первая строка — JSON-объект с разделом hourly.
Вторая строка — целое число (порог).

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

По одной строке на каждый подходящий час:

HH:00 — X°C

Или Нет данных, если ни один час не подошёл.

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом (раздел hourly, массив temperature_2m из 24 значений).

Посчитайте среднюю температуру за сутки, округлите до одного знака после запятой.

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

Одна строка — JSON-объект с разделом hourly.

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

Одна строка:

Средняя: X°C

где X — число с одним знаком после запятой.

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом (раздел hourly, массив temperature_2m из 24 значений).

Найдите максимальную и минимальную температуру за сутки.

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

Одна строка — JSON-объект с разделом hourly.

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

Две строки:

Максимум: X°C
Минимум: Y°C

Вам на вход подаётся JSON-ответ от API погоды с почасовым прогнозом (раздел hourly) и номер часа.

Раздел hourly содержит два параллельных массива по 24 элемента: time (время в формате "2026-04-16T15:00") и temperature_2m (температура).

Выведите строку:

Температура в HH:00: X°C

где HH:00 — время, X — целое число температуры.

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

Первая строка — JSON-объект с разделом hourly.
Вторая строка — целое число от 0 до 23 (номер часа).

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

Одна строка в указанном формате.

Вам на вход подаётся JSON-ответ от API погоды (раздел current) и название города.

Выведите строку в формате:

Город: T°C, ветер W м/с, влажность H%

где T, W, H — значения из JSON (как записаны, без округления).

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

Первая строка — JSON-объект с разделом current.
Вторая строка — название города.

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

Одна строка в указанном формате.

Вам на вход подаётся JSON-ответ от API погоды — это словарь с разделом current, внутри которого хранятся текущие метеоданные.

Выведите значение температуры (поле temperature_2m).

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

Одна строка — JSON-объект.

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

Одно число — температура (как оно записано в JSON, без дополнительного форматирования).

Примечание

В реальной программе эти данные вы бы получили через requests.get(...).json(), а здесь они подаются на вход. Парсить JSON можно так:

import json
data = json.loads(input())

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

Цены написаны по-разному: 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 — один человек.