Субота, 15.05.2021, 16:26
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 60
Головна » 2018 » Лютий » 5 » 1 Тур. Всеукраїнська олімпіада з інформатики ІІІ (обласний етап). 03/02/2018
19:05
1 Тур. Всеукраїнська олімпіада з інформатики ІІІ (обласний етап). 03/02/2018

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

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

Задача А. Рівняння

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

    Леді написала у свій електронний зошит з математики рівняння, що містить три цілих числа, знак рівності та одну з чотирьох основних арифметичних операцій (додавання, віднімання, множення і ділення). На жаль, вірус знищив знак рівності та операції з ноутбука Леді.
    Допоможіть Леді відновити рівняння з трьох цілих чисел.

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

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

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

    Виведіть знайдене рівняння, яке містить три цілих числа (в тому ж порядку), знак «дорівнює» і одну з чотирьох операцій. Якщо є декілька рішень, виведіть будь-яке з них.

Приклади

equation.inequation.out
5 3 85+3=8
5 15 35=15/3

Задача В. Ланч-бокси

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

    Леді працює менеджером ресторану. В ресторані приготували N ланч-боксів і Леді планує роздати їх в деякі школи. Припустимо, що є M шкіл та i-та школа замовляє ki ланч-боксів.
    Леді намагається поширювати ланч-бокси для максимально можливої кількості шкіл. Крім того, Леді забобонна, а тому в неї є правило – для і-ої школи вона дає або нуль або ki ланч-боксів.
    Напишіть програму, яка допоможе Леді знайти максимальну кількість шкіл, які зможуть отримати ланч-бокси?

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

    Перший рядок вхідного файлу містить 2 цілих числа N i M. Далі йдуть M рядків: і-й рядок містить ціле число ki.

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

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

Приклад

boxes.inboxes.outПояснення
10 4
3
9
4
2
3




Ланч-бокси зможуть отримати перша, третя та четверта школи.


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

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

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
120M = 1; 1 ≤ N ≤ 60000; 1 ≤ ki ≤ 30000
2301 ≤ M ≤ 1000;1 ≤ N ≤ 60000;1 ≤ i ≤ 1000
3501 ≤ M ≤ 60000;1 ≤ N ≤ 60000;1 ≤ i ≤ 30000

Задача C. Магічний набір

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

    Леді дуже довго відкладала кошти на те, щоб купити собі магічний набір відрізків. Набір вважається магічним, якщо у наборі рівно N відрізків та кожна пара відрізків має спільну точку.
    Коли вона назбирала необхідну суму та купила набір, відразу ж вирішила пограти з ним. Це було просто неймовірно! Але сталось те, чого вона ніяк не могла передбачити: кола вона пішла їсти, її мале Нька сестра Марічка підкинула туди ще один відрізок та перемішала набір, то ж Леді не знає, який саме відрізок підкинула Марічка. Вона дуже розізлилася на сестру, але що поробиш – доведеться видалити з набору один відрізок, що лежать перед нею, визначить, який саме відрізок треба видалити.

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

    У першому рядку задається єдине число N (1 ≤ N ≤ 105) – кількість відрізків у магічному наборі. Далі йде N + 1 рядок, де рядок з номером i містить два числа, Li, Ri (1 ≤ Li ≤ Ri ≤ 109) – кінці відповідного відрізку. Відрізки прнумеровані починаючи з 1.

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

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

Приклади

magic.inmagic.out
2
1 2
2 3
4 5
3



1
1 2
2 3
1


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

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

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
1131 ≤ N ≤ 500
2141 ≤ N ≤ 105; відрізок Марічки не перети-
нається з жодним іншим
3211 ≤ N ≤ 104;1 ≤ Li ≤ Ri ≤ 100
4521 ≤ N ≤ 105

Задача D. Футбол в Ужляндії

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

    В Ужляндії знову щось трапилось! Усі жителі країни очікують гру між збірними Ужляндії та Океанії з футболу.
    Відомо, що футбольне поле – це матриця, що містить N та M стовпців. Рядки матриці пронумеровані зверху вниз, стовпці – зліва направо. Команда Ужляндії складається з Q гравців. Кожен гравець характеризується ділянкою поля, у межах якої він гратиме. Також відомо, що така ділянка є прямокутником, сторони якого паралельні сторонам матриці.
    Вважається, що два гравці зіграні, якщо перетин ділянок, у межах яких вони рядків грають, непорожній. Іншими словами, два гравці зіграні, якщо існує елемент матриці, який належить обом прямокутникам, що характеризують цих гравців. Зіграністю команди вважається кількість пар гравців, що є зіграними.
    Президент Ужляндії вирішив дізнатись зіграність збірної команди Ужляндії з футболу. Але, оскільки у нього багато справ, він доручив це завдання Вам.

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

    У першому рядку вхідного файлу знаходиться два цілих числа N та M – кількість рядків та стовпців відповідно. У другому рядку знаходиться одне ціле число Q – кількість гравців у збірній команді Ужляндії з футболу.
    У наступних Q рядках знаходиться по чотири цілих числа x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ N; 1 ≤ y1 ≤ y2 ≤ M), що описують ділянку у межах якої гратиме відповідний гравець у наступний спосіб: (x1, y1) – координата лівої верхньої клітинки прямокутника, а (x2, y2) – координата правої нижньої клітинки прямокутника.

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

    Виведіть одне число – зіграність збірної команди Ужляндії з футболу.

Приклад

football.infootball.out
3 4
4
1 1 1 2
1 1 3 3
2 2 3 3
2 3 3 4
4





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

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

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
1201 ≤ Q ≤ 1000
2301 ≤ N ≤ 7; 1 ≤ M ≤ 7
3501 ≤ N ≤ 1000; 1 ≤ M ≤ 10000; 1 ≤ Q ≤ 106

Задача E. Радіоактивні банани

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

    У коров’ячому селі кожна корова володіє одним будинком. Ці будинки розташовані по прямій лінії. N будинків позначено від 1 до N в порядку їх віддалення від центру села, починаючи з будинку, найближчого до центру села.
    Бананів у Леді багато – вистачить усім коровам, і сьогодні вона дуже щедра! Вона вирішила роздати коровам частину своїх бананів.
    Однак, як ми всі знаємо, банани є радіоактивними. Що ще гірше, банани Леді особливо радіоактивні, тому що вона живе поруч з екватором, де середній потік космічних променів найвищий. Якщо надто багато бананів Леді розміщувати в безпосередній близкості один від одного, вони можуть викликати ядерний вибух, який, бузсумнівно, призведе до погіршення іміджу Леді. Леді зберігає свої банани в маленьких коробочках, але їй доведеться відкрити їх, якщо вона хоче віддати їх коровам. Щоб запобігти ядерному вибуху, Леді повинна розподілити свої банани відповідно до таких правил:
  • Корова отримує не більше одного банану.
  • Не більше, ніж С корів, що мають послідовні номери будинків, всі можуть отримати банани.
    Так, наприклад, якщо N = 4 і C = 2, Леді може дати банан кожній корові у бідинках 1, 2 і 4, але вона не може дати по банану усім коровам в будинках 2, 3 і 4, тому що будинки 2, 3 та 4 розташовані поруч один з одним, і виникає ядерний вибух.
    Леді хоче, знайти кількість способів розподілити свої банани між коровами, по модулю 1 000 000 007. Зверніть увагу, що немає обмежень на кількість бананів, які Леді може роздавати коровам – зокрема, Леді може не дати коровам взагалі бананів.

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

    Єдиний рядок вхідного файлу містить два додатних числа: N – кількість бананів і C – кількість послідовних будинків, які можуть отримати банани, не викликаючи ядерного вибуху.

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

    У вихідний файл виведіть одне число – кількість способів, якими Леді може розподілити свої банани між коровами по модулю 1 000 000 007.

Приклади

radioactive.inradioactive.outПояснення
4 2



13



Існує 13 наборів номерів будинків, які задовольняють наведеним вище правилам: {1,2,4}, {1,3,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1}, {2}, {3}, {4}, {}.
3 1





5





Існує 5 наборів номерів будинків, які задовольняють наведеним вище правилам: {1,3}, {1}, {2}, {3}, {}. Зверніть увагу, що {1,3} дозволено, оскільки будинки 1 та 3 не розташовані поруч один з одним, тому ядерного вибуху не відбудеться.
3 5





8





Леді не потрібно турбуватися про друге правило, оскільки немає п’яти номерів послідовних будинків. Таким чином, усі 8 підмножин задовольняють наведеним в умові правилам: {1,2,3}, {1,2}, {1,3}, {2,3}, {1}, {2}, {3}, {}.

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

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

№ підзадачіБалиОбмеженняПримітка
00 Тести з умов
190 < N < C < 200
220 ≤ N ≤ 106; C = 1
350 < N < 16; 0 < C < 16
470 < N < 105; 0 < C < 20
5190 < N < 106; 0 < C < 200
6120 < N < 1018; C = 1
7130 < N < 1018; 0 < C < 50
8330 < N < 1018; 0 < C < 200

Наверх

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