Ремарка от 30.01.2024: в оригинальном тексте условий я использовал ФИО своих тогдашних знакомых (в основном одноклассников) в качестве имён героев. Сейчас, через 5 лет, это уже не кажется мне смешным, поэтому отсылки я решил убрать. Контест создавался в качестве шутки, поэтому задачи алгоритмически довольно простые, вся соль в условиях.
(P.S. Контеста тоже пока не будет)
В 2020 году во Всероссийской олимпиаде школьников по информатике приняло участие N московских школьников. Их размещение взяла на себя гостиница [УДАЛЕНО].
В гостинице [УДАЛЕНО] есть N свободных номеров, в каждом из которых может с комфортом разместиться K человек. Для каждого номера известна ci — стоимость аренды данного номера в течение олимпиады. Руководитель сборной Москвы, Д.П.Кириенко, хочет минимизировать количество денег, которые он потратит на заселение школьников. Помогите ему сделать это.
В первой строке входного файла вводятся два целых числа N и K (1 ≤ K ≤ N ≤ 1000000) — общее количество школьников и вместимость одной комнаты. Во второй строке входного файла вводятся N чисел ci (1 ≤ ci ≤ 109) — стоимости аренды каждого из номеров.
Выведите одно целое число — минимальную суммарную стоимость аренды номеров в худшем случае.
| стандартный ввод | стандартный вывод |
|---|---|
7 1 1 1 1 1 1 1 1 | 7 |
4 3 1 2 3 1 | 2 |
6 2 1 1 1 1 1 1 | 4 |
В первой половине 21-го века, в связи с бурным развитием как традиционной, так и нетрадиционной медицины, в России произошел резкий рост населения. В связи с этим в 2057 году во Всероссийской командной олимпиаде школьников по программированию готовы принять участие целых N команд из разных регионов, по K человек каждая.
Глава оргкомитета олимпиады, [ОТСЫЛКА], подходит к вопросу о расселении участников неординарно. Он считает, что членов разных команд ни в коем случае нельзя селить друг с другом, чтобы исключить обмен информацией между командами. Кроме того, так как при поселении в гостинице оплачивается каждое жилое место, он хочет, чтобы все арендуемые номера были полностью заполнены.
Владелец гостиницы, в которой планируется поселить участников, узнал о подходе [ОТСЫЛКА]. Кроме того, из сообщений в СМИ ему известно точное количество команд N и количество человек в команде K, но списка участников у него, разумеется, нет. Так как крыло гостиницы, где находились M-местные номера, пострадало в результате пожара, его интересует, сколько M-местных номеров нужно успеть отремонтировать к началу олимпиады. Помогите ему узнать, какое максимальное количество M-местных номеров может потребоваться.
В единственной строке входного файла вводятся три целых числа N, M, K (1 ≤ N, M, K ≤ 109)
Выведите одно целое число — ответ на задачу.
| стандартный ввод | стандартный вывод |
|---|---|
3 3 3 | 3 |
3 4 3 | 0 |
7 2 4 | 14 |
Как уже было сказано, владельцу гостиницы, где предполагается поселить участников, список участников олимпиады неизвестен. Но [ОТСЫЛКА] его, естественно, знает. Он заметил, что в этом году все участники ВКОШП — этнические русские. Для каждого i (1 ≤ i ≤ K) он хочет рассчитать, сколько комнат вместимостью i человек нужно снять.
В первой строке входного файла вводятся числа N и K (1 ≤ N, K, N•K ≤ 100000). В следующих N•K строках вводятся по 3 слова, записанных кириллицей — ФИО участника. Для каждой команды гарантируется, что ее участники записаны последовательно.
Обратите внимание: данные вводятся в кодировке KOI8-R, может потребоваться ручное считывание.Выведите K чисел ci (1 ≤ i ≤ K) — количество номеров вместимостью i мест, которое потребуется снять.
| стандартный ввод | стандартный вывод |
|---|---|
| отсылка удалена | 0 0 1 |
1 3персональные данные удалены по требованию одного из участников | 1 1 0 |
2025 год. Вирус Donny поразил большую часть компьютеров по всему миру. По счастливому стечению обстоятельств, вирус не был рассчитан на кодировки, отличные от Latin-1, поэтому компьютеры в странах с не-латинскими алфавитами не пострадали. В связи с нашествием вируса многие страны оказались неспособны выставить участников на Международную олимпиаду школьников по информатике, в результате чего было принято решение поднять квоту: к участию от России будут допущены все N победителей Всероссийской олимпиады.
Как и на любой другой олимпиаде, участников нужно где-то поселить. В связи с нашествием вируса, большинство стран оказались неспособны принять олимпиаду, и было принято решение провести ее в России, в том самом городе, что и Всеросс 5 лет назад. Заселить участников решили в той самой гостинице [УДАЛЕНО].
Как вы уже знаете, в гостинице [УДАЛЕНО] есть N свободных номеров, каждый из которых может вместить K человек. Однако компьютеры в бухгалтерии были настроены на английскую локаль, в связи с чем были выведены из строя вирусом. Поэтому руководство гостиницы, для упрощения рассчетов, решило сдать все номера по одигаковой цене C.
Руководителя сборной РФ, как всегда, интересует, какую минимальную сумму денег они должны будут заплатить.
В единственной строке входного файла вводятся три числа N, K, C (1 ≤ N, K, C ≤ 109) — количество участников, вместимость одного номера и стоимость аренды одного номера.
Выведите единственное число — суммарную стоимость аренды номеров.
| стандартный ввод | стандартный вывод |
|---|---|
7 1 1 | 7 |
4 3 1 | 2 |
[ОТСЫЛКА УДАЛЕНА]
Денис Павлович, дайте это на регионе, пожалуйста!