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

Легкая, вариант-1#24738

Пете подарили n гирь и чашечные весы. Каждая гиря весит a_i грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.

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

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

В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 4 2 1 1 8 1 5 2 2 1	0
6 20 2 3 2 2 1 5 1 1 1 3 2	6
4 3 2 10 2 8 2 9 2	4

Разбор случаев реализация

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

Легкая, вариант-1#24734

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

Ваша задача написать программу, которая сможет оценить эффективность данной системы и посчитает сколько ящиков останутся на складе.

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

В первой строке находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков останутся на складе, после выполнения отправки.

Пример входных и выходных данных

Ввод	Вывод
5 2 1 1 1 2 1 1 1 2 1 1 1	1
5 1 2 1 1 1 2 1 1 1 2 1 1	5

Очередь реализация

✓ 76✗ 45500лёгкаяВойти и решать

ЭПИЗОД X ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР#24727

ЭПИЗОД X: ФИРИОН НАНОСИТ ОТВЕТНЫЙ УДАР
Берляндия наконец-то окрепла после крупного поражения в войне против Стерляндии, и император Берляндии Фирион готовит атаку на противника.
Стерляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Стерляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой.
Планируется следующее:
Выбирается город, на который будет производиться атака. Город уничтожают, а дороги, исходящие из него, баррикадируются. При этом Стерляндия должна потерять свою целостность. Далее одна из образованных областей подвергается атаке. При этом эта область должна составлять не менее 1/8 и не более 1/4 от оставшейся площади страны ( площадь измеряется в количестве городов в данной области). Если при разрушении города Стерляндия сохраняет целостность, или подходящих областей не образуется, то данный город не подходит для атаки.
Фирион хочет знать сколько городов удовлетворяют выше описанным условиям, а также номера этих городов в порядке возрастания.
Входные данные
В первой строке даны два числа: n – кол-во городов в Стерляндии ( 2 <= n <= 10^3), m – количество дорог в Стерляндии ( 1 <= m <= 10^4).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s – кол-во городов, подходящих для атаки. Во второй строке выведите s чисел - номера таких городов в порядке возрастания.
Пример

5 5
1 2
1 3
2 3
3 4
4 5

1
4

графы Точки сочленения

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

ГОЛБЕЗ В БЕРЛЯНДИИ#24726

ГОЛБЕЗ В БЕРЛЯНДИИ
Турист Голбез очень любит путешествовать. На этот раз он решил посетить Берляндию.
Берляндия представляет собой определенное количество городов, соединенных двусторонними дорогами. От любого города Берляндии можно добраться до любого другого. Никакая дорога не соединяет город с самим собой.
Будем называть дорогу дорогой федерального значения, если существует любая пара городов v и u ( v != u), такая, что любой путь от v до u лежит через эту дорогу. Будем называть город городом федерального значения, если все дороги, исходящие из этого города являются дорогами федерального значения.
Голбез решил посетить все города федерального значения Берляндии. Помогите ему определить какие именно города ему необходимо посетить.
Входные данные
В первой строке даны два числа: n – кол-во городов в Берляндии ( 2 <= n <= 10^5), m – количество дорог в Берляндии ( 1 <= m <= 10^6).
Далее идут m строк, в которых задается описание дорог, а именно: в каждой строке заданы два числа: X и Y. Это означает, что город X и город Y соединены дорогой.
Выходные данные
В первой строке выведите число s – кол-во городов федерального значения. Во второй строке выведите s чисел - номера городов федерального значения в порядке возрастания.
Пример

5 5
1 2
1 3
2 3
3 4
4 5

2
4 5

Мосты

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

Поезд#24691

Вам дан массив целочисленных чисел размера n.Необходимо реализовать структуру данных,которая могла бы исполнять следующие операции:
1)Прибавлять всем числам на отрезке [l;r] величину d.
2)Получить сумму чисел на отрезке [l;r].
3)Получить минимум из чисел на отрезке [l;r].
INPUT
На ввод приходит число n – размер массива.В следующей строке,через пробел, даны n чисел - a_i.
Далее задается число m - количество запросов.В следующих m строках запросы трех видов:
1)add l r d - прибавление на отрезке [l;r] числа d.
3)rsq l r - запрос суммы на отрезке [l;r].
3)rmq l r - запрос минимума на отрезке [l;r].
OUTPUT
Ответы для запросов второго и третьего типов через пробел.
P.S. 0 < n, m < 100001 a_i < 1000000001.
P.S.S. Гарантируется,что ответ вмещается в 64-битный тип данных.
INPUT
5
1 2 3 4 5
3
rsq 1 5
add 2 3 1
rmq 2 4
OUTPUT
15 3

(с) Никита Максимов, 2017г.

Дерево отрезков, RSQ, RMQ

✓ 1✗ 61 300средняяВойти и решать

Анализ цифр числа - 14#24687

В первой строке вводится натуральное чило n
Во второй строке вводится число B
Вывести на экран
- слово YES, если сумма его цифр больше числа В, а само число четное
- в противном случае вывести слово NO

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545 15	NO
2	554 5	YES

Цикл while

✓ 418✗ 1 061500лёгкаяВойти и решать

Анализ цифр числа - 1#24686

Дано натуральное число N (N<=10⁹). Определить порядковый номер его минимальной цифры, считая от конца числа (если таких цифр несколько, то вывести номер первой из них)

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	2
2	100	1

Цикл while

✓ 216✗ 617500лёгкаяВойти и решать

Анализ цифр числа - 2#24685

Дано натуральное число N (N<=10⁹). Определить порядковый номер его минимальной цифры, считая от начала числа (если таких цифр несколько, то вывести номер первой из них)

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	1
2	100	2

Цикл while

✓ 141✗ 539600лёгкаяВойти и решать

Анализ цифр числа - 3#24684

Дано натуральное число N (N<=10⁹). Определить порядковый номер его максимальной цифры, считая от начала числа (если таких цифр несколько, то вывести номер первой из них)

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	2
2	100	1

Цикл while

✓ 154✗ 584600лёгкаяВойти и решать

Анализ цифр числа - 4#24683

Дано натуральное число N (N<=10⁹). Определить порядковый номер его максимальной цифры, считая от конца числа (если таких цифр несколько, то вывести номер первой из них)

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	1
2	100	3

Цикл while

✓ 133✗ 418600лёгкаяВойти и решать

Анализ цифр числа - 5#24682

Дано натуральное число N (N<=10⁹). Найти сумму его максимальной и минимальной цифр

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	9
2	111	2

Цикл while

✓ 541✗ 959500лёгкаяВойти и решать

Анализ цифр числа - 6#24681

Дано натуральное число N (N<=10⁹). Определить, на сколько его максимальная цифра превышает минимальную

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	1
2	111	0

Цикл while

✓ 489✗ 693400лёгкаяВойти и решать

Анализ цифр числа - 7#24679

Дано натуральное число N (N<=10⁹) и цифра k. Определить произведение цифр числа N, которые больше, чем k. Если таких цифр нет, то необходимо вывести 0.

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545 4	125
2	1235 2	15

Цикл while

✓ 578✗ 2 173600лёгкаяВойти и решать

Анализ цифр числа - 8#24678

Дано натуральное число N (N<=10⁹). Определить, сколько раз в нем встречается последняя цифра (без учета последней цифры).

Пример входных и выходных данных

№ теста	Входные данные	Выходные данные
1	45545	2
2	445	0

Цикл while

✓ 412✗ 1 022500лёгкаяВойти и решать

Средняя урожайность пшеницы#24677

В области Че в каждом из N районов решили засеять свободные поля пшеницей. После жатвы всю пшеницу свозят в хранилище и считают, сколько было собрано урожая в каждом районе. Известная площадь, засеянная пшеницей (A_i, в гектарах) в каждом районе, и размер собранного урожая в каждом районе (B_i,в центнерах). Напишите программу, которая считает среднюю урожайность пшеницы по каждому району и по всей области в целом.

Входные данные
В первой строке вводится значение N - количество районов в области (1 <= N <= 1000). Во второй строке, вводится N чисел A_i - площади каждого района (1 <= A_i <= 10⁹). Во второй строке, вводится N чисел B_i - урожайность каждого района (1 <= B_i <= 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	5 10 20 25 30 35 30 40 50 60 70	3.000000 2.000000 2.000000 2.000000 2.000000 2.083333

Одномерные массивы

✓ 242✗ 597600лёгкаяВойти и решать

Арифметическое выражение-3#24676

Напишите программу, которая вычисляет выражение, состоящее из трех чисел, трех знаков арифметических операций (допускаются знаки «+», «–», «*» и «/») и круглых скобок. На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа - целые. Операция «/» выполняется как целочисленное деление.

Примеры

№	Входные данные	Выходные данные
1	2*(3+45)+4	100
2	2*3/(5-2)	2

Строки

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

Арифметическое выражение-1#24675

Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа целые.

Примеры

№	Входные данные	Выходные данные
1	12+3+45	60
2	12-45+3	-30

Строки

✓ 489✗ 478500лёгкаяВойти и решать

По мотивам ЕГЭ 2016 - 2#24670

Дано N пар чисел. Из каждой пары нужно выбрать одно так, чтобы сумма выбранных чисел была наименьшей из возможных и не делилась на 4. В первой строке вводится число N, не превышающее 100 000.
Если таких чисел нет, вывести "no".
На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

Примеры

№	Входные данные	Выходные данные
1	6 10 10 1 7 2 5 4 5 6 9 13 13	37

ЕГЭ - вычислительные задачи

✓ 715✗ 1 149500лёгкаяВойти и решать

По мотивам ЕГЭ 2016 - 1#24669

Дано N пар чисел. Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел была наибольшей из возможных и не делилась на 4. В первой строке вводится число N, не превышает 100 000.
Если таких чисел нет, вывести "NO".

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

Входные данные
В первой строке задается количество пар. В последующих строках - сами пары. Числа по модулю не превышают 30 000.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 2 4 9 3 5 7 2 4 4 2 2	29

ЕГЭ - вычислительные задачи

✓ 660✗ 1 973500лёгкаяВойти и решать

И.О. Фамилия#24659

Ввести имя, отчество и фамилию. Преобразовать их к формату «инициалы-фамилия».

Входные данные: в первой строке задается предложение. Слова разделены одном пробелом, вначале и в конце текста лишних пробелов нет.

Выходные данные: необходимо вывести модифицированную строку.

Примеры

№	Входные данные	Выходные данные
1	Inav Ivanovich Ivanov	I. I. Ivanov

Строки

✓ 1 324✗ 1 876300лёгкаяВойти и решать