Завдання для учнів 9-11 класів
Час виконання 4 години
Задача Farm2022. Фермер Нечитайло отримав земельну ділянку у вигляді правильного багатокутника з кількістю сторін (а, отже, і вершин) N. Між деякими вершинами протоптані стежки у вигляді прямих. Скільки є пар стежок, що перетинаються? Якщо стежки виходять з однієї вершини, то вони там не перетинаються. Стежка з А в В і з В в А – це одна й та ж стежка і може розглядатися один раз.
Технічні умови Програма Farm2022 читає з пристрою стандартного введення 2 числа через пропуск – кількість вершин N (4≤N≤200) та кількість діагоналей M (2≤M≤5000) а далі М пар чисел – номери вершин, що з’єднані стежкою. Програма виводить на пристрій стандартного виведення єдине число – кількість пар стежок, що перетинаються.
Приклади
Введення
4 2
1 3
2 4
Виведення 1
Введення
6 3
1 4
2 5
3 6
Виведення 3
Задача Powder. На острові Хортиця знайшли старовинний фінансовий документ - чи то рахунок за порох, чи то вартість роботи коваля, що викував шаблю – невідомо. Але відомо, що сума рахунку складає N монет, але число записане в невідомій дослідникам системі числення. Потрібно знайти основу козацької системи числення, якщо відомо, що вона менша 10.
Технічні умови. Програма Powder читає з пристрою стандартного введення два числа: N в десятковій системі і К – в системі числення з невідомою основою. Програма виводить на пристрій стандартного виведення єдине число – основу невідомої системи. Гарантується, що козаки не помилялися – таке єдине число існує. ( 10≤ N,K≤1018)
Приклад
Введення 15 1111
Виведення 2
Задача Discount. Відвідавши перед Різдвом великий магазин, ви обрали багато подарунків рiдним та друзям. Зекономити певну кількість грошей вам можуть допомогти два типи знижок, що дають у магазина:
1. при купівлі 3-х товарів, Ви платите за них як за 2 найдорожчих з них;
2. при купівлі 5-и товарів, Ви платите за них як за 3 найдорожчих з них.
Таким чином, певнi товари можна об’єднати у трійки або п’ятірки i заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків.
Напишуть програму, що за цінами усіх подарунків, знаходить мінімальну суму грошей, якої вистачить на їх купівлю.
Технічні умови. Програма Discount читає з пристрою стандартного введення ціле число N (1⩽ N⩽123456). Другий рядок містить N натуральних чисел — ціни подарунків. Сума цін усіх подарунків менша за 1018. Об’єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.
Програма виводить на пристрій стандартного виведення єдине число — знайдену мінімальну суму грошей, за яку можна купити усі подарунки.
Приклад
|
Введення |
Виведення |
|
5 50 80 50 100 20 |
230 |
Коментар. Якщо ціни п’яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна з них усіх скласти п’ятірку й отримати за них знижку: два найдешевші товари (20+50=70) дістануться безкоштовно, сплатити треба лише за решту. Загалом вся покупка буде коштувати 80+50+100=230 грошових одиниць, замість 300.
Задача Presents2022. Василько чекає різдвяні подарунки! Від друзів та родичів він чекає чотири подарунки з тим, щоб однаковими були вартості тільки двох подарунків.
Василько гарний математик та програміст. Він вирішив визначити для довільної суми вартості подарунків n кількість їх варіантів. Допоможіть йому.
Технічні умови. Програма Presents2022 читає з пристрою стандартного введення єдине число n
(0≤n≤3·109). Програма виводить на пристрій стандартного виведення єдине число – шукану кількість варіантів.
Приклади
Введення 7
Виведення 1
Введення 19
Виведення 30
Коментар. Єдина комбінація для першого прикладу 1+1+2+3.