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

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

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

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

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

30 баллов

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

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

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

30 баллов

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

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

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

40 баллов

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

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

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

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

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

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

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

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

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

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

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.

30 баллов

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

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

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

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

40 баллов

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