Четвер, 13.05.2021, 06:05
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 60
Головна » 2020 » Лютий » 2 » III ЕТАП ВСЕУКРАЇНСЬКОЇ ОЛIМПIАДИ З IНФОРМАТИКИ, II ТУР
21:45
III ЕТАП ВСЕУКРАЇНСЬКОЇ ОЛIМПIАДИ З IНФОРМАТИКИ, II ТУР
2 лютого 2020 року відбувся 2-й тур ІІІ обласного етапу Всеукраїнської учнівської олімпіади з інформатики 2019/2020 н.р.

Оцiнювання
Є два види оцiнювання:
«Потестове оцiнювання». Кожний тест оцiнюється незалежно вiд iнших. Проходження тесту приносить певну кiлькiсть балiв. Приклади оцiнюються в 0 балiв.
«Блочне оцiнювання». Усi тести подiленi на блоки, якi описанi в умовi задачi. Бали нараховуються лише при проходженнi всiх тестiв блоку. Якщо обмеження блока i не меншi за обмеження блока j, то для нарахування балiв за блок i, також потрiбно, щоб пройшли всi тести блока j. В умовi про це не буде сказано. Також є «нульовий блок», який складається з прикладiв, вiн оцiнюється в 0 балiв. В умовi про це згадувати не будуть.

Задача A. Газон у Потоколяндiї

Назва вхідного файлу:lawn.in
Назва вихідного файлу:lawn.out
Обмеження використання часу:0.25 second
Обмеження використання пам'яті:256 megabytes

У саду Потоколяндiї є газон шириною в 1 метр та довжиною в n метрiв.
Козак Вус хоче покосити цей газон за допомогою наступних дiй: вiн вибирає деякий пiдвiдрiзок цього газону довжиною k (частина газону шириною в 1 метр та довжиною в k метрiв) такий, що вiн повнiстю покритий травою та косить траву цiєї частини газону. На цю дiю йому необхiдно витратити одну годину.
Також вiдомо, що рiвно через годину з моменту, коли було завершено описану дiю, трава на цiй дiлянцi знову виросте. Це виростання вiдбувається миттєво в описаний момент часу.
Тодi Козак Вус зрозумiв, що його задовольнить навiть не повнiстю покошений газон - достатньо щоб будь-яка дiлянка газону була покошена хоча б один раз.
Допоможiть Козаку дiзнатись мiнiмальний час, який йому знадобиться, щоб будь-яка дiлянка газону була покошена хоча б один раз.
Початково на всьому газонi трава не є покошеною.
Формат вхідних даних:
Перший рядок мiстить два цiлих числа n та k (1 ≤ kn ≤ 100) - довжина газону в метрах та довжина пiдвiдрiзку, який вибирається для того, щоб покосити газон, вiдповiдно.
Формат вихідних даних:
Виведiть одне цiле число - вiдповiдь на задачу у годинах. Легко показати що вiдповiдь завжди є цiлим числом.
Приклади
lawn.inlawn.out
5 2 3
3 31
Примiтка
Пояснення до першого прикладу:

Оцiнювання
Кожний тест, крiм прикладiв, оцiнюється в 4 бали.


Задача B. Мафiя у Потоколяндiї

Назва вхідного файлу:mafia.in
Назва вихідного файлу:mafia.out
Обмеження використання часу:0.25 second
Обмеження використання пам'яті:256 megabytes

Нещодавно у Потоколяндiї розробили онлайн версiю гри «Мафiя».
Оскiльки Козак Вус - головний програмiст Потоколяндiї, то саме йому i довiрили протестувати цю гру.
Всiм вiдомо, що головне у грi «Мафiя» - чати повiдомлень. Козак Вус вважає гру протестованою, якщо у чатах сумарно буде написано хоча б n слiв.
Оскiльки програмiсти не тестують чати, Козаку доведеться найняти кiлька тестувальникiв на наступних умовах: кожен тестувальник напише привiтальне повiдомлення, що складатиметься з a слiв у загальний чат гри, а також напише кожному iншому тестувальнику привiтальне повiдомлення, що складатиметься з b слiв у особистий чат. Тестувальники не писатимуть iнших повiдомлень, крiм описаних вище.
Припустимо, що є 3 тестувальники, кожен з яких має написати «Усiм привiт!» (2 слова) у загальний чат, а також «Привiт!» (1 слово) кожному iншому тестувальнику в особистий чат. Тодi у загальному чатi буде написано 2 · 3 = 6 слiв (кожен тестувальник напише 2 слова), а в кожному особистому чатi буде написано по два слова (по одному слову вiд кожного тестувальника). Оскiльки всього 3 особистих чатiв (мiж першим та другим, мiж першим та третiм, мiж другим та третiм тестувальниками), то всього буде написано 3 · 2 = 6 слiв в особистих чатах. Отже, всього буде написано 6 + 6 = 12 слiв у всiх чатах.
Пiд час тестування лише тестувальники писатимуть повiдомлення у чати повiдомлень.
Через те, що Козак Вус не хоче витратити багато грошей на найм тестувальникiв, вiн вирiшив мiнiмiзувати їх кiлькiсть. Допоможiть йому дiзнатись мiнiмальну кiлькiсть тестувальникiв, яку доведеться найняти, щоб у чатах сумарно було написано хоча б n слiв.
Формат вхідних даних:
Перший рядок мiстить три цiлих числа n, a та b (1 ≤ n ≤ 1012, 0 ≤ a, b ≤ 106, 0 < a + b) - мiнiмальна кiлькiсть слiв, яка має бути написана, кiлькiсть слiв, яку має написати кожний тестувальник у загальний чат, а також кiлькiсть слiв, яку має написати кожний тестувальник кожному iншому в особистий чат.
Формат вихідних даних:
Виведiть одне цiле число - мiнiмальну кiлькiсть тестувальникiв, яку доведеться найняти, щоб у чатах сумарно було написано хоча б n слiв.
Приклади
mafia.inmafia.out
10 1 33
10 8 22
Примiтка
У першому прикладi, якщо буде найнято 3 тестувальника, то у загальний чат буде написано 3 слова, а в особистих чатах буде написано 18 слiв.
У другому прикладi, якщо буде найнято 2 тестувальника, то у загальний чат буде написано 16 слiв, а в особистих чатах буде написано 4 слова.
Оцiнювання
Кожний тест, крiм прикладiв, оцiнюється в 5 балiв.


Задача C. Козак Вус та мiньйони

Назва вхідного файлу:minions.in
Назва вихідного файлу:minions.out
Обмеження використання часу:0.5 second
Обмеження використання пам'яті:256 megabytes

Бути мiньйоном – це звiсно ж круто, але Козак Вус сильнiший за них...
У розпорядженнi у Козака Вуса є n мiньйонiв, пронумерованих цiлими числами вiд 1 до n.
Кожен мiньйон характеризується своїми силою та витривалiстю. У i-го мiньйона сила рiвна ai, а витривалiсть рiвна bi.
Козак Вух попросив Козака Вуса передати йому в розпорядження загiн мiньйонiв. Припустимо, що Козак Вух попросив передати k мiньйонiв. Тодi Козак Вус може передати будь-якi k мiньйонiв своєму другу. Цi мiньйони можуть мати будь-якi номери, не обов’язково послiдовнi. В кожному загонi має бути один лiдер, який вибирається Козаком Вусом.
Герої для кожного загону мiньйонiв визначили його цiну. Вони вважають, що цiна загону рiвна сумi сили лiдера та витривалостей всiх iнших мiньйонiв в загонi (якщо такi є). Розмiром загону називають кiлькiсть мiньйонiв у ньому.
Припустимо, що є чотири мiньйони, у яких:

1. сила 3, а витривалiсть 6,
2. сила 7, а витривалiсть 3,
3. сила 1, а витривалiсть 8,
4. сила 6, а витривалiсть 5.

Якщо Козак Вух просить передати йому загiн з 3 мiньйонiв, то Козак Вус може, наприклад, вибрати першого, другого та четвертого. Якщо вiн назначить другого лiдером, то цiна загону буде рiвна 7 (сила лiдера) + 6 (витривалiсть першого) + 5 (витривалiсть четвертого) = 18.
Нехай f (k) – мiнiмальна цiна загону серед всiх загонiв, в яких розмiр k.
У попередньому прикладi Козаку Вусу для мiнiмiзацiї цiни краще за все вибрати загiн, в якому другий, третiй та четвертий мiньйони та призначити третього мiньйона лiдером. Тодi цiна загону рiвна 1 + 3 + 5 = 9. Оскiльки немає кращого рiшення, то f (3) = 9.
Тепер Козаки хочуть дiзнатись всi можливi значення f. Допоможiть Козакам дiзнатись значення f (1), f (2), . . . , f (n).
Формат вхідних даних:
Перший рядок мiстить одне цiле число n (1 ≤ n ≤ 2 · 105) – кiлькiсть мiньйонiв у розпорядженнi у Козака Вуса.
Кожний з наступних n рядкiв мiстить два цiлих числа ai та bi (1ai, bi109) – значення сили та витривалостi мiньйона з номером i вiдповiдно.
Формат вихідних даних:
Виведiть n цiлих чисел – f (1), f (2), . . . , f (n).
Приклади
minions.inminions.out
3
1 4
3 3
2 1
1
2
5

5
3 4
3 3
2 4
4 3
5 3
2
5
8
11
15

Примiтка
Пояснення до першого прикладу:
Щоб утворити загiн мiнiмальної вартостi серед всiх загонiв розмiру 1, необхiдно утворити загiн що складається з мiньйона з номером 1.
Щоб утворити загiн мiнiмальної вартостi серед всiх загонiв розмiру 2, необхiдно утворити загiн що складається з мiньйонiв з номерами 1 та 3 та вибрати лiдером мiньйона з номером 1.
Щоб утворити загiн мiнiмальної вартостi серед всiх загонiв розмiру 3, необхiдно утворити загiн що складається з всiх мiньйонiв та вибрати лiдером мiньйона з номером 1.
Оцiнювання
ОбмеженняБали
na, bДодатковi
11 ≤ n ≤ 2 · 1051 ≤ a, b ≤ 3-7
21 ≤ n ≤ 20001 ≤ a, b ≤ 109Всi значення a рiвнi мiж собою13
31 ≤ n ≤ 2 · 1058
41 ≤ n ≤ 100-23
51 ≤ n ≤ 200019
61 ≤ n ≤ 2 · 1051 ≤ a, b ≤ 10917
71 ≤ a, b ≤ 10913


Переглядів: 254 | Додав: ivv
Всього коментарів: 0
avatar