Четвер, 13.05.2021, 06:10
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 60
Головна » 2018 » Лютий » 6 » 2 Тур. Всеукраїнська олімпіада з інформатики ІІІ (обласний етап). 04/02/2018
20:18
2 Тур. Всеукраїнська олімпіада з інформатики ІІІ (обласний етап). 04/02/2018

4 лютого 2018 року відбувся 2 тур ІІІ-го (обласного етапу) Всеукраїнської учнівської олімпіади з інформатики з використанням автоматичної системи прийняття та перевірки робіт учасників олімпіади на порталі Хмельницького обласного інституту післядипломної педагогічної освіти (http://sbs2.km.ua/olymp/).

У 1 турі приймали участь учні Хоцьківської ЗОШ І-ІІІ ступенів:
    1. Коваленко Валентина (учениця 8 класу),
    1. Боровик Таїсія (учениця 8 класу),
    2. Янча Тетяна (учениця 10 класу),
    3. Чухно Катерина (учениця 11 класу).

Задача А. Охохо!

Ім’я вхідного файлу:dog.in
Ім’я вихідного файлу:dog.out
Обмеження по часу:0,1 секунди
Обмеження по пам’яті:64 Мб

    Дача Леді охороняється двома собаками, які часто викливають проблеми. Кожного дня до Леді приходить листоноша, молочник та прибиральник сміття. Вони знають, що поведінка собак цілком передбачувана. Коли починається день, одна собака А хвилин агресивна, а потім В хвилин спокійна. Аналогічно, інша собака агресивна С хвилин, а потім спокійна D хвилин. Обидві собаки повторюють свою повелінку на невизначений термін – агресивний період, потім спокійний період, потім знову агресивний, т.д.
    З огляду на час прибуття листоноші, молочника та прибиральника сміття, допоможіть Леді визначити скільки собак (жодна, одна або обидві) нападає на кожного з них. Зверніть увагу, що люди прибувають у k-ту хвилину, а не рівно через k хвилин.

Формат вхідних даних

    У першому рядку вхідного файлу знаходиться чотири цілих числа A, B, C, D. Другий рядок містить цілі числа P, M, G – хвилини дня, коли листоноша, молочник і прибиральник сміття прибувають до дачі Леді.
    Наприклад, якщо P = 3, то це слід тлумачити як «листоноша прийшов в третю хвилину дня». Усі вхідні дані будуть від 1 до 999.

Формат вихідних даних

    Вихідні дані мають містити три рядка, кожен з яких містить «2», «1» або «0», в залежності від того, скільки собак атакує кожного з наших героїв.

Приклади

dog.indog.out
2 2 3 3
1 3 4

2
1
0
2 3 4 5
4 9 5

1
0
0

Задача В. Розрахунок

Ім’я вхідного файлу:calculation.in
Ім’я вихідного файлу:calculation.out
Обмеження по часу:0,1 секунди
Обмеження по пам’яті:64 Мб

    Леді нащедрувала повну кишеню монет 5, 10, 20 і 50 копійок, і коли вона має сплатити будь-яку сму, то вибирає свої монети таким чином, щоб використати мінімально можливу кількість монет.
    Ваше завдання полягає у написанні програми, яка, враховуючи кількість монет 5, 10, 20 і 50 копійок в кишені Леді, визначає кількість монет кожного номіналу та загальну кількість використаних монет так, що загальна кількість монет, яку вона може використати, була мінімальною. Зауважте, що Леді не завжди зможе заплатити потрібну суму грошей.

Формат вхідних даних

    Перший рядок вхідного файлу містить п’ять цілих чисел – перші чотири це кількості відповідно 5, 10, 20 і 50 копійок, а п’яте число представляє суму, яку Леді має заплатити, в копійках. (Кількість монет кожного типу менша 1 000 000, а сума менша 100 000 000 копійок).

Формат вихідних даних

    У єдиному рядку вихідного файлу виведіть п’ять чисел: перші чотири – кількість монет кожного типу, які Леді має потратити, а також загальна кількість монет. Якщо розрахуватись Леді не може – виведіть -1.

Приклади

calculation.incalculation.out
2 2 2 2 351 1 1 0 3
3 2 0 4 535-1

Система оцінювання

    Ця задача складається з чотирьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
117У Леді немає двох різних монет (монет різно- го номіналу), тобто лишу одне з чотирьох у вхідному файлі може бути ненульовим.
219Кількість монет кожного виду не більше 100.
321У Леді немає монет номіналом в 50 копійок.
443Обмеження з умови (кількості до 106, потрібно зібрати до 108).

Задача C. Рядки в Ужляндії

Ім’я вхідного файлу:strings.in
Ім’я вихідного файлу:strings.out
Обмеження по часу:0,5 секунди
Обмеження по пам’яті:64 Мб

    В Ужляндії знову щось трапилось! Сьогодні відзначає свій день посвяти у лицарі головний Ужляндський Лицар – Маша. За традицею їй задали головний Ужляндський рядок S довжини N, що складається з маленьких букв англійського алфавіту. Символи рядка пронумеровані від 1 до N.
    Щоб пройти щорічне випробування, Маші необхідно дістатися останнього елементу рядка, отриавши максимальну кількість балів. Правила випробування та нарахування балів такі:
  • Початкова позиція лицаря – елемент рядка з номером 1.
  • Лицар може перейти від позиції з номером j до позиції з номером i за умови 1 ≤ j < i ≤ N. За такий перехід він отримає (i - j)·|Si - Sj| балів, де |Si - Sj| позначає різницю між позиціями символів у алфавіті.
  • Кінцева позиція – елемент рядка з номером N.
    На жаль, журі випробовування не знає яку ж насправді максимальну кількість балів можна отримати. Саме тому воно доручило Вам знайти це значення.

Формат вхідних даних

    У першому рядку вхідного файлу знаходиться одне ціле число N (1 ≤ N ≤ 106) – довжина рядка S. У другому рядку знаходиться рядок S, що складається з маленьких букв англійського алфавіту.

Формат вихідних даних

    Виведіть одне число – максимальну кількість балів, яку можна отримати при проходженні випробування.

Приклади

strings.instrings.out
4
abca
6

7
abadedc
20

Система оцінювання

    Ця задача складається з п‘яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі, а також всі тести всіх необхідних для неї підзадач. Необхідні підзадачі також вказані в таблиці.

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
1201 ≤ N ≤ 15
2201 ≤ N ≤ 1000Необхідні підзадачі: 1.
3101 ≤ N ≤ 106; S може містити лише символи «a» та «b»Необхідні підзадачі: 0, 1, 2.
4201 ≤ N ≤ 105Необхідні підзадачі: 1, 2.
5301 ≤ N ≤ 106Необхідні підзадачі: 1, 2, 3, 4.

Задача D. Нова робота для Валл-І

Ім’я вхідного файлу:robot.in
Ім’я вихідного файлу:robot.out
Обмеження по часу:2 секунди
Обмеження по пам’яті:64 Мб

    Робот Валл-І влаштувався на нову роботу в невеличкий склад, що обслуговує компанію Замазо. Склад вже давно повністю автономний, тож на ньому працює лише 1 робот. На складі є всього N полиць, які занумеровані цілими числами від 1 до N. Всі полиці розташовані по одну сторону від доріжки, по якій рухається наш робот. Полиці не обов’язково розташовані в порядку зростання від початку доріжки.
    Робот Валл-І маж два контейнера: робочий та прокрастинаційний. Спочатку в робочому контейнері Валл-І знаходиться рівно N коробок, кожну з яких потрібно покласти на одну з полиць. На кожній коробці написаний номер, який означає на яку полицю потрібно її покласти. Кожного дня, коли робот починає працювати і йти повз полиці, він отримує в свій робочий контейнер коробки відсортовані в порядку зростання номерів, що на них написані. Робот може брати для обробки лише ту коробку, яка знаходиться вгорі робочого контейнера.
    Робот починає маршрут з полиці, яка розташована на початку доріжки. Зупиняючись біля кожної полиці, робот дивиться на номер полиці. Далі він або проходить мимо, або відкладає певну кількість коробок в прокрастинаційний контейнер і якщо вгорі залишається коробка, яку потрібно поставити на цю полицю, то він її ставить і йде далі. Валл-І не може брати коробки з прокрастинаційного контейнера.
    Наприклад, якщо Валл-І підійшов до полиці з номером 5, а верхню коробку потрібно поставити на полицю з номером 2, то він або прибирає в прокрастинаційний контейнер коробки 2, 3 та 4 і викладає коробку 5 на полицю, або проходить до наступної полиці. За один день Валл-І проходить по доріжці K разів, тому коли він доходить до її кінця, він розвертається і йде в зворотньому порядку, продовжуючи розставляти коробки.
    Програмне забезпечення Валл-І вже застаріле, він не здатен розставити коробки оптимально. Тому ми просимо Вас оновити його програмне забезпечення, тобто обрахувати яку максимальну кількість коробок теоретично може розставити Валл-І за 1 робочий день.

Формат вхідних даних

    В першому рядку вхідних даних знаходяться два числа N та K (1 ≤ N ≤ 105; 1 ≤ K ≤ 100) – кількість полиць на складі (кількість коробок в робочому контейнері відповідно) і кількість проходів робота за 1 день. В другому рядку вхідних даних знаходиться перестановка з N цілих чисел – номери полиць в порядку від початку до кінця доріжки.

Формат вихідних даних

    В єдиному рядку вихідних даних має бути єдине ціле число – максимальна кількість коробок, яку змоєе розатавити Валл-І за 1 робочий день.

Приклади

robot.inrobot.out
4 1
1 3 2 4
3

6 3
1 5 3 2 4 6
5

Пояснення до прикладів

    Перший приклад. За один прохід Валл-І може розставити не більше 3 коробок – поставити коробки 1, 2, 4 або 1, 3, 4.
    Другий приклад. За три проходи по доріжці Валл-І може розставити 5 коробок. Рухаючись перший раз від початку до кінця він розставить 1, 3, 4, в зворотньому порядку коробку 5, і третій раз, рухаючись зліва, коробку 6.

Система оцінювання

    Ця задача складається з трьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
127K = 1; N ≤ 1000
231K ≤ N &le 10; 1 ≤ N ≤ 10000
342K < 100; 1 < N < 10000

Задача E. Ліхтарі

Ім’я вхідного файлу:lanterns.in
Ім’я вихідного файлу:lanterns.out
Обмеження по часу:1,5 секунди
Обмеження по пам’яті:64 Мб

    Вулицю, на якій живе леді, освітлюють N ліхтарів, пронумерованих вздовж вулиці 1 до N. Один або кілька ліхтарів, що стоять підряд, назвемо сегментом. Таким чином, загальна кількість сегментів дорівнює (N·(N+1))/2. Сегмент вважається робочим, якщо лампочки в усіх ліхтарях цього сегмента працюють.
    З ліхтарями регулярно відбуваються події з двох типів:
  • в якомусь сегменті через стрибок напруги усі лампочки одночасно перегорають;
  • Леді вибирає деякий сегмент і викликає ремонтників, щоб вони замінили на ньому усі перегорілі лампочки.
    Після кожної такої події мерія міста, в якому живе Леді, вимагає від неї надати звіт про кількість робочих сегментів. Для покращення показників роботи ремонтників Леді включає у звіт усі сегменти, які є робочими на момент подання звіту або були робочими коли-небудь до цієї події.
    Напишіть програму, яка після кожної події визначить кількість сегментів у звіті Леді.

Формат вхідних даних

    У першому рядку вхідного файлу знаходяться два натуральних числа N і Q – кількість ліхтарів і кількість подій, що відбулись. Другий рядок вхідного файлу містить N символів «0» і «1», які описують початковий стан ліхтарів, де «1» означає ліхтар з робочою лампочкою, а «0» - з перегорілою.
    У кожному з наступних Q рядків міститься опис подій у вигляді трьох чисел Li, Ri, Ci, які означають, що після цієї події усі лампочки в ліхтарях Li, Li+1, … ,Ri
  • перегорають при Ci = 0,
  • замінюють на робочі при Ci = 1.
    В описах усіх подій 1 ≤ Li ≤ Ri ≤ N і Ci приймають значення 0 або 1.

Формат вихідних даних

    У першому рядку вихідного файлу виведіть єдине число – кількість дібчих сегментів в початковому стані. Потім по одному в рядку виведіть Q чисел: для кожної події, що відбулась виведіть кількість сегментів, вказаних у звіті після цієї події.

Приклад

lanterns.inlanterns.out
7 4
1100101
4 6 1
3 6 0
3 4 1
5 7 1
5
13
13
19
28

Система оцінювання

    Ця задача складається з п’яти підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
191 ≤ N ≤ 50; 1 ≤ Q ≤ 150
2111 ≤ N ≤ 500; 1 ≤ Q ≤ 250
3151 ≤ N ≤ 5000; 1 ≤ Q ≤ 1000
4201 ≤ N ≤ 50000; 1 ≤ Q ≤ 1000
5451 < N < 300000; 1 ≤ Q ≤ 300000

Наверх

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