Х комплексная олимпиада "Турнир чемпионов"
Задания по информатике
Задача СЛОВА (WORDS). Дан словарь из N слов и одна фраза. Из этой фразы удаляют некоторые буквы так, чтобы в ней остались только слова из словаря. Слова в получившейся фразе могут встречаться несколько раз или не встречаться вовсе, однако не могут накладываться друг на друга.
Напишите программу WORDS, которая читает число - количество слов в словаре, затем сами слова и фразу из файла WORDS.DAT и записывает максимальное число слов X в файл WORDS.SOL.
Ограничения:
1<= N <= 10. Слова и фраза состоят из маленьких английских букв. Их длина не превышает 250 символов.
| Формат файла WORDS.DAT: |
Формат файла WORDS.SOL: |
N
слово1
...
словоN
фраза |
Х
|
Пример:
| WORDS.DAT: |
WORDS.SOL: |
3
fee
and
mathematics
setupfeewaivedandfreedomains |
3
|
Задача СУММА (SUM).
Дана последовательность целых чисел X1,X2,...,XN. Из нее можно исключить некоторые числа, но не все. Из полученной последовательности Y1 Y2,...,YN (1<= K<= N) составляют сумму S = Y1 - 2Y2 + 3Y3 - Y4 + ,..., + (-1)k+1 . Какую наибольшую сумму S можно так получить?
Напишите программу SUM, которая читает числа N, X1, X2,..., XN.из файла SUM.DAT и записывает число S в файл SUM.SOL.
Ограничения:
1<N<=1000 ,-1000 <= Xj <= 1000 (j = 1,2,...,N)
| Формат файла SUM.DAT: |
Формат файла SUM.SOL: |
N
X1
X2
...
XN. |
S
|
Пример:
| SUM.DAT: |
SUM.SOL: |
4
1
2
3
4
|
9
|
Задача ТАБЛИЦА (TABLE).
Дана доска розмером M x N клеток ( M горизонталей, N вертикалей). Надо провести фигуру из левого нижнего в правый верхний угол за минимальное число шагов. За один шаг фигуру можно переместить в одну из соседних по горизонтали или по вертикали клеток или оставить на месте. Проход между соседними горизонталями и вертикалями бывает закрыт. А именно:
· если номер очередного шага кратен V1, то фигура не может переходить с горизонтали i на горизонталь i+1 и наоборот;
· если номер очередного шага кратен H1, то фигура не может переходить с вертикали j на вертикаль j+1 и наоборот.
Горизонтали и вертикали отсчитываются с левого нижнего угла доски.
Напишите программу TABLE, которая читает числа M ,N ,H1 ,V1 из файла TABLE.DAT и записывает наименьшее количество шагов K в файл TABLE.SOL.
Ограничения:
1< M ,N <= 1000, 1<H1 ,V1 <= 10
| Формат файла TABLE.DAT |
Формат файла TABLE.SOL |
M N
H1
...
HM-1
V1
...
VN-1 |
K
|
Пример:
| TABLE.DAT |
TABLE.SOL |
4 5
2
2
2
3
3
3
2 |
9
|
Памятка участника.
Решения задач - файлы с текстами программ, должны быть записаны на диск под именами words.pas, sum.pas, path.pas (или *.c, или *.cpp). Программы должны читать из текстовых файлов с расширением dat и записывать результаты в файлы с расширением sol.
Программа не должна ничего выводить на экран и не должна ждать ввода с клавиатуры!
Решения проверяются автоматически на наборе тестов. В текст программ изменения не вносятся и сам он не оценивается.
