Написання програм DOMINO, COINS і RECT (Завдання першого туру X Всеукраїнської олiмпiади з iнформатики)

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

1 тур

1. Доміно

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

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

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

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

2. Монети

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

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

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

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

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

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

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

подати 27 копійок за допомогою монет номіналом 5 і 13 коп.

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

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

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

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

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

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

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

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

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

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