[The Godfather]

2005-2006 уч. год, Районная-городская олимпиада, г. Н.Новгород

Прочитать:

Задача 1. «Мишень» (10 баллов).

Мишень представляет собой 10 концентрических кругов. Радиус меньшего - 5, радиус каждого следующего на 5 больше предыдущего. Попадание пули задается в системе координат (см. рисунок) вещественными числами х и у, каждое из которых по модулю не превосходит 100. Количество выбитых очков зависит от того, в какую зону попала пуля и можег принимать значения 10, 9, ..., 2, 1,0.
Ваша программа должна
- запросить координаты попадания;
- найти и сообщить количество выбитых очков.



Пример: Исходные данные 8, 13, ответ = 7

Примечание. В случае попадания н границу круга может быть выведено любое из значений, соответствующих задетым кругам. Например, если исходные данные 3 и 4, то допустимы ответ и 10 и 9.


Задача 2. «Числа» (20 баллов).

Дано натуральное n-значное число (n <= 79), запись которого не содержит цифры 0. Из него отбрасывается несколько подряд идущих цифр с начала и несколько цифр (также подряд идущих) с конца (может быть ни одной). Программа должна сообщить количество разных чисел, которое может при этом может получиться.

Пример: n = 1323, ответ = 9

Примечание. Имеются ввиду числа 1323, 323, 132, 23, 32, 13, 3, 2, 1


Задача 3. «Многотомник» (30 баллов).

Многотомное собрание сочинений (не более 6 томов) поставлено в произвольном порядке на полке. Необходимо упорядочить тома. Для этого разрешается брать вторую с начала книгу и перекладывать её либо на первое, либо на последнее место. Составить программу, которая сообщает наименьшее число перестановок необходимого для этою. Программа должна также вынести последовательно получающиеся состояния многотомника.

Пример:
Число томов 4
Начальная последовательность 4, 2, 3, 1
Число шагов 4
0 шаг: 4, 2, 3, 1
1 шаг: 4, 3, 1, 2
2 шаг. 4, 1, 2, 3
3 шаг: 1, 4, 2, 3
4 шаг: 1, 2, 3, 4


Задача 4. «Многоугольник» (40 баллов).

Часть поверхности прямоугольного стола покрыта одинаковыми листами бумаги. Стороны листов параллельны краю стола и одинаково ориентированы (см. рисунок).



Известно, что
- всего листов n (n < 6);
- размер каждого листа 30 см на 20 см
- целочисленные координаты (0 <= x <= 160, 30 <= y <= 90) левых верхних углов каждого листа в системе координат, связанной с левым нижним углом поверхности стола;
- ни один из листов не выходит за край стола;
- всеми листами покрыт многоугольник.
Написать программу, которая сообщает координаты вершин покрытого многоугольника в порядке обхода.
Исходные данные либо вводятся с клавиатуры, либо читаются из файла input.dat, которым к первой строке содержит натуральное число (n)- количество разложенных листов. Последующие n строк - пары координат (х, у) левого верхнего угла листа.

Пример:
Число листов 2
1 лист 30, 60
2 лист 40, 50
Ответ (30, 60) (50,60) (50, 50) (60,50) (60,20) (40,20) (40, 30) (30, 30)

2006-2007 уч. год, Районная-городская олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Числа». 10 баллов

Даны наименьшее общее кратное k и наибольший общий делитель n двух натуральных чисел a и b (n,k<=3200). Найти сами числа.
Запросить значения k и n
найти и сообщить числа a и b для которых введенные являются НОД и НОК соответственно (из всех возможных ответов вывести тот, для которого модуль разности a и b наименьший).

Пример: k = 240, n = 8, ответ = 48, 40


Задача 2. «Замок». 20 баллов

В подземелье графа Дракулы n^2 (n<10000) пещер, соединенных туннелями. Два вампира, Гриша и Миша, по очереди засыпают туннели землей (Гриша первый). За один ход можно засыпать от одного до шести туннелей, но так, чтобы из любой пещеры можно было добраться из- любой другой по оставшимся туннелям. Проигрывает тот кто не может сделать ход.

Запросить значение n.
Найти и сообщить, кто выигрывает при правильной игре, причем если выигрывает Гриша, то его первый выигрышный ход.

Пример: n = 4, ответ "Гриша", первый ход 2.


Задача 3. «Строка». 35 баллов.

Дана строка, состоящая из символов 0 и 1. Перестановкой называется обмен местами двух рядом стоящих символов строки. Необходимо собрать в любом месте строки k символов подряд, причем применив для этого как можно меньшее число перестановок.

Запросить строку (не более 120 символов).
Запросить значение k (k<100).
Найти и сообщить наименьшее возможное число перестановок для сбора k символов 1 в любом месте строки.

Пример: строка = 100110101, k = 3, ответ = 100110101, 100111001


Задача 4. "Разложение". 35 баллов.

Натуральное число n (n<100) можно представить различными способами в виде суммы натуральных чисел:
n=b1+b2+...+bk ; b1>=b2>=...>=bk

Запросить значение n.
Найти и сообщить количество разных способов разложения n на сумму натуральных чисел.

Пример: n = 3, ответ = 3 (3=3, 3=2+1, 3=1+1+1)