|
Завдання III-го етапу Всеукраїнської учнівської олімпіади з інформатики
Івано-Франківськ – 2007
| Задача 1. Різні слова в двох текстах (15 балів) |
Задача 2. Прямокутники (20 балів) |
Задано два тексти. Необхідно написати програму, яка виводить лише ті слова, які зустрічаються тільки в першому чи другому тексті. Слово - це послідовність великих літер латинського алфавіту та цифр; символи: пропуски, коми, крапки, знаки оклику, знаки запитання - вважати розділювачами. Тексти відрізняються хоча б одним словом.
Формат вхідних даних: файл 1.in містить обидва тексти, кожен у окремому рядку. Довжина рядка не перевищує 250 символів.
Формат вихідних даних: файл 1.out містить знайдені слова, кожне в окремому рядку, в тій послідовності, в якій вони зустрічаються в першому, а потім у другому текстах.
| 1.in | 1.out |
I LOVE YOU, BABY
I LOVE MARRY |
YOU
BABY
MARRY |
. . . YGJ22!!UHS.
TFS, YGJ22 |
UHS
TFS |
|
Вершини прямокутників знаходяться в точках перетину прямокутної сітки розміром MxN. Скласти програму, яка визначає кількість можливих прямокутників різних розмірів, що можна помістити на цій сітці довільним чином.
Формат вхідних даних: файл 2.in містить рядок з двома числами M та N (M,N<100), розділених пропуском.
Формат вихідних даних: файл 2.out Містить рядок з числом - кількість прямокутників.
|
| Задача 3. Шашки (30 балів) |
Задача 4. Свиня-скарбничка (35 балів) |
В довільних клітинках шахової дошки розміру 8х8 розставлені шашки, причому не більше однієї шашки на клітинці. Будемо називати кластерами такі групи шашок, які групуються за правилами: кожна шашка може входити не більше, ніж в один кластер, якщо дві шашки розташовані у сусідніх клітинках (що мають спільну вершину або сторону), то вони входять у склад одного кластера.
Написати програму, яка для заданого числа шашок N і їхніх координат виводить число кластерів і число окремих шашок.
Формат вхідних даних: файл 3.in містить у першому рядку кількість шашок N, у наступних N рядках координати кожної шашки (координати задаються у шаховому форматі: a1, a2, ..., a8, b1, ..., h1, ..., h8).
Формат вихідних даних: файл 3.out містить у першому рядку кількість кластерів, у другому - кількість окремих шашок
|
Для того, щоб почати бізнес, юний комерсант вирішив накопичити трохи грошей. З цією метою він знайшов свиню-скарбничку і почав збирати гроші. Відомо, що визначити накопичену суму можна тільки розбивши цю скарбничку. Однак юному комерсанту не хотілось робити це передчасно, тобто до тих пір, поки там не накопичилась потрібна сума. Уникнути цього йому допоміг товариш, який порадив, як можна оцінити мінімальну кількість грошей всередині скарбнички, знаючи її вагу без монет, вагу з монетами і вагу монет кожного типу.
Написати програму, яка б визначала мінімальну суму грошей, яка може знаходитись у скарбничці.
Формат вхідних даних: файл 4.in містить в першому рядку два цілих числа: E - вага порожньої скарбнички (1<=E<=10000); F - вага скарбнички, заповненої монетами (1<=E<=F<=10000). Другий рядок містить ціле число N (1<=N<=50) - кількість типів монет. Далі знаходиться N рядків опису монет різних типів. Кожен рядок містить два числа Pi і Wi (1<=Pi<=1000, 1<=Wi<=10000, 1<=i<=N), де Pi - номінал монети i-го типу, а Wi її вага. Монети однакового номіналу мають однакову масу.
Формат вихідних даних: файл 4.out містить одне ціле число - значення мінімальної суми грошей, яка може знаходитись в скарбничці.
| 4.in | 4.out |
10 110
2
1 1
30 50 |
60 |
20 120
2
1 1
50 30 |
100 |
|
|
|
|