Завдання першого етапу
Всеукраїнської учнівської олімпіади
з інформатики
(програмування)
1. ZERO (25 балів). Написати програму Zero.*, що визначає число k − кількість натуральных чисел, не більших даного N, які мають у своєму двійковому разкладі рівно три значущих нулі.
Вхідні дані: У файлі zero.dat записане натуральне число N (N<10000000).
Результати: У файл zero.res записати число k − кількість натуральних чисел, які у двійковому представленні мають рівно три нулі.
2. POINTS (25 балів). На аркуші в клітинку побудували трикутник, вершини якого розміщено у вузлах решітки (перетини ліній клітинок аркушу). Всі вузли решіток, що лежать всередині трикутника, після цього зафарбували, за виключенням вершин трикутника та вузлів, що лежать на сторонах трикутника. Написати програму Points.*, яка допоможе підрахувати кількість зафарбованих точок.
Вхідні дані: У першому рядку вхідного файлу points.dat міститься натуральне число N – кількість тестів (1≤N≤10), в наступних N рядках через пропуск задано 6 чисел: координати x1, y1, x2, y2, x3, y3 вершин чергового трикутника (−15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000).
Результати: Для кожного тестового випадку вихідний файл points.res повинен містити в окремому рядку шукану кількість зафарбованих точок.
3. SELECT (30 балів). N шукачів скарбів знайшли горщик із золотими монетами. Один з них взяв собі одну монету і ще 1/N частину від тих монет, що залишилися. Так само зробили всі інші компаньйони. Монети, що залишилися, було поділено порівну. Написати програму Select.*, яка визначає найменшу кількість монет M, що задовольняє описаному алгоритму поділу.
Вхідні дані: У файлі sel.dat записане (N<10).
Результати: У файл sel.res записати число s − кількість монет знайденого скарбу.
4. BACTS (40 балів). На планеті Земля з’явилися нові вірусні бактерії. Поодинці вони дуже слабі і не здатні заразити здорові бактерії. Але, об’єднавшись у групи, вони дуже небезпечні. Заражені вірусом бактерії живуть за такими правилами:
• за одну секунду вони об’єднуються в групи по три і п’ять бактерій;
• за одну секунду група з трьох заражених бактерій заражає п’ять здорових бактерій, а група з п’яти заражених бактерій заражає дев’ять здорових бактерій;
• заражені бактерії об’єднуються так, щоб заразити за одну секунду найбільшу кількість здорових бактерій;
• кожна заражена бактерія живе три роки, після того як її заразили, а потім вмирає.
Відома початкова кількість бактерій K. Щойно всі вони заразилися. Напишіть програму Baсts.*, яка визначить скільки заражених бактерій буде через N секунд?
Вхідні дані: Єдиний рядок текстового файлу baсts.dat містить через один пропуск два цілих числа K і N (0≤K, N≤18).
Результати: У єдиний рядок текстового файлу baсts.sol записати одне число – кількість заражених бактерій через N секунд.