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

Тяжелая, вариант-2#24737

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — максимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не меньше a_i-x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, на которое каждый школьник мог выпить менее своего максимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (x+1 ≤ a_i ≤ 200), разделенных пробелами, — максимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

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

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

Ввод	Вывод	Комментарий
3 4 1 2 2 3	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 2-1=1, 2-1=1 и 3-1=2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 2 2 3	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 2 2 3	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 3 4 6	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

Жадный алгоритм Разбор случаев

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

Сжатие текста#23587

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

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

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

В первой строке входного файла задано целое число R - количество заменяемых последовательностей и целое число N - количество строк в исходном тексте (1<=N<=1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая - заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст, подлежащий сжатию. В этом тексте, также как и в заменяемых последовательностях, отсутствуют буквы английского алфавита.

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

В выходной файл вывести заархивированный текст.

Примечания

Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов.

Пример входного файла

8 10

рхиватор

замен

ены

зам

быт

про

сжат

ом называется

Архиватором называется программа, предназначенная для сжатия данных за счет удаления

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

архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы

символов не встречаются, поэтому они могут быть использованы для замены часто

повторяющихся последовательностей символов.

Заданы последовательности, которые могут быть заменены некоторыми символами английского

алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти

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

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

Пример выходного файла

Аbg dграмма, предназначенная для fия данных за счет удаления

изhочной информации. В этой задаче вашей целью является разработка dстейшего

аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы

символов не встречаются, поэтому они могут hь использованы для Dы часто

повторяющихся последовательностей символов.

Заданы последовательности, которые могут hь DF некоторыми символами английского

алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти

последовательности могут накладываться друг на друга, результат fия существенно зависит

от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.

Задача на реализацию Разбор случаев

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

Метро#23399

В мегаполисе, испытывающем большие транспортные проблемы, построили легкое метро. Оно состоит из 6 радиальных линий, которые расходятся от центра города, и k кольцевых линий в форме правильных шестиугольников. Станции метро располагаются на пересечении кольцевых и радиальных линий. На любой станции разрешено делать пересадки с кольцевых линий на радиальные и обратно. Радиальные линии последовательно нумеруются по часовой стрелке от 1 до 6. Кольцевые линии нумеруются от центра города (центр считается кольцевой линией с номером ноль, состоящей из одной станции).

Расстояние между двумя соседними станциями на одной радиальной линии равно 1 км. Расстояние между соседними станциями на кольцевой линии с номером i составляет i км. Любая станция обозначается парой чисел - номером радиальной линии r (\(1<=r<=6\)) и номером кольцевой линии k (\(0<=k<=32000\)), на пересечении которых она находится.

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

Входные данные: Вводятся четыре числа: r1, k1, r2, k2 - координаты начальной и конечной станции.

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

Примеры

№	Входные данные	Выходные данные
1	1 5 1 4	1
2	1 5 2 4	5
3	2 0 6 3	3

кратчайшие пути Разбор случаев

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

День рождения#23382

На день рождения пришли N человек. В некоторый момент именинник решил, что пора устроить какую-нибудь игру. Он выяснил, что i-й человек согласен вступить в игру, если в ней уже принимают участие не менее A[i] и не более B[i] человек. Единожды вступив в игру, никто из нее

не выходит.

Требуется выяснить, может ли именинник установить такую

последовательность вступления в игру, что в итоге все

присутствующие станут ее участниками. (Сам именинник в игре участия

не принимает.)

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

Сначала вводится количество гостей N (1<=N<=100). Затем вводится

N пар чисел A[i] и B[i] (все эти числа из диапазона от 0 до N-1).

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

Если можно установить последовательность вступления гостей в игру,

чтобы в итоге все стали ее участниками, то нужно вывести номера гостей

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

в игру не удастся, выведите одно число - 0.

Пример 1

Пример входного файла

4 4

0 3

1 4

1 3

2 2

Пример выходного файла

2 3 5 4 1

Пример 2

Пример входного файла

1 1

Пример выходного файла

Пример 3

Пример входного файла

0 0

Пример выходного файла

Жадный алгоритм Разбор случаев

—Войти и решать

Сливаемся!#23375

Слияние двух упорядоченных последовательностей чисел в одну упорядоченную основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-

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

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

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

Результат слияния известен полностью. Вам необходимо подставить на место знаков вопроса числа так, чтобы исходные последовательности были неубывающими и при слиянии образовывали заданную результирующую последовательность.

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

В первой входного файла строке содержится число N количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса

содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел - результат слияния.

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

Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если

в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.

Ввод	Вывод
2 ? 4 3 ? 1 3 4 5	1 4 3 5

Разбор случаев Сортировка слиянием

—Войти и решать

Узник нейропривода#23040

2022 год. Человечество совершило прорыв в области электроники. Был создан всеми ожидаемый нейропривод, позволяющий человеку совершить полное погружение в видеоигру. Полная передача эмоций, самые настоящие чувства и ощущения и т.д.

И как вы думаете, что попросил Павлик у Дедушки Мороза на новый год? Конечно же нейропривод а так же только что вышедшую под него “Borderlands 5 online”.

Первого января, после получения своего подарка, Павлик начал играть. Паша был лютым геймером, поэтому прокачивался с космической скоростью. Это позволило ему в первый же день игры развести 5 новичков на деньги и шмот. Конечно Дедушке Морозу это не понравилось, и он решил проучить Павлика. Он заблокировал Павлику доступ вернуться в реальность и послал ему в игре злого босса по имени Даня Зевс, элитного игрока команды NA’VI по CS GO в прошлом. Чтобы выбраться в реальность Павлику необходимо победить босса.

У Дани Зевса n здоровья. У Павлика же есть Дробовик с a1 патронами и наносящий а2 урона, пистолет с b1 патронами и наносящий b2 урона и снайперская винтовка с с1 патронами и наносящая с2 урона.

Какое минимальное количество выстрелов необходимо сделать Павлику, чтобы убить босса, если это вообще возможно.

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

В первой строке записано число n – количество здоровья у Данечки Зевса.

Во второй строке записаны числа а1 и а2 – количество патрон и урон дробовика.

В третей строке записаны числа b1 и b2 – количество патрон и урон пистолета.
В четвертой строке записаны числа с1 и с2 – количество патрон и урон снайперской винтовки.

0<=n,a1,a2,b1,b2,c1,c2<=2*10^9

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

Вам необходимо вывести минимальное количество выстрелов, которое необходимо сделать Павлику или -1, если Павлик не сможет убить босса

Пример

Ввод

7 1

3 5

10 2

Вывод

(с) Курбатов Егор 9и

Жадный алгоритм Разбор случаев

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

Числа#21838

У Артура есть два натуральных числа — x и y (x < y). Помогите ему найти натуральное число z такое, что:

z > x;
z > y;
z не делится на x;
z не делится на y;
z делится на y - x;
z минимально.

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

В первой строке находятся числа x и y (x, y ≤ 10⁶)

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

Выведите число z или '0', если его не существует.

Ввод:
1 2

Вывод:
0

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

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

Игра#21814

На уроке физкультуры первоклассники Петя и Вася играют в увлекательную игру. Перед ребятами в ряд стоит n столбиков разной высоты. У мальчиков есть m колец, которые они по очереди кидают на столбики, причем если на столбике уже есть кольцо, то кидать кольцо на этот столбик нельзя. Петя кидает первым.

Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше l₁ и не больше r₁. На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше l₂ и не больше r₂ и гарантированно закидывает кольцо на любой такой столбик.

Физрук Андрей Сергеевич обещал поставить пятерку тому из ребят, кто по итогам игры закинет больше колец на столбики. Помогите ребятам выяснить, кто из них выиграет при оптимальной игре.

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

В первой строке входного файла находятся два целых числа n и m — количество столбиков и колец, соответственно (1 ≤ m ≤ n ≤ 10⁵). Следующие две строки содержат числа l₁, r₁ и l₂, r₂ — минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно (1 ≤ l₁ ≤ r₁ ≤ 10⁹, 1 ≤ l₂ ≤ r₂ ≤ 10⁹). В последней строке содержится n чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает 10⁹.

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

В выходной файл выведите «Petya», если выиграет Петя, «Vasya», если выиграет Вася, или «Draw», если при оптимальной игре оба мальчика закинут на столбики равное число колец.

Задачи на моделирование Разбор случаев

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

Шахматы#21811

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

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

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

В первой строке входного файла задано целое число n — количество столбцов доски

(1 ≤ n ≤ 1000). Следущая строка содержит n чисел a1, a2, . . . , an — количество клеток в столбцах

(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).

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

В первой строке выведите число k — минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие k строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.

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

Примеры
Ввод

5 2 1

Вывод

1 5

2 1

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

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