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

Оптом – дешевле!#34828

В Москве начал работать новый оператор сотовой связи, предоставляющий доступ в интернет посредством технологии 3G. Новый оператор предлагает простые и невысокие
тарифы, в частности, один мегабайт интернет-трафика стоит 1 рубль.

Кроме того, оператор предлагает покупать оптовые пакеты трафика – есть два предложения: купить пакет трафика на A мегабайт за B рублей и купить пакет трафика на C мегабайт за D рублей.

Таня планирует использовать в течение месяца N мегабайт интернет-трафика. Определите минимальную сумму, которую придётся ей заплатить. Таня может приобретать
любое количество каждых из двух предлагаемых пакетов, а также оплачивать трафик по тарифу «1 рубль за мегабайт». Таня может приобретать пакеты интернет-трафика и в том
случае, если суммарный оплаченный трафик будет более N мегабайт, если это выйдет дешевле.

Программа получает на вход пять натуральных чисел N, A, B, C, D, записанных в отдельных строках, не превосходящих 500 000 каждое. Гарантируется, что A > B и C > D.
Программа должна вывести одно целое число – минимальную сумму, которую нужно заплатить для приобретения N мегабайт трафика.

Ввод	Вывод	Примечание
35 10 9 20 17	31	Пакет на 10 мегабайт стоит 9 рублей, пакет на 20 мегабайт стоит 17 рублей. Для оплаты 35 мегабайт нужно купить пакет на 10 мегабайт и пакет на 20 мегабайт, а за оставшиеся 5 мегабайт заплатить 5 рублей.
55 30 20 20 16	40	Пакет на 30 мегабайт стоит 20 рублей, пакет на 20 мегабайт стоит 16 рублей. Для оплаты 55 мегабайт нужно купить два пакета на 30 мегабайт, что суммарно будет стоить 40 рублей.

Жадный алгоритм Задачи на моделирование

✓ 15✗ 1571 100средняяВойти и решать

Ёж#33113

Тем временем Ёж решил покатать шары из снега. В итоге у него получилось N шариков с диаметрами a₁, a₂, … a_n, все они различны. Из них он хочет собрать как можно больше НОРМАЛЬНЫХ снеговиков. Нормальный снеговик состоит из трёх шаров, диаметр которых снизу вверх строго уменьшается. Сколько максимум снеговиком он сможет собрать?

Ввод	Вывод
6 2 3 4 5 6 7	2

(с) Манаев И., Кашукова М., 2018 г.

Жадный алгоритм реализация

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

Счастливые билеты#32975

На автобусных билетах указываются их номера. Номера всех билетов всегда записываются при помощи одного и того же количества цифр, при этом число используемых цифр чётно. При необходимости числа дополняются ведущими нулями. К примеру, если для записи используют 4 цифры, то 514 будет записано как 0514. Билеты отпечатаны на лентах, билеты на каждой ленте нумеруются подряд числами от 00...01 до 99...99.

Счастливым считается тот билет, у которого сумма цифр первой половины равна сумме цифр второй половины, например, билеты 1001 и 123051 счастливые, а 7778 и 39 – нет. Сегодня Дима зашел в автобус, и кондуктор выдал ему билет с номером N. Поскольку Диме ехать достаточно долго, а заняться чем-нибудь надо, он стал думать, какой номер будет иметь следующий счастливый билет, выданный из той же ленты, что и Димин билет. Если в текущей ленте не осталось счастливых билетов, Диму интересует номер минимального счастливого билета из новой ленты.

В первой и единственной строке входного файла содержится номер Диминого билета N, записанный с ведущими нулями. Количество цифр в записи числа N не превосходит 100 000 и чётно.

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

Ввод	Вывод	Примечание
0514	0523	Диме был выдан счастливый билет (сумма цифр обеих половин равна 5), но Диму не интересует номер его билета, его интересует номер следующего счастливого билета.

Жадный алгоритм

✓ 17✗ 2631 100средняяВойти и решать

Лифт в бизнес-центре#32974

Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнесцентр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого

из N этажей. Определите, какое минимальное время потребуется, чтобы перевезти на парковку всех сотрудников бизнес-центра.

Первая строка входных данных содержит наибольшее возможное число людей в лифте K, 1 ≤ K ≤ 10⁹

Вторая строка содержит число этажей в бизнес-центре N, 1 ≤ N ≤ 10⁵

Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1, 2, … , N-м этаже соответственно, эти числа не превосходят 10⁹каждое. В здании находится хотя бы один человек.

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

Ввод	Вывод	Примечание
2 3 3 0 1	8	Лифт перевозит 2 человек, в здании 3 этажа. Лифт поднимается на первый этаж за 1 с, забирает 2 человек и за 1 с спускается на парковку, затем лифт поднимается на первый этаж, забирает 1 человека, вместе с ним поднимается на третий этаж, забирает 1 человека и спускается на парковку. Подъём на третий этаж занимает 3 с, спуск – ещё 3 с.

Жадный алгоритм Задачи на моделирование реализация

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

Fenced In#29546

Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.

Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a₁…a_n (0<a_i<A); каждая изгородь проходит от точки (a_i,0) до точки (a_i,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<b_i<B); каждая изгородь, проходит из (0,b_i) в (A,b_i). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.

К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.

Например, ФД мог построить изгороди так:

+---+--+

| | |

+---+--+

| | |

+---+--+

и открыть их так:

+---+--+

| |

+---+ +

| |

+---+--+

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

ФОРМАТ ВВОДА:

Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a₁…a_n. Следующие m строк содержат b₁…b_m.

ФОРМАТ ВЫВОДА:

Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )

Ввод	Вывод
15 15 5 2 2 5 10 6 4 11 3	44

Алгоритмы сортировки Жадный алгоритм

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

Paired Up#27220

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 10⁹, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.

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

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

Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 10⁹) литров. Сумма всех x-ов есть M- общее количество коров.

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

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

Примеры

№	Входные данные	Выходные данные
1	3 1 8 2 5 1 2	10

"Два указателя"Жадный алгоритм

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

Курьер#26986

Курьеру Васе поручили доставить n посылок. Вася начинает работать в первый день и каждый день может доставить ровно одну посылку. Про каждую посылку известен последний день, когда ее можно доставить d_i, и штраф w_i, который придется заплатить, если посылка не будет доставлена в срок.

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

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

Формат ввода

В первой строке дано единственное натуральное число n (1 n 200 000) — количество посылок.

Затем следует n строк, в каждой из которых содержится по два числа d_i и w_i (1 d_i 200 000, 1 w_i 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

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

В первой строке выведите единственное число, равное минимально возможному суммарному штрафу. Во второй строке через пробел выведите n чисел, где i-е число — день, в который необходимо доставить i-ю посылку.

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

Пример

Ввод	Вывод
3 1 2 1 3 3 1	2 3 1 2

Жадный алгоритм Использование сортировки

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

Тяжелая, вариант-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средняяВойти и решать

Тяжелая, вариант-1#24736

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

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

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

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

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

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

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

Жадный алгоритм Задачи на моделирование

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

День рождения#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

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

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

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

Узник нейропривода#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средняяВойти и решать