Заочный тур

1. Рассмотрим сумму

Найдите по заданному n (1<n<1000) сто десятичных цифр дробной части числа sn.

Оценка за задачу - 25 баллов.

2. В лабиринте находятся кошка и мышка. За один ход мышка или кошка могут переместиться на одну клетку вверх, влево, вправо, вниз или по диагонали. Определить, сможет ли мышка добежать до выхода, не пойманная кошкой (кошка ловит мышку, если достигает ее на своем ходу), или кошка не выпустит мышку из лабиринта.

Лабиринт задан матрицей 8*8, где 0 - проход, 1 - стена, 2 - мышка, 3 - кошка, 9 - выход (выход один). Первый ход делает мышка. Далее ходы делаются по очереди кошкой и мышкой.

Пример данных:

0

0

0

9

0

0

0

0

0

0

0

1

1

1

1

0

0

1

1

1

0

0

1

0

0

0

2

0

0

0

3

0

0

0

1

1

1

1

1

0

0

1

1

0

0

0

1

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

Матрица вводится из текстового файла INPUT.DAT, в котором по строкам (без пробелов) записаны ее строки.

Программа должна выдать ответ:

“да” (мышка может прорваться) или “нет” (не может).

Если мышка может прорваться, то осуществить игру мышки с кошкой - выдавать ходы мышки в виде:

n m - новое положение мышки (n - номер строки, m - номер столбца)

и считывать ответные ходы кошки:

nk mk - (nk - номер строки, mk - номер столбца).

Координаты левого верхнего угла - (1, 1).

Оценка за задачу - 40 баллов.

3. В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском алфавите (А-1, Б-2, ..., Я-33), а символ пробела заменили нулем. Напишите программу, которая вводит получившуюся последовательность цифр (не более 30) и находит количество исходных сообщений, из которых могла получиться заданная последовательность. Например, для последовательности “1025” количество возможных исходных данных равно 4.

Оценка за задачу - 35 баллов.

4. При игре в домино пользуются костяшками с номерами от 0-0 до 6-6. Все 28 костяшек расположили в виде прямоугольника 7*8 (7 строк и 8 столбцов) и числа записали в таблицу таких же размеров.

Пример таблицы:

0

0

1

1

2

3

3

6

0

1

1

2

2

4

4

4

0

2

1

3

2

5

4

5

0

3

1

4

2

6

4

5

0

4

1

5

3

3

5

5

0

5

1

6

3

4

5

6

0

6

2

2

3

5

6

6

По заданной таблице восстановить хотя бы одно исходное расположение костяшек домино. Ответ представить в одном из видов:

- заданием координат и расположения всех костяшек домино,

- с использованием символов псевдографики,

- с использованием графического режима.

Заданная таблица вводится из текстового файла INPUT.DAT, в котором по строкам (без пробелов) записаны строки таблицы.

Оценка за задачу - 50 баллов.

Памятка участнику

Для проведения тестирования Вы должны скопировать на дискету жюри файлы XXXXN.exe и XXXXN.pas (XXXXN.bas), где XXXX - первые четыре буквы Вашей фамилии, N - номер задачи.

Ваша программа перед началом работы должна выводить на экран следующую справочную информацию:

- фамилию, имя, место учебы, класс;

- номер задачи.

Время тестирования каждой задачи ограничено 1 минутой. При превышении этого времени очки за задачу не начисляются.

I отборочный тур

1. Система уравнений. Тpебуется pешить систему уpавнений и неpавенств

X1+X2+...+Xn=S

AXB1

AXB2

...

AXBn

т.е. по заданным n, S, A1, B1,..., An, Bn найти соответствующие значения X1, ..., Xn, либо установить, что pешения не существует. Если pешений несколько, то выдать любое из них. Все пеpеменные и константы в уpавнении - вещественные числа. Ваша пpогpамма должна pаботать линейное вpемя, т.е. выполнять не более C*n шагов, где С - некотоpая константа.

Оценка за задачу - 25 баллов.

2. Лесенки. Задано натуральное число N (NЈ 120). Составьте программу, которая вычисляет количество различных лесенок, состоящих ровно из N одинаковых кубиков. Здесь лесенка - это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка содержит по крайней мере две ступеньки, ступенька состоит по крайней мере из одного кубика. На рисунке приведен пример такой лесенки для N=11, а для N=5 таких лесенок две.

Оценка за задачу - 30 баллов.

3. Римский водопровод. Римляне решили построить водопровод, используя тяжкий, подневольный труд своих рабов. Естественно, никаких насосов у них нет. Поэтому они выбрали источник, расположенный достаточно высоко и наметили точки на местности, до которых должна доходить вода "самотеком".

Заданы:

1) координаты и высота над уровнем моря источника воды;

2) количество точек, до которых требуется довести водопровод;

3) координаты и высоты над уровнем моря всех этих точек

Требуется: сделать проект водопровода для снабжения намеченных точек водой из источника при условии, что вода должна течь самотеком, и длина прокладываемых водоводов должна быть минимальна. Водоводы прокладываются строго по прямой. Понятно, что до каких-то точек вода идет непосредственно от источника, а до каких-то - от других точек, расположенных, разумеется, выше данной, но ниже источника. Между точками, расположенными на одном уровне, вода течь не может. Заканчиваться любая ветка водовода может в любой точке - просто дальше не идет.

Вводимая информация:

В первой строке - количество точек, включая источник;

Во второй строке - через пробел координаты (X,Y) и высота над уровнем моря источника воды;

В третьей и последующих строках - через пробел координаты (X,Y) и высота над уровнем моря каждой точки, требующей водоснабжения.

Примечания: 1) все координаты и высоты задаются целыми положительными числами;

2) максимальное количество точек - 30;

Оценка за задачу - 45 баллов.

II отборочный тур

4. Образец. Образец имеет вид:

образец ::= <PT>

<PT> ::= <A><PT>

<A> ::= [<PT>] | <ST>

<ST> ::= <символы>

Часть образца заключенная в квадратные скобки показывает, что эту часть можно исключать. Таким образом образец описывает множество строк.

Hапример, образец: [a[b]]c описывает строки: c, ac, abc.

Слово подходит под образец, если оно совпадает с одним из слов описываемых образцом.

Написать программу которая по заданным образцу и слову печатает “ДА” если слово подходит под образец, и “НЕТ” если не подходит.

Hапример:

образец: [a[b]]c слово: ab

ответ: НЕТ

Оценка за задачу - 30 баллов.

5. Шахматный конь. В углу шахматной доски стоит конь. Какое наименьшее количество ходов должен сделать конь, чтобы побывать в каждом углу и вернуться обратно.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

1. С клавиатуры вводятся через пробел два числа - размеры доски.

2. На экран выводится число шагов.

3. При отсутствии решений выводится сообщение "Решений нет".

ПРИМЕР:

После ввода размеров 3 и 4 выводится число шагов 10.

Оценка за задачу - 30 баллов.

6. Кольцевая дорога. Мэрия строит кольцевую дорогу вокруг населенного пункта.

Требуется найти центр и радиус наименьшей кольцевой дороги.

Входные данные. Считать дома и другие городские строения точками на плоскости. В файле INPUT.TXT хранятся по строкам координаты каждого строения.

Выходные данные. Найденные центр и радиус вывести на экран.

Оценка за задачу - 40 баллов.

 

III отборочный тур

7. Робот. На координатной плоскости задан робот-манипулятор, состоящий из двух последовательно соединенных звеньев, длины которых L1 и L2. Первое звено шарнирно закреплено в начале координат, второе шарнирно соединено с первым. В конце второго звена установлено сверло. Робот управляется путем поворота звеньев в первом и во втором шарнирах с угловыми скоростями, по абсолютной величине не превышающими w1 и w2 (рад/с) соответственно. Второе звено может вращаться относительно первого беспрепятственно.

Робот предназначен для сверления отверстий. Координаты точек сверления: (x1; y1), (x2; y2), ..., (xN; yN).

В начальный момент первое звено направлено вдоль положительной полуоси OX, а второе звено образует угол А, отсчитываемый от оси OX против часовой стрелки. Время операции сверления отверстия фиксировано и равно Р.

Требуется составить программу, которая:

а) выдает какую-либо последовательность номеров точек сверления и требуемое для этого время;

б) выдает последовательность сверления заданных точек за наименьшее, по возможности, время работы робота и само это время;

в) для заданного интервала времени (О, Т) выбирает максимальное количество просверленных отверстий и выдает их последовательность.

Примечания

1) Все исходные данные целочисленные.

2) Программа должна осуществлять ввод исходных данных из входного файла ROBOT.DAT в виде последовательности: L1, L2, w1, w2, A, T, P, N, x1, y1, ..., xN, yN.

Оценка за задачу - 40 баллов.

8. Лишние скобки. Составить программу, которая из вводимой строки, содержащей корректную запись арифметического выражения с общепринятыми математическими приоритетами, удаляет лишние скобки. Скобки считаются лишними, если их отсутствие не влияет на значение выражения. Выражение содержит только переменные, состоящие из латинских букв, знаки четырех операций (+, -, * и /) и круглые скобки. Его длина не превышает 60 символов. Имя переменной может встречаться в выражении только один раз. Выражение не может содержать операции смены знака (-a, +a и т.п.).

Примеры:

((alfa+beta)+gamma) ® alfa+beta+gamma

a*(b-c) ® a*(b-c)

p*(q/r)*s/(a*b) ® p*q/r*s/(a*b)

Оценка за задачу - 35 баллов.

9. Сумма квадратов. Вычислите сумму квадратов всех положительных целых чисел, запись которых в десятичной системе счисления состоит ровно из K цифр, каждая из которых отлична от нуля.

Оценка за задачу - 25 баллов.

 

IV отборочный тур

10. Уравнение. Задано уравнение вида A+B=C, где A, B, C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса "?". Например, ?65+443=2?4. Требуется подставить вместо знаков вопроса цифры, так чтобы равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений.

Файл исходных данных содержит одну или несколько строк, в каждой из которых записано одно уравнение. Уравнение состоит не более чем из 80 символов. Файл исходных данных не содержит пробелов и пустых строк.

Для каждого уравнения вывести в выходной файл на отдельной строке решение - верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение “решения не существует”.

Пример файла исходных данных INPUT.TXT:

2+2=5

?+?=??

??2?4+9?=355

Выходной файл OUTPUT.TXT для приведенного примера:

решения не существует

9+5=14

00264+91=355

Оценка за задачу - 35 баллов.

11. Биллиард. Дано биллиардное поле длиной a и шириной b с единственной лузой, расположенной в левом нижнем углу, совпадающим с началом координат. Внутри поля в точке с координатами (x, y) находится биллиардный шар. По шару наносится удар и он начинает прямолинейное движение. При соударении со стенками удар абсолютно упругий (угол падения равен углу отражения).

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

Входные данные. Ввод осуществляется с клавиатуры в следующем порядке:

a b

x y

N

Выходные данные. Координаты найденных точек вывести на экран монитора.

Оценка за задачу - 35 баллов.

12. Свертка. Имеется цепочка символов ограниченной длины, состоящая из букв латинского алфавита.

Можно выполнять свертку повторяющихся подстрок этой строки по следующим правилам:

(а) несколько последовательных повторений одной и той же подстроки заменяются так:

ааа ® 3(а),

abcbcd ® а2(bc)d,

(б) правило (а) можно применять многократно к уже свернутой строке, например:

2(а)b2(а)b ® 2(2(а)b)

Требуется выдать по возможности оптимальную свертку для введенной строки.

Оценка за задачу - 30 баллов.