2013-2014 рікю Інформатика (8–11 кл.)
Завантажити завдання і відповіді
ІІ етап Всеукраїнської учнівської олімпіади з інформатики
Завантажити завдання і відповіді
Завдання
ІІ етапу Всеукраїнської учнівської олімпіади з інформатики для учнів 8-11
класів
2013-2014
н.р.
A. Борг
|
Input file name:
|
debt.in
|
|
Output file name:
|
debt.out
|
|
Time limit:
|
100 ms
|
|
Memory limit:
|
128 M
|
Сьогодні
у Степана щасливий день – сусід по парті вернув борг A цукерок,
а молодший брат Мишко віддав B цукерок.
Степан
одразу одну цукерку з'їв, і одну дав Оленці. Скільки цукерок залишилось у
Степана?
Формат
вхідних даних: У єдиному рядку вхідного файлу міститься два
натуральних числа A i B (1 ≤ A, B ≤ 100).
Формат
вихідних даних: Виведіть у вихідний файл одне число – кількість
цукерок, що залишились у Степана.
Приклад
вхідних та вихідних даних:
|
debt.in
|
debt.out
|
|
2 5
|
5
|
B.
Нові правила оцінювання
|
Input file name:
|
new_rules.in
|
|
Output file name:
|
new_rules.out
|
|
Time limit:
|
100 ms
|
|
Memory limit:
|
128 M
|
Вчителька
математики Л.І. відома своєю демократичністю при оцінювання учнів. З першого
вересня цього року вона вирішила ввести нові правила оцінювання учнів при
захисті учнями рефератів з історії математики. Доповідь оцінюють усі учні
класу. Кожен учень виставляє оцінку від 1 до 100 (саме так, Л.І. практикує
100-бальну систему оцінювання). Після чого Л.І. відкидає одну найменшу і одну
найбільшу оцінку (для більшої об'єктивності).
Щоб
пришвидшити підрахунок результатів захисту, Л.І. просить Вас написати програму,
яка буде демонструвати оцінювання. Вона повинна виводити N оцінок,
які поставили учні, не змінюючи їх порядку, а потім їх суму, до того ж брати в
дужки ті оцінки, які не враховуються при розрахунку суми.
Формат
вхідних даних: Перший рядок вхідного файлу містить число N
(3 ≤ N ≤ 35) - кількість учнів, які оцінювали захист. Другий рядок
містить N чисел - оцінки, які поставили учні.
Формат
вихідних даних: Виведіть у вихідний файл ті ж числа в тому ж порядку,
взявши в дужки мінімальне (а якщо їх декілька - саме ліве з них) і максимальне
(а якщо їх декілька - саме праве з них) число, а також суму всіх чисел, не
взятих в дужки. Всі числа (включаючи суму) повинні бути надруковані в одному
рядку і розділені одним пропуском (усередині дужок пропусків бути не повинно).
Перед сумою повинен стояти знак рівності, відділений ліворуч і праворуч одним
пропуском. Порядок оцінок повинен бути такий же, як і у вхідних даних.
Приклад вхідних та вихідних даних:
|
new_rules.in
|
new_rules.out
|
|
5
1
2 3 4 5
|
(1)
2 3 4 (5) = 9
|
|
5
7
8 7 8 7
|
(7)
8 7 (8) 7 = 22
|
C. Розбиття числа
|
Input file name:
|
partition.in
|
|
Output file name:
|
partition.out
|
|
Time limit:
|
100 ms
|
|
Memory limit:
|
128 M
|
На
уроці математики Степан вивчив розбиття числа на класи. Але з усього, що
розповідала вчителька, він запам'ятав, що число слід розбивати по три цифри,
починаючи справа. Тепер він тренується – бере довільне ціле число і розділяє
комами трійки його цифр, починаючи справа.
Напишіть
програму, яка допоможе Степану у цій справі.
Формат
вхідних даних: У вхідному файлі міститься одне натуральне число N,
яке не перевищує 10100.
Формат
вихідних даних: У вихідний файл виведіть те ж число, розділяючи трійки
цифр комами.
Приклад
вхідних та вихідних даних:
|
partition.in
|
partition.out
|
|
1234
|
1,234
|
|
12345678
|
12,345,678
|
|
100
|
100
|
D. Модернізація
|
Input file name:
|
modernization.in
|
|
Output file name:
|
modernization.out
|
|
Time limit:
|
1000 ms
|
|
Memory limit:
|
128 M
|
У
зв'язку з модернізацією виробництва на заводі зубних щіток в Тау Кита було
прийнято рішення зробити перепис роботів, які обслуговують завод. Кожен робот
має два номери: основний і додатковий. Новий список має задовольняти таким
правилам:
1.
Якщо один робот у новому списку знаходиться раніше другого, то основний номер
першого менший або рівний основному номеру другого.
2.
Якщо основні номери роботів рівні, то вони розташовані в тому ж порядку, як і в
початковому списку.
Тау
Китяни звернулись до Вас з проханням переписати список. Допоможіть модернізації
організації!
Формат
вхідних даних: У першому рядку вхідного файлу знаходиться натуральне
число N (1 ≤ N ≤ 100 000) - кількість роботів на заводі.
Кожен
наступний рядок містить 2 числа - основний і додатковий номери чергового
робота. Обидва номера невід'ємні і не перевищують 109.
Формат
вихідних даних: Вихідний файл має містити N рядків.
Кожен рядок має містити 2 числа - основний і додатковий номер i-го
робота в новому списку.
Приклад
вхідних та вихідних даних:
|
modernization.in
|
modernization.out
|
|
10
1
8
8
9
2
10
1
11
4
2
7
2
3
11
2
23
3
3
6
7
|
1
8
1
11
2
10
2
23
3
11
3
3
4
2
6
7
7
2
8
9
|
E. Точки
|
Input file name:
|
pixel.in
|
|
Output file name:
|
pixel.out
|
|
Time limit:
|
100 ms
|
|
Memory limit:
|
128 M
|
Степан
і Мишко грають в "точки". Степан позначає на листочку паперу в
клітинку кілька точок - вузлів сітки. Мишко хоче окружити їх многокутником так,
щоб усі позначені вузли лежали строго в середині (не на межі) цього
многокутника і щоб усі сторони цього многокутника проходили тільки по сторонах
або діагоналях клітинок сітки, а його периметр був мінімальним.
Визначте
периметр цього многокутника.
Формат
вхідних даних: На першому рядку вхідного файлу знаходиться
число N (1 ≤ N ≤ 100 000) - кількість позначених
Степаном точок.
У
кожному із наступних N рядків записано по два
числа Xi, Yi - координати точок,
позначених Степаном. Координати по абсолютній величині не перевищують 106.
Деякі точки можуть співпадати.
Формат
вихідних даних: У вихідний файл виведіть одне число - периметр
шуканого многокутника з точністю не менше 0.001.
Приклад
вхідних та вихідних даних:
|
pixel.in
|
pixel.out
|
|
1
0
0
|
5.656
|
|
2
1
1
1
2
|
7.656854
|
ІІ етап Всеукраїнської учнівської олімпіади з інформатики
2014-2015 н.р.
Друзі Степана
Time limit:
|
100 ms
|
Memory limit:
|
128 M
|
Степан повернувся з міжнародної олімпіади школярів з
програмування (ІОІ) і привіз з собою N різнокольорових
каменів в якості сувенірів. Степан зовсім не жадний хлопчик, тому вирішив
поділитися камінням зі своїми друзями. Кожному другу Степан віддав рівно один
камінь. Виявилося, що у самого Степана залишився теж тільки один камінь.
Визначте, скільки ж у нього друзів?
Вхідні дані: У першому рядку задано число N (1 ≤ N ≤ 100).
Вихідні дані: Виведіть одне число - кількість друзів Степана.
Пояснення до прикладу: Степан привіз 2 каменя, один з яких залишився у нього.
Отже, другий камінь Степан віддав своєму єдиному другу.
Приклад
Введення
|
Виведення
|
2
|
1
|
Факультатив з інформатики
Time limit:
|
100 ms
|
Memory limit:
|
128 M
|
Степан вирішив додатково позайматись програмуванням і
записався на факультатив з інформатики. Він записав у щоденник час початку
заняття (години, хвилини і секунди) та час закінчення (години, хвилини і
секунди). Тепер його цікавить скільки годин, хвилин і секунд він буде задіяний
на факультативі?
Формат вхідних даних: У
першому рядку записані три цілих числа A, B, C (0 ≤ A ≤ 23, 0 ≤ B ≤
59, 0 ≤ C ≤ 59) - час початку заняття в годинах, хвилинах і
секундах.
У другому рядку записані три цілих числа G, H, S (0 ≤ G ≤ 23, 0 ≤ H ≤ 59, 0 ≤ S ≤ 59) - час закінчення заняття в годинах, хвилинах і секундах.
У другому рядку записані три цілих числа G, H, S (0 ≤ G ≤ 23, 0 ≤ H ≤ 59, 0 ≤ S ≤ 59) - час закінчення заняття в годинах, хвилинах і секундах.
Формат вихідних даних: Три
цілих числа - тривалість заняття в годинах, хвилинах і секундах.
Приклад
Введення
|
Виведення
|
12 30 10
13 50 15
|
1 20 5
|
Улюблена гра
Time limit:
|
1000 ms
|
Memory limit:
|
128 M
|
За своє життя Степан пограв у величезну кількість
ігор. Одного разу він вирішив з'ясувати, яка ж гра у нього є улюбленою. Для
цього він вирішив порахувати сумарний час, проведений за кожною грою. Та, за
якою він провів найбільше часу, і є улюбленою.
На щастя, Степан щодня вів щоденник, у якому записував
кількість хвилин, проведених за кожною грою. Тому йому не складе труднощів
знайти гру, в яку він грав сумарно найбільше часу. Для простоти Степан
пронумерував всі ігри цілими числами.
Гарантується, що улюблена гра єдина.
Вхідні дані: У першому рядку міститься натуральне число N (1 ≤ N ≤ 1000) -
кількість записів у щоденнику Степана. У кожному з наступних N рядків
містяться записи із щоденника Степана - пара чисел Xi, Yi,
які показують, що Степан провів за грою Xi рівно Yi хвилин
(1 ≤ Xi, Yi ≤ 1000).
Вихідні дані: Виведіть одне число - номер улюбленої гри Степана.
Приклад
Введення
|
Виведення
|
3
1 10
2 20
1 5
|
2
|
4
1 10
3 31
1 20
2 25
|
3
|
Плагіат
Time limit:
|
1000 ms
|
Memory limit:
|
128 M
|
Учасники Всесвітнього Змагання з Програмування
відправили N файлів-розв'язків до тестуючої системи. До
того, як затвердити результати, журі хоче виключити будь яку можливість
плагіату. Для цього у них є програма, що порівнює два файли - розв'язки та
вирішує наскільки вони схожі.
Не дивлячись на це, кількість файлів досить велика і
перевірка усіх пар розв'язків забрала б дуже багато часу. З іншого боку, багато
таких пар можуть бути відкинуті через різницю у розмірах файлів.
Більш точно, журі вирішило не порівнювати такі пари
файлів, де менший файл становить менше ніж 90% від розміру більшого файлу. Нарешті,
порівняльна програма має перевірити лише такі пари різних файлів(f[i], f[j]),
де i ≠ j, size(f[i])≤size(f[j]) та size(f[i])≥
0.9*size(f[j]).
Напишіть програму, що знаходитиме кількість пар
розв'язків, що потрібно буде перевірити.
Вхідні дані: Перший рядок містить ціле число N, кількість розв'язків,
що були відправлені. Наступний рядок містить N чисел size(f[1]),..,
size(f[N]), що означають розміри кожного з файлів.
Вихідні дані: Виведіть кількість пар, що потрібно окремо перевірити.
Обмеження:
1 ≤ N ≤ 100000, 1 ≤ size(f[i]) ≤ 1000000000
Рішення, що працюють при 1 ≤ N ≤ 2000, будуть
оцінюватися з 50 балів.
Приклад
Введення
|
Виведення
|
2
2 1
|
0
|
5
1 1 1 1 1
|
10
|
Скарби та вікінги
Time limit:
|
1 s
|
Memory limit:
|
128 M
|
У Вас є карта скарбів, що являє собою сітку
розміром N x M. Клітинка сітки може бути як частиною моря,
так і суші. До того ж на карті вказані місце знаходження скарбів та корабля
ворожих вікінгів, що займає одну клітинку моря. Також, для зручності Ви нанесли
на карту своє місцезнаходження.
Зараз Ви маєте скласти шлях, щоб дістатися скарбів.
Шлях має починатися у Вашій початковій позиції, закінчуватися в клітинці зі
скарбами та складатися з послідовності рухів. За кожен рух Ви можете
переміститися у сусідню клітинку по вертикалі чи горизонталі, якщо вона не є
частиною суші. Але обережно: корабель вікінгів може переслідувати Вас,
використовуючи такий же спосіб переміщення. Після кожного руху, що належить
вашому шляху, корабель вікінгів може як рухатись, так і не рухатись.
- Якщо Ви на одній лінії з кораблем вікінгів (Ви на одній
вертикальній чи горизонтальній лінії, а між вами та вікінгами лише море), то Ви
мертві.
- Якщо Ви не мертві та дісталися до скарбів, то вони
Ваші.
Напишіть програму, що вирішує чи можливо вибрати такий
шлях заздалегідь, що Ви дістанетесь скарбів незалежно від того, як буде
рухатись корабель вікінгів.
Вхідні дані: Перший рядок містить два цілих числа N та M -
розміри карти. Кожен з наступних N рядків містить
по M символів. Кожен символ описує клітинку карти, це
може бути .(море), I(суша), V(корабель
вікінгів), Y(Ваша позиція) або T(скарби).
Символи V, Y та T з'являться в
точності один раз.
Вихідні дані: Єдиний рядок має містити YES, або NO, в залежності від того, чи можливо
скласти безпечний маршрут.
Обмеження:
1 ≤ N, M ≤ 700
Система оцінювання:
В
даній задачі 9 блоків, кожен блок оцінюється окремо. Бали нараховуються тільки
за умови проходження усіх тестів блоку.
Перший
блок - тести з умови - оцінюється в 0 балів.
Другий
блок - 1 ≤ N, M ≤ 63 - оцінюється в 12 балів.
Третій
блок - 1 ≤ N, M ≤ 122 - оцінюється в 12 балів.
Четвертий
блок - 1 ≤ N, M ≤ 180 - оцінюється в 12 балів.
П'ятий
блок - 1 ≤ N, M ≤ 200 - оцінюється в 12 балів.
Шостий
блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів.
Сьомий
блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів.
Восьмий
блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів.
Дев'ятий
блок - 1 ≤ N, M ≤ 700 - оцінюється в 13 балів.
Приклади
Введення
|
Виведення
|
5 7
Y.....V
..I....
..IIIII
.......
...T...
|
YES
|
5 7
Y....V.
..I....
..IIIII
.......
...T...
|
NO
|
2 3
.YT
VII
|
NO
|
Немає коментарів:
Дописати коментар