Завдання для учнів 8 класів (та молодших)
Час виконання – 4 години
Задача Farm2022. Фермер Нечитайло отримав земельну ділянку у вигляді правильного багатокутника з кількістю сторін (а, отже, і вершин) N. Між деякими вершинами протоптані стежки у вигляді прямих. Скільки є пар стежок, що перетинаються? Якщо стежки виходять з однієї вершини, то вони там не перетинаються. Стежка з А в В і з В в А – це одна й та ж стежка і може розглядатися один раз.
Технічні умови Програма читає з пристрою стандартного введення 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
Задача Brackets2022. Правильна послідовність дужок утворюється за такими правилами:
- () – правильна;
- якщо а – правильна послідовність, і b – правильна, то ab правильна;
- Якщо а – правильна, то (а) – теж правильна.
Дано послідовність дужок. Яку мінімальну кількість дужок (відкритих чи закритих) треба вставити в дану послідовність, аби отримати правильну послідовність?
Технічні умови. Програма Brackets2022 читає з пристрою стандартного введення стрічку, яка складається виключно з круглих дужок довжиною не більше 104 символів. Програма виводить на стандартний пристрій виведення одну величину – шукану кількість дужок.
Приклади
Введення ))((
Виведення 4
Введення (())
Виведення 0
Задача Presents2022. Василько чекає різдвяні подарунки! Від друзів та родичів він чекає по чотири подарунки з тим, щоб однаковими були вартості тільки двох подарунків. Василько гарний математик та програміст. Він вирішив визначити для довільної суми вартості подарунків n кількість їх варіантів. Допоможіть йому.
Технічні умови. Програма Presents2022 читає з пристрою стандартного введення єдине число n (0≤n≤3·109). Програма виводить на пристрій стандартного виведення єдине число – шукану кількість варіантів.
Приклади
Введення 7
Виведення 1
Введення 19
Виведення 30
Коментар. Єдина комбінація для першого прикладу 1+1+2+3.