26 листопада 2017р. відбулась районна учнівська олімпіада з інформатики (програмування). Як і кожного року учасники олімпіади мали змогу в режимі онлайн тестувати свої розв’язки на сайті http://algotester.com/en. Крім цього після закінчення олімпіади будь-хто зможе попробувати розв’язати дані завдання на сайті алготестер. Пропонуємо переглянути цьогорічні завдання з програмування.
Перегляунти олімпіадні завдання з інформатики 2017-2018 н.р. (програмування)
Задача А. Дзідзьо і його пісня
Обмеження: 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
Примітки