Завдання п'ятого туру

Розв’язки задач відправляти з 22.11 по 5.12.2010 р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

1. Задача  DOMINO (20 балів)

Ім’я вхідного файлу: DOMINO.DAT
Ім’я вихідного файлу: DOMINO.SOL
Максимальний час роботи на одному тесті: 20с

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

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

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

Приклади вводу і виводу
DOMINO.DAT :

1
DOMINO.SOL :

1

2. Задача   FRACTION(100 балів)

Ім’я вхідного файлу: FRACTION.DAT
Ім’я вихідного файлу: FRACTION.SOL
Максимальний час роботи на одному тесті: 3с

Знайти суму двох нескоротних дробів A/B i C/D. Результат записати у вигляді нескоротного дробу.

Вхідні дані. Вхідний файл FRACTION.DAT містить числа  A, B, C, D (1 < A, B, C, D < 10^{^1000}), кожне з яких записане в окремому рядку.

Вихідні дані. Вихідний файл FRACTION.SOL повинен містити два числа, записаних у різних рядках: чисельник дробу і знаменник дробу.

Приклади вводу і виводу
FRACTION.DAT :

1

6

1

3
FRACTION.SOL :

1

2