Задачи районной олимпиада Удмуртии по программированию

Задачи районной олимпиада Удмуртии по программированию

Задания для учащихся школ (классов) повышенного уровня образования.

Л1. Работа с памятью.

Заданы 3 натуральных числа, двоичное разложение которых задает относительное положение страниц памяти. 1 показывает наличие страницы, 0 -- отсутствие. Какой максимальный непрерывный участок памяти останется после самого оптимального размещения?

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Размер страницы 64Кб. Размер памяти 4Мб. Написать программу, которая будет запрашивать три числа и выводить размер максимально возможного непрерывного участка памяти.

ПРИМЕР
Вход: 10 6 9
Выход: 3648Кб

30 баллов

Л2. Вычёркивание символов.

Заданы две строки. Из строк, из первой и второй, можно убирать любые символы. Какова максимальная длина общей строки после сокращения?

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Длина строк не более 20 символов. Написать программу определяющую максимальную длину общей строки.

ПРИМЕР
Вход:
абвгд
авбгд
Выход: 4

30 баллов

Л3. Высота формулы.

Пусть задана математическая формула с использованием только операций +, -, *, /. Высотой формулы считается количество строк, которое займет формула при обычной математической записи (дробь занимает 2 строки). На пример, формула \frac{1+\frac{1}{a}}{\frac{1}{3}-b}, имеет высоту 4.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Написать программу подсчитывающую высоту формул. Операция '/' занимает 2 строки, одну - под числитель, одну - под знаменатель. Остальные операции записываются в одной строке. Входная строка, кроме арифметических операций, может содержать парные круглые скобки, изменяющие приоритет операций (как обычно). Операндами служат целые числа (длина их не важна) и переменные. Переменные обозначаются одной маленькой латинской буквой.

ПРИМЕР
Вход: (1+1/a)/(1/3-b)
Выход: 4

40 баллов

Сумма баллов за все задачи: 100.


Задания для учащихся общеобразовательных учреждений.

О1. Крестики-нолики.

Правила игры классические.

Игра в крестики-нолики ведется на квадратном поле 3x3. Играют двое. Начинают "крестики". Каждый из игроков, по очерёдно, ставит свой значок, крестик или нолик, на свободную клетку. Выигрывает тот, кто первым поставит три своих значка вряд по вертикали, горизонтали или диагонали.

Задаётся последовательность ходов. Определить кто выиграл, "крестики" или "нолики"?

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Последовательность ходов задаётся 9-значным числом. Цифра числа обозначает номер клетки хода, а порядковый номер цифры - номер хода.

Клетки пронумерованы так как показано на рисунке.

7 8 9
4 5 6
1 2 3
В примере приведена позиция показанная слева. Очевидно, что последние два хода лишние, но они нужны для девятизначности кода позиции.
X 0 X
0 X 0
X 0 X

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

Правильность кода позиции проверять не надо.

ПРИМЕР
Вход: 123456789
Выход: X

30 баллов

О2. Уравнение x | a = b.

Операция | действует с целыми положительными числами побитово. a|b означает, что надо представить числа a и b в двоичном виде и для каждой пары бит, с одинаковыми номерами, выполняет действие по следующим правилам:
0|0=0, 1|0=1, 0|1=1, 1|1=0.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Написать программу решающую уравнение x|a=b.

Программа должна запрашивать a и b, а потом печатать x.

ПРИМЕР
Вход:
a=10
b=3
Выход: x=9

30 баллов

О3. Высота формулы.

Пусть задана математическая формула с использованием только операций +, -, *, /. Высотой формулы считается количество строк, которое займет формула при обычной математической записи (дробь занимает 2 строки). На пример, формула \displaystyle\frac{1+\frac{1}{a}}{\frac{1}{3}-b}, имеет высоту 4.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

Написать программу подсчитывающую высоту формул.

Операция '/' занимает 2 строки, одну - под числитель, одну - под знаменатель. Остальные операции записываются в одной строке. Входная строка, кроме арифметических операций, может содержать парные круглые скобки, изменяющие приоритет операций (как обычно). Операндами служат целые числа (длина их не важна) и переменные. Переменные обозначаются одной маленькой латинской буквой.

ПРИМЕР
Вход: (1+1/a)/(1/3-b)
Вход: 4

40 баллов

Сумма баллов за все задачи: 100.


E-mail: pvv@ uni. udm. ru