ЗАДАЧИ НА ОЛИМПИАДУ ПО ПРОГРАМММИРОВАНИЮ ДЛЯ 3-4 КУРСА
Время работы программы, там где не указано, не должно
превосходить 2-5 секунд. Ввод ТОЛЬКО из файла INPUT.TXT, вывод
ТОЛЬКО в файл OUTPUT.TXT. Никакого ввода-вывода на экран!
1. Транслятор с языка мини-Бейсик на Си (10 баллов)
------------------------------------
Язык мини-Бейсик можно описать следущим образом:
строка :=: метка оператор
оператор :=: REM текст
| PRINT "текст"
| PRINT выражение
| INPUT переменная
| LET переменная = выражение
| GOTO метка
| IF выражение ==|!=|>=|>|<|<= выражение THEN метка
| GOSUB метка
| RETURN
| END
выражение :=: число
| переменная
| ( выражение )
| выражение +|-|*|/ выражение
числа и метки - это целые числа (не превосходящие 32767).
переменные - это 1 (одна!) буква от A до Z (т.е. всего 26 ЦЕЛЫХ
переменных)
В файле INPUT.TXT находится синтаксически правильная
программа на языке мини-Бейсик (до 100 строк). Метки операто-
ров идут в порядке возрастания. Глубина вызова подпрограмм не
превосходит 10. Последним оператором программы является END.
Ключевые слова и имена переменных написаны прописными буквами
(как в примерах).
В файле OUTPUT.TXT должен находиться текст программы на
языке Си, которая выполняет действия, описанные программой на
языке мини-Бейсик.
Пример работы программы:
INPUT.TXT
10 PRINT "Введи число:"
20 INPUT N
25 LET S=0
30 LET I = 1
35 IF I>N THEN 60
40 LET S = S + I
50 LET I = I + 1
55 GOTO 35
60 PRINT "Результат вычислений:"
70 PRINT S
100 END
OUTPUT.TXT ! Должен сильно отличаться от вашего вывода
main()
int N,S,I;
printf("%s\n","Введи число:");
scanf("%d",&N);
S=0;
for(I=1;I<=N;I++)
S=S+I;
printf("%s\n","Результат вычислений:");
printf("%d\n",S);
exit(0);
Другой пример программы для тестирования можно взять из LUNAR.BAS
2. Замощение фигуры (7 баллов)
----------------
Найти способ замощения фигуры L-образными элементами вида:
#
#
##
В файле INPUT.TXT в первой строке задается количество
строк и столбцов для формы, определяющей фигуру, далее идет
форма. В файле OUTPUT.TXT должно выводиться разбиение заданной
фигуры на L-образные элементы. Разные L-элементы обозначаются
разными буквами. Число клеток в фигуре не будет превышать 100.
Если разбиение невозможно, вывести только слово "НЕВОЗМОЖНО".
Время работы программы не должно превышать 15 секунд.
Пример работы программы:
INPUT.TXT
5 10
...#...... . - пустая клетка
..####.... # - принадлежащая фигуре
######....
..####.#..
..#..###..
OUTPUT.TXT
...E...... . - пустая клетка
..DEBB.... A - принадлежащая L-элементу A
DDDEEB.... ...
..CCCB.A.. Z - принадлежащая L-элементу Z
..C..AAA..
3. Слово без повторений (5 баллов)
--------------------
Построить из трех заданных букв слово длины N, так чтобы
никакие два стоящих подряд подслова не совпадали.
В файле INPUT.TXT в первой строке идет длина слова
N<=1000, во второй строке - три буквы, из которых надо постро-
ить слово. Результат выводится в файл OUTPUT.TXT. Если постро-
ение такого слова невозможно, в файл OUTPUT.TXT вывести сооб-
щение "НЕВОЗМОЖНО". Время работы программы не должно превышать
20 секунд для N=1000.
Пример работы программы:
INPUT.TXT
10
abc
OUTPUT.TXT
abacabcacb
4. Вывод дерева (5 баллов)
------------
В файле INPUT.TXT задан список каталогов (до 100 строк).
В файл OUTPUT.TXT вывести дерево каталогов (a-la Norton
Commander).
Пример работы программы:
INPUT.TXT
\TOOLS
\TOOLS\ARC
\WORK\PS-101
\TOOLS\DRIVERS
\TOOLS\DRIVERS\VESA
\WORK\PS-101\MOE
OUTPUT.TXT
\
+-TOOLS
| +-ARC
| +-DRIVERS
| +-VESA
+-WORK
+-PS-101
+-MOE
5. Генерация множества (4 балла)
-------------------
Напишите программу для генерации первых N (N<=1000) по-
парно различных чисел множества M, которое определяется следу-
ющим образом:
а) число 1 принадлежит M
б) если x принадлежит M, то y=2*x+1 и z=3*x+1 также принадлежат M
в) никакие другие числа не принадлежат M.
Выводимые элементы множества M должны быть упорядочены по
возрастанию. Время работы программы не должно превышать 5 се-
кунд для N=1000.
Пример работы программы:
INPUT.TXT
7
OUTPUT.TXT
1 3 4 7 9 10 13