Вінницька обласна олімпіада з інформатики 2012 року

Задача A

Решта

Ні для кого не секрет, що Марічка для Зеника є сенсом його життя. Він заради неї ладен на все і нічого не пошкодує для того, щоб Марічка була щасливою.

Одного разу Зеник вирішив придбати Марічці дороге намисто у розкішному магазині в самісінькому центрі Львова. Біля каси він гонорово витягнув купюру вартістю 500 гривень. Продавець має багато купюр наступних вартостей: 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень. Він дасть Зеникові решту таким чином, щоб використати якомога меншу кількість купюр.

Намисто коштує N гривень. Вам необхідно визначити яку кількість купюр отримає Зеник від продавця.

Вхідні дані:

Єдине ціле число N.

Вихідні дані:

Єдине число – кількість купюр, що отримає Зеник.

Обмеження:

1 ≤ N ≤ 500.

Приклад вводу:

47

Приклад виводу:

5

Підказка:

Продавець дасть решту Зеникові наступним чином: дві купюри по 200 гривень та по одній купюрі 50, 2 та 1 гривню.

Задача B

Без шестірок

З часом Зеник усвідомив одну просту річ – якщо він і надалі буде задовольняти забаганки Марічки такими темпами, то йому потрібно буде або лотерею вигравати, або в рабство йти. Довго не думаючи, Зеник вибрав перший варіант.

Зеник придбав пачку лотерейних квитків. Кожен квиток має серійний номер. Ці номери у пачці йдуть підряд, починаючи з номера A та закінчуючи номером B. По незрозумілих причинах Зеник вирішив, що якщо у серійному номері квитка зустрічається цифра 6, то такий квиток є нещасливим і має бути знищеним. Почухавши потилицю, Зеник спалив усі квитки з пачки, серійні номери яких містили хоча б одну цифру 6. Вам необхідно визначити скільки квитків залишилось у Зеника.

Вхідні дані:

Два цілих числа A та B через пробіл.

Вихідні дані:

Єдине число – кількість квитків, що залишилися у Зеника.

Обмеження:

1 ≤ A ≤ B ≤ 1000000000000000000 (10¹⁸).

Приклад вводу:

1 100

Приклад виводу:

81

Підказка:

Зеник спалить наступні квитки: 6, 16, 26, 36, 46, 56, 60-69, 76, 86, 96.

Задача C

Солодкі слова

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

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

Вам відомі всі солодкі для Марічки слова. Вам необхідно скласти нове солодке слово якнайменшої довжини, яке б містило всі попередні солодкі слова як підрядки. Якщо таких слів декілька – оберіть лексикографічно найменше (яке зустрінеться першим у словниковому порядку).

Вхідні дані:

Перший рядок містить ціле число N – кількість солодких для Марічки слів. Наступні N рядків містять по одному солодкі слова S₁, S₂, ..., S_N.

Вихідні дані:

Нове солодке слово.

Обмеження:

1 ≤ N ≤ 10,

всі S_i містять тільки маленькі латинські літери (‘a’-‘z’),

всі S_i мають довжини від 1 до 10 включно,

всі S_i різні.

Приклад вводу:

3

princess

mara

rama

Приклад виводу:

maramaprincess

Підказка:

Серед усіх можливих варіантів з найкоротшою довжиною maramaprincess, ramaraprincess, princessmarama та princessramara перший є лексикографічно найменшим.

Задача D

Жахливий сон

Нещодавно Зеникові приснився жахливий сон. Він та Марічка опинилися у величезній прямокутній кімнаті з дуже злими собаками. На щастя собацюри у тому сні спали, але як тільки хтось опиниться на відстані D чи ближче до собаки, то вона прокинеться і тоді вже почнеться справжній жах.

Уявіть собі, що стіни кімнати є паралельними осям координат, лівий нижній кут кімнати має координати (0, 0), а правий верхній (W, H). Кімната є дуже великою, тому Зеника, Марічку та собак можна вважати точками на площині.

Зеник знаходиться у лівому нижньому кутку кімнати, а Марічка - у правому верхньому. Виходити за межі кімнати вони не можуть. Вам відомі координати собак. Необхідно визначити при якому найменшому значенні параметра D Зеник не зможе дістатися до Марічки так, щоб не розбудити жодну з собацюр.

Вхідні дані:

Перший рядок містить три цілих числа W, H та N через пробіл. Тут N – це кількість собак у кімнаті. Кожен з наступних N рядків містить два цілих числа x_i та y_i через пробіл. Тут (x_i, y_i) – це координати i-тої собаки.

Вихідні дані:

Єдине число – шукане найменше значення параметра D. Результат необхідно вивести з чотирма знаками після коми, використовуючи для заокруглення стандартні математичні правила.

Обмеження:

2 ≤ W, H ≤ 1000,

1 ≤ N ≤ 1000,

0 < x_i < W,

0 < y_i < H,

всі (x_i, y_i) різні.

Приклад вводу:

15 20 2

2 7

7 3

Приклад виводу:

3.2016

Підказка:

При меншому параметрі D Зеник міг би пройти між двома собаками так, щоб їх не розбудити.