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

Страницы работы

Содержание работы

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

1 тур

1. Доміно

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

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

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

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

DOMINO.DAT

DOMINO.SOL

1

1

·

·

1

DOMINO.DAT

DOMINO.SOL

4

5

·

·

·

·

·

·

·

·

5

·

·

·

·

·

·

·

·

4

·

·

·

·

·

·

·

·

3

·

·

·

·

·

·

·

·

2

·

·

·

·

·

·

·

·

1

2. Монети

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

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

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

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

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


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

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

COINS.DAT

COINS.SOL

514

+

2

3

3

101

5

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

COINS.DAT

COINS.SOL

27

-

2

5

13

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

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

 


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

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

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

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

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

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

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

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

RECT.DAT

RECT.SOL

6

32.0

0.0 0.0

4.0 4.0

3.0 2.0

0.0 8.0

4.0 4.0

4.0 -4.0

5.0 2.0

0.0 0.0

8.0 0.0

4.0 1.0

Похожие материалы

Информация о работе