Сайт підготовки до олімпіади з інформатики

Завдання олімпіади з інформатики

Максимальна кількість балів – 100. 5 завдання по 20 балів кожне.

Вхідні дані допускається читати як з клавіатури (консолі), так і з файлу input.txt, вихідні данні необхідно виводить на екран (в консоль), або в файл output.txt.

Задача 1. «Дільники» (20 балів)

Вводяться два числа  N і K. Виведіть кількість чисел з діапазону від 1 до N таких, щоб їх сума цифр ділиться на K.

Задача 2. «Трикутники» (20 балів)

На площині дано N точок. Ніякі дві точки не співпадають. Знайдіть трикутник з вершинами в цих точках, що має найменший можливий периметр.

Введення

Спочатку вводиться число N - кількість точок (3 ≤ N ≤ 50), а потім N пар дійсних чисел, які задають координати точок.

Виведення

Виведіть три числа - номери точок, які повинні бути вершинами трикутника, щоб його периметр був мінімальний. Якщо розв’язків декілька виведіть будь-яке з них.

Задача 3. «Драбинка» (20 балів)

Драбинкою називається набір кубиків в один або декілька шарів, в якому кожен вищий верхній шар містить кубиків менше, ніж нижній.

Підрахувати число драбинок, котре можна побудувати з  N кубиків.
Введення
На вході записано число N (1 ≤ N ≤ 100).

Виведення
Вивести шукане число драбинок.

Задача 4. «Віруси» (20 балів)

На полі розміром N * N розташоване M вірусів. За кожен хід вірус заражає 4 сусідні з ним клітини. Положення вірусів задано координатами на полі. Потрібно написати програму, що визначає, за яке найменшу кількість ходів буде заражене все поле.

Введення

У першому рядку записано два числа N (1 ≤ N ≤ 100) та M (1 ≤ M ≤ 10). Кожний з наступних M рядків містить по два числа - координати вірусу на полі. Всі числа цілі, координати за величиною не перевершують розмірів поля. Ліва нижня клітинка поля має координати (1, 1).

Виведення

В перший і єдиний рядок виведіть одне число - шукану найменшу кількість ходів.

Задача 5. «Гра» (20 балів)

Легендарний вчитель математики Юрій Петрович придумав забавну гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів і одиниць, що починається з одиниці. (Наприклад, десяткове число 19₁₀ = 1*2⁴+0*2³+0*2²+1*2¹+1*2⁰ в двійковій системі запишеться як 10011₂.) Потім учитель починає зсув цифр отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсуваються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору початкового числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, Юрій Петрович відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом пророблених маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри, отже, опиниться число 1*2⁴+1*2³+1*2²+0*2¹+0*2⁰ = 28. Оскільки придумана гра з числами все більше займає уяву вчителя, відволікаючи тим самим його від роботи з дуже обдарованими школярами, Вас просять написати програму, яка б допомогла Юрію Петровичу отримувати результат гри без утомливих ручних обчислень.

Введення

Введення містить одне ціле число N (0 ≤ N ≤ 32767).

Виведення

Ваша програма повинна вивести одне ціле число, рівне результату гри.