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