Районный тур олимпиады школьников по информатике
(1999-2000 учебный год)

I. "Разбиение на части" (автор задачи — Брызгалов Е.В.) — 10 баллов

Натуральное число N < 30000 представить в виде суммы M целых примерно равных частей (M < 20). Назовём примерно равными части, любые две из которых отличаются не более, чем на 1.

Технические требования

Формат входных данных:
первая строка — N;
вторая строка — M.

Пример входных данных:
13
4

Пример выходных данных:
3 3 3 4

II. "Школьная алгебра" (автор формулировки Брызгалов Е.В., оппонент Южаков М.А.) — 20 баллов

Трёхчлен a + bx + сy от двух переменных x и y (a, b, c — целые числа, модуль которых меньше 30000) однозначно определяется свободным членом а и коэффициентами b и c. Написать программу, которая по заданным a, b и c выводит соответствующий трёхчлен, записанный с использованием алгебраических соглашений:

• коэффициент при члене, содержащем переменную, опускается, если его модуль равен единице;


• член, коэффициент при котором равен нулю, опускается;


• знак "+" опускается, если он предшествует отрицательному коэффициенту;


• знак "+" опускается, если он стоит в начале выражения (так называемый унарный плюс);


• знак умножения между коэффициентом и переменной опускается.

При этом запрещено менять местами члены.

Технические требования

Формат входных данных:
первая строка — a;
вторая строка — b;
третья строка — c.

Формат выходных данных:
строка, содержащая трёхчлен, записанный с учетом указанных правил.

Пример входных данных:
0
2
–1

Пример выходных данных:
2х – y

III. "Периодические трамваи" (автор задачи Деменев А.Г., оппонент Брызгалов Е.В.) — 30 баллов

На остановке сидел инспектор и записывал номера проходящих трамваев (натуральные числа, не превосходящие 1000). Известно, что график движения составлен так, что эти номера должны образовать правильную периодическую последовательность; количество записанных номеров не менее чем в два раза больше длины минимального периода этой последовательности.

Написать программу, которая по записям инспектора определит и выведет длину минимального периода этой последовательности, если график не нарушен, иначе выведет число 0.

Технические требования

Формат входных данных:
строка длиной не более 80 символов, состоящая из последовательных записей номеров трамваев, начинающихся со знака #.

Формат выходных данных:
строка, состоящая из записи одного целого числа.

Пример 1 входных данных:
#10#11#12#10#11#12#10

Пример 1 выходных данных:
3

Пример 2 входных данных:
#10#11#12#11#12#10

Пример 2 выходных данных:
0

IV. "Лифты и эскалаторы" (автор задачи Брызгалов Е.В., оппонент Еремин Е.А.) — 35 баллов

В 101-этажном Торговом Центре (этажи нумеруются от 0 до 100) покупатели могут использовать два типа лифтов. Один — стандартный, который может доставить на любой этаж и проходящий один этаж за E₁ секунд, другой — экспресс, который останавливается только на этажах, номера которых кратны 10 и проходящий один пролет (то есть 10 этажей) за E₂ секунд. Время ожидания лифта (как при посадке, так и при пересадке) составляет соответственно W₁ и W₂ секунд. Кроме того, в любой момент можно воспользоваться эскалаторами, которые переносят человека на один этаж за S секунд и не требуют времени на ожидание.

Определить минимальное время T, за которое покупатель может попасть с этажа Х на этаж Y.

Замечания: для хранения данных достаточен тип integer.

Технические требования

Формат входных данных:
первая строка — E₁;
вторая строка — W₁;
третья строка — E₂;
четвертая строка — W₂;
пятая строка — S;
шестая строка — Х;
седьмая строка — Y.

Формат выходных данных:
первая строка — T (в сек)

Пример входных данных:
2
25
4
15
10
85
43

Пример выходных данных:
96

Алгоритм действия для разобранного выше примера:
Подождать стандартный лифт — 25 секунд
Вниз до 80 этажа — 10 секунд
Подождать экспресс — 15 секунд
Вниз до 40-го этажа — 16 секунд
Вверх по лестнице на 43 этаж — 30 секунд
Итого — 96 секунд

Замечание: при решении задачи алгоритм действия выводить не следует, но участник должен его предоставить в случае возможной апелляции или несогласия с авторским ответом к тестовому заданию.

V. "Квадроинвариант" (автор задачи Брызгалов Е.В., оппонент Шестаков А.П.) — 45 баллов

При возведении некоторых натуральных чисел в квадрат полученный результат может оканчиваться исходным числом. Например, 76² = 5776. Определить все N-значные числа, обладающие указанным свойством (N < 21).

Технические требования

Формат входных данных: N

Формат выходных данных: все числа, обладающие заданным свойством, каждое из которых выводится с новой строки. Порядок вывода значения не имеет.

Пример входных данных:
2

Пример выходных данных:
76
25

VI. "Многоугольник" (автор задачи Брызгалов Е.В., оппонент Деменев А.Г.) — 60 баллов

Дано N точек (N > 2) с целочисленными координатами, некоторые из которых являются вершинами выпуклого многоугольника, а остальные находятся внутри него. Любые три точки не лежат на одной прямой. Определить число и номера вершин многоугольника.

Ограничения: число точек не более 20. Модули координат не превосходят 30000.

Формат входных данных: N + 1 строка. Первая строка содержит число точек, остальные строки содержат по два числа, разделенных одним пробелом — координаты точек:
N
X1 Y1
…
XN YN

Формат выходных данных:
первая строка — число вершин;
вторая строка — номера точек, являющихся вершинами; номера друг от друга отделяются одним пробелом.

Пример входных данных:
7
0 7
0 3
1 3
2 2
3 0
3 5
5 0

Пример выходных данных:
5
1 2 5 6 7

---

---