Завдання особистої олімпіади з ІТ-2018

Числа Сміта (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

Завдання командної олімпіади IT -2018

Завдання командної олімпіади

Штанга (Barbell) Гноми добре знають, наскільки важливі заняття спортом, а тому часто ходять до тренажерної зали. Утім, займатися прибиранням після виснажливого тренування зовсім не хочеться, тож більшість тренажерів залишаються у стані «хай буде». Адміністратору зали особливого клопоту завдають штанги (виявляться, зняти усі диски самотужки досить складно). Штанга – спортивний снаряд, що складається з грифу (металевого стержня) масою M, розміщеного на двох опорах, віддалених від центру мас грифу на L. Ліворуч від лівої опори щільно розміщено N дисків, кожен шириною 2W маси Ai. Ці N дисків нумеруються, починаючи від опори (тобто справа наліво). Праворуч від правої опори аналогічним чином розміщено K дисків, кожен шириною також2W та маси Bi. Ці K дисків нумеруються, починаючи від опори (тобто зліва направо). Гном-адміністратор вміє швидко знімати диски (звісно, починаючи від крайнього), але досить повільно змінює сторону. Крім того, гному зовсім не хочеться, щоб в якийсь момент часу штанга перехилилася (тобто, щоб її центр мас був не між опорами; якщо центр мас виявляється рівно на якійсь з опор, штанга не перехиляється). У початковий момент часу штанга не перехиляється, тобто центр мас усієї конструкції знаходиться між лівою та правою опорою (можливо, рівно на одній з опор). Адміністратор хоче обрати сторону, з якої починати, підійти до неї, зняти якусь кількість крайніх дисків, після чого змінити сторону, повторити ті самі дії, потім знову змінити сторону і продовжувати, поки можливо знімати хоча б один диск без перекидання всієї конструкції. Вам необхідно заздалегідь сказати гному таку інформацію: яку максимальну кількість дисків можна зняти та яку мінімальну кількість змін сторони необхідно на це витратити. Зверніть увагу, що в першу чергу вам необхідно максимізувати кількість знятих дисків, а в другу мінімізувати кількість змін сторони. З самого початку гном може обрати сторону «безкоштовно», тобто до кількості змін сторони цей вибір не додається. Формат введення-виведення: Програма Barbell читає з клавіатури (стандартного пристрою введення) три рядки. У першому рядку розміщено чотири числа: M, L, W, N, K (1 ≤ M, L, W, N, K ≤ 105) – відповідно, маса грифу, половина відстані між опорами, половина ширини кожного з дисків та кількості дисків на правій та на лівій половині. У другому рядку рівно N цілих невід'ємних чисел, кожне не перевищує 103– маса кожного з дисків, що розташовані праворуч. У третьому рядку рівно K натуральних чисел, кожне не перевищує 103 – маса кожного з дисків, що розташовані ліворуч. Програма Barbell виводить на екран (стандартний пристрій виведення) рівно 2 цілих числа через пробіл: максимальну кількість дисків, що можна зняти, та мінімальну необхідну кількість змін сторони. Приклад вхідних та вихідних даних Введення 1 Виведення 1 3 6 1 2 2 9 3 9 3 4 1 Введення 2 Виведення 2 2 9 1 2 3 10 3 9 3 1 5 2 Зображення до другого тесту - - - - - - - - - - - - - - - - - - - - - - - - - Опуклі оболонки (ConvexHulls) Опукла оболонка множини точок - опуклий багатокутник з найменшою площею, що містить усю множину точок. Вам дано n точок на площині. Довільним чином можна вибрати і видалити одну із заданих точок, після чого побудувати опуклу оболонку решти. Очевидно, що видаляючи різні точки, ви будете отримувати різні опуклі оболонки. Припустимо, Ви по черзі видаляєте точки заданої множини і будуєте опуклі оболонки (видаляючи чергову точку, попередньо видалену Ви повертаєте назад). Зробивши вказану дію для кожної точки, Ви отримаєте n опуклих оболонок (деякі з яких можуть співпадати). Запишемо набір чисел, що дорівнюють кількості вершин в кожній з отриманих опуклих оболонок. Знайдіть середнє арифметичне даного набору чисел. Вважати, що якщо опукла оболонка є відрізком, то в ній дві вершини. Якщо ж вона є невиродженим багатокутником, то всі кути при вершинах строго менше π. Формат введення-виведення: Спочатку програма ConvexHulls читає з клавіатури (стандартного пристрою введення) число n (3 ⩽ n ⩽ 2 · 105) - кількість точок множини. Далі у наступному рядку читаються пари цілих чисел, що не перевищують по модулю 109 - координати точок. Гарантується, що жодні дві точки не співпадають. Програма ConvexHulls виводить на екран (стандартний пристрій виведення) два числа через пробіл p q, де p, q – цілі невід'ємні числа. Приклад вхідних та вихідних даних Введення Виведення 5 0 0 0 4 4 0 3 3 4 4 17 5 - - - - - - - - - - - - - - - - - - - - - - - - - Іспити (Exams) Одного чудового ранку студент прокинувся і зрозумів: скоро сесія! Студент знає, скільки часу (від даного моменту) залишилося до початку кожного іспиту, та скільки часу потрібно на підготовку до кожного іспиту. Студент складає іспити моментально. Крім того, студент вміє готуватися до іспитів як безперервно, так і з розривами на підготовку до інших іспитів та/або на складання інших іспитів (все це не впливає на сумарну тривалість підготовки). Яку максимальну кількість іспитів може скласти студент? Формат введення-виведення: Спочатку програма Exams читає з клавіатури (стандартного пристрою введення) ціле число n (0<=n<=10000) і далі n пар цілих чисел Ti, Di (0<=Ti<1000000, 0<Di<1000000, всі Ti попарно різні) – момент початку та тривалість підготовки для i-го іспиту. Всі числа розділені пробілами. Програма Exams виводить на екран (стандартний пристрій виведення) єдине ціле число: максимальну кількість іспитів, які студент може. Приклад вхідних та вихідних даних Введення 1 Виведення 1 3 3 2 5 4 10 5 2 Введення 2 Виведення 2 3 3 2 5 3 10 5 3 - - - - - - - - - - - - - - - - - - - - - - - - - Нелюбимі цифри (Numbering) Новий керівник організації виявив, що його попередник, по одному йому відомим причинам, для нумерації офіційних документів принципово не використовував числа, десяткові записи яких містили деякі цифри. Причому в різні роки обструкції підлягали різні комплекти цифр. У якості початкового номеру в кожному році попередній керівник брав мінімальне невід’ємне число, що не містило знехтуваних у даному році цифр. При нумерації кожного наступного документу, у тих випадках, коли наступний номер містив знехтувану цифру, це число просто пропускалося. І так, доки чергове число не виявлялося вільним від небажаних для нього цифр. Наприклад, якщо нехтувалися цифри 8, 7, 9, 5, 1, то перші кілька документів цього року мали наступні номери: 0, 2, 3, 4, 6, 20, 22, 23, 24, 26, 30, 32, 33, ... Оскільки попередник керував організацією досить довго і накопичилась велика кількість перенумерованих ним документів, у нового керівника виникла потреба у програмі, яка для заданого комплекту знехтуваних цифр за вихідним номером документа (тобто за номером, який був йому наданий) швидко визначить порядковий номер цього документа, відрахований від нуля. Формат введення-виведення: Програма Numbering зчитує з клавіатури (стандартного пристрою введення) два непустих рядки. У першому рядку через пробіл перераховано нелюбимі цифри (їх загальна кількість від однієї до восьми включно). У другому рядку дано вихідний номер шуканого документу (не менше нуля та не більше 1,000,000,000). Програма Numbering виводить на екран (стандартний пристрій виведення) єдине число – номер шуканого документу, тобто порядковий номер документу, вихідний номер якого вказано у вхідному файлі. Приклад вхідних та вихідних даних Введення Виведення 8 7 9 5 1 24 8 - - - - - - - - - - - - - - - - - - - - - - - - - Гномоградуси (Gnomedegrees) Гноми чудово розуміють, що «Математика – цариця наук!» і тому приділяють цьому предмету особливу увагу. Найулюбленішими у них є геометричні задачі з колами. Однак, зверніть увагу, що одиницею вимірювання кута у гномів є не градуси чи радіани, а деяка величина – гномоградус. Причому, в залежності від настрою, ця величина може змінюватися! Визначається ця величина таким чином: задається число L – кількість рівних частин, на які ділиться коло. И ось гномам задали таку задачу. На колі є N перегородок з відомими кутами, заданими у гномоградусах, причому число L, що визначає гномоградус, обов’язково кратно кількості перегородок N. Необхідно визначити мінімальну кількість переміщень перегородок, в результате якого коло буде розділено на рівні частини. Перегородки можна рухати тільки в межах від попередньої до наступної, тобто заборонено міняти їх місцями відносно заданого розташування. Крім того, перегородки дозволяється рухати тільки по умовним поділкам, тобто нові кути повинні бути виражені цілою кількістю гномоградусів. Формат введення-виведення: Програма Gnomedegrees читає з клавіатури (стандартного пристрою введення) два непустих рядка. У першому рядку два цілих числа L та N (L≤109, N≤103, L кратно N), а у другому N цілих чисел через пробіл ai (0≤ ai≤L-1) – кути, на яких знаходяться перегородки у гномоградусах. Початок відліку кожного з кутів від вертикалі (див. рисунок). Програма Gnomedegrees виводить на екран (стандартний пристрій виведення) єдине ціле число: мінімальну кількість переміщень. Приклад вхідних та вихідних даних Введення Виведення 27 9 13 2 11 9 10 20 1 21 22