П’ятий тур - 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 рядок вигляду:
V1,2 V1,3 … V1,N
V2,3 V2,4 … V2,N
…………
VN-1,N
, де Vi,j – натуральне число, що вказує на кількість хвилин, які втрачаються при переході з i-ого місця на j-те місце, Vi,j = Vj,i .
Решта рядків мають вигляд:
…………
i Ti1 Mi1
i Ti2 Mi2
…………
i TiK MiK
…………
, де ціле додатне число Mi1 означає середньостатистичний улов в грамах за хвилину на i-ому місці протягом перших Ti1 хвилин, число Mi2 – улов в грамах за хвилину на i-ому місці протягом наступних Ti2 хвилин і т.д., Ti1 + Ti2 + … + TiK = 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
|
