Готуємось до олімпіади 3 Печать
Добавил(а) Гісь Ігор Володимирович   
30.10.12 21:14

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

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

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

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

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

input.txt

input.txt

100 3

22 4

output.txt

output.txt

33

5

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

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

Введення

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

Виведення

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

input.txt

output.txt

5
0 0
1.3 0
-2 0.1
1 0
10 10

1 2 4

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

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

Описание: http://127.0.0.1/ru/figureimageru?pid=108Підрахувати число драбинок, котре можна побудувати з  N кубиків.
Введення
На вході записано число N (1 ≤ N ≤ 100).

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

input.txt

3

output.txt

2

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

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

Введення

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

Виведення

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

input.txt

input.txt

2 1
2 1

58 4
46 22
20 26
38 30
23 37

output.txt

output.txt

2

48

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

Легендарний вчитель математики Юрій Петрович придумав забавну гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів і одиниць, що починається з одиниці. (Наприклад, десяткове число 1910 = 1*24+0*23+0*22+1*21+1*20 в двійковій системі запишеться як 100112.) Потім учитель починає зсув цифр отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсуваються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору початкового числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, Юрій Петрович відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом пророблених маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

...

і результатом гри, отже, опиниться число 1*24+1*23+1*22+0*21+0*20 = 28. Оскільки придумана гра з числами все більше займає уяву вчителя, відволікаючи тим самим його від роботи з дуже обдарованими школярами, Вас просять написати програму, яка б допомогла Юрію Петровичу отримувати результат гри без утомливих ручних обчислень.

Введення

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

Виведення

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

input.txt

output.txt

19

28