Завдання II етапу Всеукраїнської районної олімпіади з інформатики (програмування) 2017-2018 н.р.

26 листопада 2017р. відбулась районна учнівська олімпіада з інформатики (програмування). Як і кожного року учасники олімпіади мали змогу в режимі онлайн тестувати свої розв’язки на сайті http://algotester.com/en. Крім цього після закінчення олімпіади будь-хто зможе попробувати розв’язати дані завдання на сайті алготестер. Пропонуємо переглянути цьогорічні завдання з програмування.

Перегляунти олімпіадні завдання з інформатики 2017-2018 н.р. (програмування)

Завантажити (PDF, 308KB)

 

Олімпіада з програмування 2017

Олімпіада з програмування 2017

Задача А. Дзідзьо і його пісня

Обмеження: 1 сек., 256 МіБ

Мегапопулярний Дзідзьо дуже любить складати мегаиоиулярні пісні. Запис його пісень є специфічним: він записує усі слова своєї пісні без пропусків та розділових знаків у єдину стрічку.

Одного разу, переглядаючи текст пісні, Дзідзьо видалив один символ з неї і помітив, що пісня стала зовсім іншою. Допитливому Дзідзю стало цікаво, скільки різних пісень може утворитись із заданої, якщо видалити з неї тільки один символ. Але Дзідзьо не має часу для того, щоб це рахувати. Допоможіть йому, напишіть для цього програму.

Вхідні дані

У першому і єдиному рядку задано стрічку 5. Вона складається тільки з малих літер англійського алфавіту (а – г).

Вихідні дані

Виведіть єдине число — відповідь на задачу.

Обмеження

2 <|8|< 100, де |5| — довжина стрічки 5.

Приклади
Вхідні дані (stdin) Вихідні дані (stdout)
abc 3

Примітки

У першому прикладі, зі стрічки abc може утворитись 3 різні стрічки, якщо з неї видалити один символ: bс, ас, ab.

 

Задача В. Дзідзьо і вівці
Обмеження: 1 сек., 256 МіБ

“Все своє життя я мріяв стати великим артистом. Мати круту машину, солідний костюм і саме основне — щоби мною гордилась Мама!”

Так склалось, що Мама нашого героя любить поєднання жовтого і блакитного кольору. У Мами в селі є дуже велике поле — координатна площина. Окрім цього, у Мами є N + М стад овець. Із незрозумілих нам причин N стад було блакитного кольору, а М — жовтого. Для кожного стада є один визначений прямокутник (паралельний осям координат), на якому воно полюбляє пастися.

Дзідзьо помітив: якщо в якійсь точці будуть пастись і жовті і блакитні вівці, то вони утворять красиве поєднання жовтого і блакитного. Дзідзьо хоче обрати одне стадо блакитного кольору і одне стадо жовтого кольору так, щоб загальна площа, де будуть знаходитись і жовті і сині вівці, була якомога більшою. Однак, це завдання виявилось йому не під силу. До того ж, у Дзідзьа виникли проблеми на митниці, тому він просить Вас про допомогу.

Вхідні дані

У першому рядку задано два цілі числа N та М, розділені одним пропуском — кількість стад блакитного та жовтого кольору відповідно.

Наступні N рядків описують улюблені пасовища овець блакитного кольору. Кожен рядок містить 4 цілі числа, розділені пропуском — х\, у і, х2 та у2 — координати лівої нижньої та правої верхньої точки прямокутника відповідно.

М

форматі.

Вихідні дані

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

Якщо є декілька оптимальних відповідей, ви можете вивести будь-яку з них.

Обмеження

N, М > 1,

50% тестів: шах^, М) < 10 та 0 < |хі|, |х2|, |уі|, |у21 < 103,

50% тестів: 10 < шax(N, М) < 100 та 103 < |хі|, |х2|, |уі|, |у2| < 109.

Приклади
Вхідні дані (віЯіп) Вихідні дані (віЯоиі)
2 2 1 2
0 0 4 4
4 4 7 7
2 2 5 5
0 0 4 2
1 1 1 1
0 0 5 5
5 5 10 10

 

 

Завдання С. Дзідзьо і планета Олімпія
Обмеження: 2 сек., 256 МіБ

Мегапопулярний Дзідзьо завітав на планету Олімпія, де живе багато прихильників спорту. Важка атлетика — найбільш популярна серед мешканців Олімпії. Дзідзьо, палкий фанат цього виду спорту, не раз був суддею на змаганнях.

Цікаво, що на цій планеті й дуже дивні правила підрахунку суми двох чисел. Так, сумою двох чисел вважають найменше спільне кратне цих чисел. Найменше спільне кратне натуральних чисел а та Ь — це таке найменше натуральне число, яке ділиться націло на а і Ь, тобто сума 2 і 4 це зовсім не 6, а 4. У важкій атлетиці правила визначення переможця доволі прості: є дві вправи за кожну з яких даються певні бали у вигляді додатного цілого числа. У кого більша сума цих балів, той і виграє.

Одного разу, під час змагань з важкої атлетики, Дзідзьо зумів записати тільки суму X переможця. Тепер його цікавить, скільки існує таких пар чисел, що в сумі (за правилами планети

Олімпія) дають число X.

Вхідні дані

У першому і єдиному рядку задано ціле число X — сума двоборства спортсмена.

Вихідні дані

Виведіть єдине число — відповідь на задачу.

Обмеження

20% тестів: 1 < X < 102,

40% тестів: 1 < X < 104,

40% тестів: 1 < X < 107.
Приклади
Вхідні дані (віЯіп) Вихідні дані (віЯоиі)
47 3
6 9

Примітки

У другому прикладі існує 9 тар: (1, 6) (2, 6) (3, 6) (6, 3) (6, 2) (6,1) (2, 3) (3, 2) (6, 6).

 

Задача D. Дзідзьо і зустріч з фанатами
Обмеження: 1 сек., 256 МіБ

Після концерту у надзвичайно дивній країні, Дзідзьо вирішив роздати кілька автографів своїм палким фанатам. Він зовсім недавно думав над новим лого своєї групи (див. Примітки), тому вирішив, що його автограф буде складатися лише з нових логотипів. Щоб фанат отримав максимальне задоволення від автографу, повинні виконуватися наступні дивні умови:

1. Автограф — це сітка розмірами п на т.

2. У кожній клітинці повинно бути рівно одне лого.

3. Кількість точок, в яких закінчується лише одна стрілка логотипу повинна бути мінімальною.

З першими двома умовами Дзідзьо розібрався одразу, а з третьою він звернувся до вас. Напишіть програму, яка допоможе йому порахувати мінімальну можливу кількість таких точок. Розмір логотипу 1 на 1. Логотип можна повертати на 90, 180 та 270 градусів.

Вхідні дані

У першому рядку задано ціле число Т — кількість фанатів.

В наступних Т рядках записано по 2 цілих числа Пі,ті — розміри автографу, який хоче і-ий фанат.

Вихідні дані

Для кожного фаната в окремому рядку виведіть мінмальну можливу кількість точок, в яких закінчується рівно одна стрілочка.

Обмеження

1 < Т < 100,

35% тестів: 1 < пі,ті < 103,

65% тестів: 1 < пі,ті < 109.

Приклади
Вхідні дані (віЯіп) Вихідні дані (віЯоиі)
3 3
1 1 2
1 2 0
4 3

Примітки

Поділитись у соціальних мережах:Share on Facebook0Share on Google+0Tweet about this on Twitter

Коментарі із Facebook

Powered by Facebook Comments

Сподобалась стаття? Оцініть її:

1 Star2 Stars3 Stars4 Stars5 Stars (голосов: 2, в среднем: 3,00 из 5)
Loading...
 

Вам також має сподобатись...

Залишити відповідь