Х Всеукраїнська олiмпiада з iнформатики

1 тур

1. Домiно

Завдання. Написати програму DOMINO.*, яка буде пiдраховувати кiлькiсть варiантiв покриття прямокутника 2хN прямокутниками 2х1. Покриття, що перетворюються одне в одне симетрiями, вважати рiзними.

Вхiднi данi. Вхiдний файл DOMINO.DAT мiстить число N (0<N<65536).

Вихiднi данi. Вихiдний файл DOMINO.SOL повинен мiстити одне число: кiлькiсть варiантiв.

Приклади введення i виведення

2. Монети

Є монети з рiзними фiксованими номiналами, вираженими в копiйках (наприклад, 3 i 5 копiйок) в достатнiй кiлькостi. Написати програму COINS.*, що:

а) визначає, чи можна подати задану суму S (виражену в копiйках), користуючись монетами заданих номiналiв,

б) якщо це можливо, то подає цю суму за допомогою мiнiмальної кiлькостi монет.

Вхiднi данi: Вхiдний файл COINS.DAT мiстить в першому рядку суму S (0? S? 1000000000), в другому рядку - N - кiлькiсть рiзних номiналiв (0? S? 20), а в наступних N рядках - А₁ ... А_N - номiнали (в порядку зростання) якi можна використовувати (0<A₁<A₂<...<A_N? 1000000000).

Вихiднi данi: Вихiдний файл COINS.SOL повинен мiстити в першому рядку знак "+", якщо задану суму S можна подати, та знак "-", якщо не можна. Якщо подана сума iснує, то наступнi N рядкiв повиннi мiстити кiлькостi монет кожного номiналу, якi потрiбнi для поданнi суми S за допомогою мiнiмальної кiлькостi монет.

Приклади введення i виведення

подати 514 копiйок за допомогою монет номiналом в 3 i 5 копiйок

подати 514 копiйок за допомогою монет номiналом в 3 i 5 копiйок

3. Прямокутники

На площинi задано многокутник. Треба написати програму RECT.*, що визначає прямокутник мiнiмальної площi, який мiстить в собi заданий многокутник. Наприклад, для многокутника

вiдповiдним прямокутником буде

Вхiднi данi: Вхiдний файл RECT.DAT мiстить в 1-му рядку цiле число N - кiлькiсть вершин многокутника (3? N? 3000), в наступних N рядках - по два дiйсних числа X_i, Y_i - координати вершин многокутника в порялку їх обходу за годинниковою стрiлкою.

Вихiднi данi: Вихiдний файл RECT.SOL повинен мiстити 5 рядкiв: в першому рядку число S - площа прямокутника, а в наступних 4-х рядках - пари координат X_i, Y_i вершин прямокутника в порядку їх обходу (в довiльному напрямку).

Технiчнi умови.

1. Всi координати у вхiдному i вихiдному файлах подаються у виглядi дiйсних чисел в форматi, що обробляється стандартгними функцiями введення-виведення.

2. Рекомендований тип даних для координат - Real в Pascal i float в С та С++.

3. Оптимальну площу i координати прямокутника треба визначити з точнiстю до 10^-5.

Приклад введення i виведення

2 тур

Нiм

В гру Нiм грають двоє. Є (2? N? 100) купок камiнцiв. Гравцi по черзi беруть камiнцi з купок. Виграє той, хто вiзьме останнiй камiнець. на кожному ходi гравецьможе брати камiнцi не бiльше нiж з K (1? K? N) купок, але повинен взяти хоча б один камiнець. На початку гри в кожнiй купцi 0<H[i]<1000000000 камiнцiв.

Завдання. Напишiть програму, яка буде грати в Нiм та, по можливостi, вигравати.

Технiчнi умови. Пiд час перевiрки до Вашої програми буде приєднано (linked) модуль перевiрки, який називається CHECK.* (PAS, C чи CPP). Цей модуль мiстить 3 функцiї: InitGame, JudgeTurn, PartTurn.

Функцiя InitGame використовується для зчитування вхiдних даних з тестового файлу. Вона має 4 вихiдних параметри: N та K - кiлькостi купок: масив Н - кiлькостi камiнцiв в купках, First - хто перший ходить. Пiсля виклику цiєї функцiї N та K отримають вiдповiднi значення, в перших N елементах масиву Н будуть кiлькостi камiнцiв в купках, а First приймає значення 0, якщо першою ходить програма переiвiрки (журi) та 1, якщо перщою ходить програма учасника. Звернiть увагу, що Ваша програма не повинна самостiйно читати вхiднi данi, це треба робити тiльки за допомогою функцiї InitGame.

Функцiю JudgeTurn Ваша програма буде викликати, коли їй потрiбно буде отримати черговий хiд журi. Єдиний вихiдний параметр цiєї функцiї - масив Т, першi N елементiв якої мiстять кiлькостi камiнцiв, що перевiряюча програма бере з купок. Вiдповiднiсть ходу умовам гри гарантується.

Функцiю PartTurn Ваша програма буде викликати, щоб повiдомити перевiряючiй програмi свiй хiд. Запишiть свiй хiд в першi N елементiв масиву Т.

Кожна з цих функцiй повертає 1, якщо все гаразд, або 0, якщо виникла помилка, i Ваша програма може припиняти роботу.

На отриманiй Вами дискетi буде модуль перевiрки (CHECK.*) та головний модуль (NIM_KBD.*). Вони надаються тiльки для того, щоб Ви могли швидко почати роботу над розв'язком, не втрачаючи час на технiчнi проблеми. Модуль CHECK виконує зчитування даних з клавiатури, перевiрку ходiв учасника та послiдовностi викликiв функцiї, але дуже погано грає. Журi при перевiрцi буде використовувати iнший. Модуль NIM_KBD викликає функцiї модуля CHECK в потрiбнiй послiдовностi, але замiсть обчислення наступного ходу учасника читає його з клавiатури. Ваша задача i полягає в тому, щоб функцiя MakeTurn обчислювала наступний хiд. Журi не наполягає на використаннi означених файлiв, але ваш розв'язок повинен коректно взаємодiяти з модулем CHECK.

Примiтка. При перевiрцi серед тестiв будуть такi частковi випадки:

1) N=2, K=1; 2) N=3, K=1; 2) N>3, K=1.

Програма- розв'язок - NIM.PAS, NIM.CPP, NIM.C.

Приклад

N=4, K=2, First=1, H=(3,4,5,6).