Областная олимпиада по информатике
2004 года
Задачи I тура
Задача 1. Калькулятор (30 баллов)
Дано выражение вида:
<число><операция><число>=
где <операция> – одна из операций +, –, *, / (деление понимается как целая часть от деления), <число> – любое натуральное число.
Требуется вычислить и вывести значение данного выражения при следующих ограничениях:
Подзадача 1. В выражении оба числа от 1 до 9.
Подзадача 2. В выражении оба числа не превышают 150.
Подзадача 3. В выражении оба числа не превышают 10100 и допускаются только операции + и -.
Подзадача 4. В выражении оба числа не превышают 10100 и допускается только операция *.
Подзадача 5. В выражении оба числа не превышают 10100 и допускается только операция /.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на один тест
Формат входных данных:
Входной файл INPUT.TXT содержит одну строку вида <число><операция><число>=.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно целое число – значение выражения, записанное без ведущих нулей.
Примеры файлов входных и выходных данных:
|
Подзадача |
INPUT.TXT |
OUTPUT.TXT |
|
Подзадача 1 |
3+4= |
7 |
|
Подзадача 1 |
9*9= |
81 |
|
Подзадача 1 |
8/2= |
4 |
|
Подзадача 2 |
17/3= |
5 |
|
Подзадача 2 |
25-124= |
-99 |
|
Подзадача 2 |
150*150= |
22500 |
|
Подзадача 3 |
1234567891234567890-1= |
1234567891234567889 |
|
Подзадача 4 |
100000000*100000000= |
10000000000000000 |
|
Подзадача 5 |
1/123456789= |
0 |
Задача 2. Функции (30 баллов)
В языке программирования ОГОЛ вызывать функции можно только лишь из функций, которые описываются после той функции, которая вызывается. В частности, функция не может вызывать себя.
Программист Петя спроектировал программу, которая должна быть написана на этом языке. В частности, в проекте указано, какие функции вызываются из каждой функции. Для удобства Петя пронумеровал все функции числами от 1 до N.
Требуется написать программу, которая определяет, в каком порядке функции должны быть описаны в программе не языке ОГОЛ.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест
Формат входных данных:
В первой строке входного файла INPUT.TXT содержится число N (1 £ N £ 100) – количество функций, которые должны быть в программе. Далее идут N строк, причем i-я строка содержит описание функций, которые должны вызываться из i-ой функции. Это описание содержит сначала число Аi (0 £ Аi £ N) – количество функций, которые вызываются из данной функции, а затем номера вызываемых функций (одна и та же функция может вызываться из одной функции несколько раз).
Формат выходных данных:
В выходной файл OUTPUT.TXT необходимо вывести номера функций в том порядке, в каком они должны быть описаны в программе. Если написать такую программу на языке ОГОЛ невозможно, в файл нужно поместить число 0.
Примеры файлов входных и выходных данных:
INPUT.TXT |
OUTPUT.TXT |
|
3 0 4 1 1 3 1 1 1 |
1 3 2 |
|
3 0 2 3 1 0 |
3 1 2 |
|
1 1 1 |
0 |
|
2 1 2 1 1 |
0 |
Задача 3. Палиндромы (20 баллов)
Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Путем вычеркивания из этого слова некоторого набора символов можно получить строку, которая будет называться палиндромом.
Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно, пустого) набора символов, чтобы образованная таким образом строка называлась палиндромом. Способы, отличающиеся порядком вычеркивания символов, считается одинаковыми.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на каждый тест
Формат входных данных:
В первой и единственной строке записано слово S (1 £ S £ 20).
Формат выходных данных:
В первой и единственной строке должно содержаться найденное число способов.
Пример файлов входных и выходных данных:
INPUT.TXT |
OUTPUT.TXT |
|
BAOBAB |
22 |
Задача 4. Игра (30 баллов)
Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.
Требуется написать программу, позволяющую вычислить, какое максимальное число монет может получить первый участник после окончания игры, если второй тоже старается ходить так, чтобы получить как можно больше монет.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на каждый тест
Формат входных данных:
Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 £ N £ 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке – не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 £ K £ 80). Все числа в строке разделены пробелом.
Формат выходных данных:
В выходной файл OUTPUT.TXT необходимо вывести одно число – максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
Пример файлов входных и выходных данных:
INPUT.TXT |
OUTPUT.TXT |
|
3 4 9 1 3 |
14 |
|
4 1 2 2 7 3 |
10 |
|
5 3 4 8 1 7 2 |
18 |
Задачи II тура
Задача 1. «Прибавлятель» (35 баллов)
Некоторое устройство, называемое «Прибавлятель», осуществляет сложение двух натуральных чисел А и В, одно из которых (число А) хранится на ленте, а другое (число В) – в специальном буфере. В процессе сложения Прибавлятель анализирует содержимое ленты и буфера и вместо числа А формирует на ленте сумму чисел А и В. В каждый момент времени Прибавлятель работает только с одной из цифр числа на ленте (говорят, что он находится над этой цифрой), выполняя одну из двух команд: «move» – передвинуться на одну цифру (позицию на ленте) влево, и «+» – изменить цифру, над которой он находится в данный момент. При этом 1 меняется на 2, 2 – на 3, 3 – на 4, 4 – на 5, 5 – на 6, 6 – на 7, 7 – на 8, 8 – на 9, 9 – на 0, 0 – на 1. Если Прибавлятель выполняет команду «move», находясь над самой левой цифрой числа на ленте, то к этому числу слева приписывается цифра 0, и Прибавлятель оказывается над ней. В исходном состоянии на ленте Прибавлятеля записано число А, а сам Прибавлятель находится над некоторой заданной его цифрой. Цифры числа на ленте нумеруются справа, начиная с 1.
Требуется написать программу, формирующую такую последовательность команд «Прибавлятеля», после выполнения которой на ленте окажется число А+В.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на каждый тест
Формат входных данных:
В первой строке входного файла содержится число, напечатанное на ленте (не более 250 знаков). Вторая строка содержит число (не более 250 знаков), которое нужно прибавить к нему (знак «– » обозначает, что это число отрицательное), третья строка – позиция Прибавлятеля над числом, считая справа. Отрицательную и нулевую позицию Прибавлятель иметь не может.
Формат выходных данных:
В выходной файл записывается последовательность команд Прибавлятеля. Каждая команда должна располагаться на отдельной строке. Если последовательность команд написать невозможно, файл должен содержать сообщение «No Solution».
Примеры файлов входных и выходных данных:
|
INPUT.TXT |
OUTPUT.TXT |
|
123456712 12 1 |
+ + move + |
|
123 123 2 |
No Solution |
|
99 -99 1 |
+ move + |
Задача 2. «Кладотолкатель» (65 баллов)
Некий лабиринт представляет собой матрицу M ´ N, некоторые ячейки которой пустые, а остальные заполнены камнями. В одной из пустых ячеек находится клад, а в другой – кладоискатель. Кладоискатель и клад не могут находиться в ячейках, заполненных камнями, за пределами лабиринта, а также одновременно в одной и той же ячейке. Кладоискатель может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также передвигать клад следующим образом: нужно встать в соседнюю к кладу ячейку и толкнуть его. При этом клад передвинется на соседнюю ячейку в направлении, заданном толчком, а кладоискатель переместится в ячейку, где только что находился клад.
Требуется написать программу, которая определяет последовательность толчков и передвижений кладоискателя, с помощью которой клад можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжелый, количество толчков должно быть минимальным.
При наличии нескольких решений программа должна выводить то из них, которое требует наименьшего количества перемещений.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 10 секунд на каждый тест
Формат входных данных:
Первая строка входного файла содержит числа M и N (1 £ N, M £ 30). Последующие M строк содержат описание лабиринта. Каждая строка состоит из N символов, описывающих ячейки лабиринта: заполненная камнями ячейка обозначается латинской буквой ‘X’, пустая ячейка обозначается символом ‘.’ (ASCII-код 46), начальная позиция кладоискателя – буквой ‘Y’, начальная позиция клада – латинской буквой ‘B’, выход – латинской буквой ‘T’.
Формат выходных данных:
Если решения не существует, то файл должен содержать слово ‘NO’. Иначе в первой строке выходного файла должно содержаться слово ‘YES’, во второй строке – последовательность символов, определяющая действия кладоискателя, в частности, символы ‘w’, ‘e’, ‘n’, ‘s’ обозначают передвижения кладоискателя на запад, восток, север и юг соответственно, а символы ‘W’, ‘E’, ‘N’, ‘S’ обозначают толчки кладоискателя в соответствующих направлениях.
Пример файлов входных и выходных данных:
INPUT.TXT |
OUTPUT.TXT |
|
3 3 ..Y .B. TXX |
YES sWnwS |
Олимпиады в сети
Test-the-Best.by соревнования по спортивному программированию
Скачать задания в Word
Сайт открыт 1 мая 2006г.
