1. Завдання особистої олімпіади

Числа Сміта (Smith)  (юніори)

Поняття числа Смита було введено Альбертом Віланскі з Університету Лехай у 1982 році. Переглядаючи свою телефонну книжку, математик звернув увагу на те, що телефонний номер його зятя Гарольда Сміта (493-7775) має таку цікаву властивість, що сума його цифр дорівнювала сумі цифр усіх його простих співмножників. Число 4937775 розкладається на прості співмножники таким чином: 4937775=3×5×5×65837. Сума цифр телефонного номера дорівнює 4+9+3+7+7+7+5=42 і сума цифр його розкладання на прості множники також дорівнює 3+5+5+6+5+8+3+7=42. Віланскі назвав такий тип чисел на ім’я свого зятя. Оскільки таку властивість мають всі прості числа, Віланскі не включив їх до означення. Допоможіть Альберту знайти ще числа Сміта. Для кожного числа із заданого набору знайдіть мінімальне число Сміта, що його перевищує.

Формат введення-виведення: 

Програма Smith зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤10) – кількість чисел у наборі, а також N натуральних чисел a_i (1≤ a_i <2³¹).  Програма Smith виводить на екран (стандартний пристрій виведення) N знайдених чисел через пробіл.

Приклад вхідних та вихідних даних

Введення                           Виведення

2 4937774 234                   4937775 265

Обнулення масиву (Zeroing)  (юніори+ старша ліга)

Є масив, що складається з N чисел. За один крок дозволяється зменшити на 1 кілька (можливо один) підряд рівних елементів. Мета – зробити всі елементи рівними нулю. За яку мінімальну кількість кроків це може бути зроблено? 

Формат введення-виведення:  Програма Zeroing зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤2∙10⁵) – кількість чисел у масиві, а з наступного рядка N невід’ємних цілих чисел, елементів масиву, кожне з яких не перевищує 2∙10⁹. Програма Zeroing виводить на екран (стандартний пристрій виведення) єдине число – шукану кількість кроків.

Приклад вхідних та вихідних даних

Введення 1            Виведення 1

3                                 4

3 4 1

Введення 2            Виведення 2

3                                 6

3 1 4

Кооперація (Coop)  (юніори+ старша ліга)

Гноми-велетні знамениті своїми гігантськими розмірами та любов'ю до золота. В одному з поселень гномів існує N пар гномів, причому в i-ій (1 ≤ i ≤ N) парі як чоловік-гном, так і жінка-гном мають зріст рівно i. Крім того, кремезні чоловіки-гноми зазвичай виступають у якості опори, у той час як тендітні жінки-гноми вправно орудують киркою. Геологічна розвідка виявила неподалік селища гномів вертикальну нескінченно високу скелю. Гноми вирішили, що там з великою вірогідністю буде золото, тож домовилися вранці вирушити на полювання на нього. Щоправда, дійшовши до скелі, гноми виявили проблему: K сімей не прийшли на зустріч. Гноми збираються довбати скелю в наступний спосіб: нехай якийсь чоловік-гном зросту A виступає опорою для якоїсь жінки-гнома зросту B. Разом цей тандем здатний довбати скелю лише на висоті A + B. Для кожної висоти обирається підходящий тандем, причому будь-який присутній гном може виступати (в різні моменти часу) у складі різних тандемів. Тепер гномів цікавить, скільки ж існує досяжних висот. Іншими словами, для скількох висот знайдеться підходящий тандем?

Формат введення-виведення: Програма Coop спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N(1 ≤ N ≤ 2·10⁹) та K (1 ≤ K ≤ min{N, 10000}) – кількість пар гномів у поселенні та кількість відсутніх на видобутку сімей гномів.Потім зчитується рівно K різних невід’ємних цілих чисел – номери сімей, у довільному порядку, що не прийшли на видобуток. Кожне число не перевищує N.Програма Coop виводить на клавіатуру (стандартний пристрій виведення) єдине ціле число – кількість досяжних висот.

Система оцінки.  30% балів припадає на тести, в яких N, K ≤ min{N, 1000}.  Ще 40% балів припадає на тести, в яких N ≤ 10⁹, K ≤ min{N, 500}.

Приклад вхідних та вихідних даних:

Введення 1                        Виведення 1

6 2                   9

3 6

Введення 2                        Виведення 2

5 3                   3

2 3 4

Введення 3                        Виведення 3

10 4                 15

2 3 4 5

Багатокутники (Numconv)  (юніори+ старша ліга)

Задана клітчаста сітка. Скільки різних опуклих багатокутників може бути на ній намальовано, якщо всі вершини повинні лежати у вузлах сітки, а сторони бути або горизонтальними, або вертикальними, або діагональними (під кутом 45 градусів)? Шириною сітки назвемо кількість вузлів у кожному її ряду, а висотою – кількість вузлів у кожному її стовпчику. Багатокутники, які потрібно знайти, повинні мати такі властивості:

- їх вершини повинні лежати у вузлах решітки;

- всі сторони горизонтальні, вертикальні або діагональні (45 градусів);

- багатокутник опуклий.

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

Формат введення-виведення: Програма Numconv зчитує з клавіатури (стандартного пристрою введення) два натуральні числа a та b (2≤a,b≤100) – ширину та висоту сітки. Програма Numconv виводить на екран (стандартний пристрій виведення) єдине число – кількість можливих багатокутників.

Приклад вхідних та вихідних даних

Введення 1            Виведення 1

3 2                              19

Введення 2            Виведення 2

2 2                              5

Вікторина (Quiz) (старша ліга)

Гноми-велетні вирішили взяти участь у чемпіонаті гри «Що? Де? Коли?». Чемпіонат складається з t турів. Кожен тур містить деяку кількість питань. Серія питань – це підпослідовність питань одного туру від l-ого до r-ого включно, причому l ≤ r і підпослідовність неперервна (беруться до уваги всі підряд питання від l-ого до r-ого). Гноми будуть вважати серію питань вдалою, якщо вони дадуть відповіді не менш, ніж на q відсотків питань з цієї серії. Для підняття настрою команди, знайдіть для кожного туру кількість вдалих серій.

Формат введення-виведення:

Програма Quiz зчитує з клавіатури (стандартного пристрою введення) число t – кількість турів у чемпіонаті, 1 ≤ t ≤ 10. У наступних t рядках знаходиться інформація про кожен з турів у такому вигляді: n q a₁...a_n, 0 ≤ q ≤ 100. a_i =  може бути 0, якщо команда не відповіла на i питання, або ж 1 в іншому випадку. Крім того, усього на чемпіонаті було задано не більш, ніж 500000 питань. Усі числа вхідних даних цілі.  Програма Quiz виводить на екран (стандартний пристрій виведення) рівно t чисел в один рядок через пробіл: i-те число дорівнює кількості вдалих серій питань у i-ому турі.

Система оцінки.70% балів припадатиме на тести, в яких q_i = 50.

Приклад вхідних та вихідних даних

Введення                                        Виведення

2

10 50 1 0 1 0 1 1 0 0 0 1                    32 4

5 50 1 0 0 0 1