П’ятий тур - 2012

скачати файл завдання (*.doc)

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

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

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

Ім’я вхідного файлу: NUMERIC.DAT

Ім’я вихідного файлу: NUMERIC.SOL

Максимальний час роботи на одному тесті: 2с

Написати програму для знаходження кількості N-розрядних чисел, що володіють наступними властивостями:

- складаються лише з цифр 1, 2 та 3;

- не містять підряд двох однакових цифр 1 та 3;

- містять цифру 2 або групу з цифр 2 лише тоді, коли в записі числа зліва знаходиться цифра 1, а справа – цифра 3.

Наприклад, при N=4 це будуть числа: 1313, 3131, 1231, 1223, 3123.

Формат вхідних даних.

Єдиний рядок вхідного файлу NUMERIC.DAT містить натуральне число N (1<=N<=45).

Формат вихідних даних.

Єдиний рядок вихідного файлу NUMERIC.SOL повинен містити одне натуральне число – відповідь.

Приклад.

NUMERIC.DAT:

4

NUMERIC.SOL:

5

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

Ім’я вхідного файлу: FISHER.dat

Ім’я вихідного файлу: FISHER.sol

Максимальний час роботи на одному тесті: 5 с.

Один рибалка для гарного улову прикормив на річці декілька місць. Всього таких місць виявилось N (1<=N<=100). Розпочав він рибалити в нульовий момент часу на першому місці.

Так як результат лову його не зовсім задовольняв, він вирішив порибалити на інших місцях. Але щоб перейти з одного місця на інше необхідно затратити деякий час.

Всього він рибалив протягом T (1<=T<=1000) хвилин.

Знаючи за весь цей час середньостатистичний улов риби в грамах за хвилину на кожному місці, а також час, який втрачається на перехід з одного місця на інше, необхідно написати програму для знаходження максимально можливого улову протягом T хвилин з врахуванням потраченого часу на переходи.

Формат вхідних даних.

Перший рядок файлу FISHER.dat містить два натуральні числа N та T. Далі знаходиться N-1 рядок вигляду:

V_1,2 V_1,3 … V_1,N

V_2,3 V_2,4 … V_2,N

…………

V_N-1,N

, де V_i,j – натуральне число, що вказує на кількість хвилин, які втрачаються при переході з i-ого місця на j-те місце, V_i,j = V_j,i .

Решта рядків мають вигляд:

…………

i T_i1 M_i1

i T_i2 M_i2

…………

i T_iK M_iK

…………

, де ціле додатне число M_i1 означає середньостатистичний улов в грамах за хвилину на i-ому місці протягом перших T_i1 хвилин, число M_i2 – улов в грамах за хвилину на i-ому місці протягом наступних T_i2 хвилин і т.д., T_i1 + T_i2 + … + T_iK = T.

Всі числа між собою розділені пробілами.

Формат вихідних даних.

Єдиний рядок вихідного файлу FISHER.SOL повинен містити одне натуральне число – максимальне можливий улов в грамах.

Приклад.

FISHER.DAT

3 30

20 5

10

1 20 120

1 10 50

2 25 80

2 5 400

3 30 120

FISHER.sol

3200