Завдання IІ етапу Всеукраїнської учнівської олімпіади

з інформатики 2014-2015 н.р.

Задача 1. «Код» (25 балів)

Ім’я файлу програми: kod.*

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

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

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

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

«Ігрове поле»  абстрактне, по вертикалі в нас види транспорту, а по горизонталі - номер прохідної ділянки маршруту Матриця тепер прямокутна 3х4 (три види транспорту і 4 ділянки  шляху) .

На малюнку представлене положення покажчиків і фішок до моменту виведення  першої і другої послідовності видів транспорту на  маршруті.

Вхідні дані. Вхідний текстовий файл містить один рядок з чотирицифровим числом.

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

Приклади файлів

Задача 2. «Варіанти» (25 балів)

Ім’я файлу програми: variant.*

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

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

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

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянок  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися Kразів. Потрібно визначити кількість способів, якими можна проїхати маршрут.

Вхідні дані. Вхідний текстовий файл містить один рядок з трьома цілини числами N,M,K (1≤M,K,N≤50)).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає кількість варіантів проїзду.

Приклад файлів

Задача 3. «Транспорт» (25 балів)

Ім’я файлу програми: transport.*

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

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

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …).  Кожним з видів транспорту можна скористуватися A_M разів і при цьому вартість одного проїзду цим видом транспорту B_M, де M номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку два цілих числа N,M (1≤M≤N≤1000000)). Два наступних рядки місять по M цілих чисел, які задають кількість можливих варіантів проїзду і вартість проїзду (0≤2A_M,B_M ≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду. Якщо проїзд неможливий то вивести “no”.

Приклад файлів

Задача 4. «Оптимальний маршрут» (25 балів)

Ім’я файлу програми: optimal.*

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

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

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

Для  того, щоб подолати шлях від початкового пункту до кінцевого, потрібно пройти  N  ділянки  маршруту.  Кожну з ділянок  можна  подолати одним з M видів транспорту (літаком, або потягом, або  автомобілем, …). Кожним з видів транспорту можна скористатися не більше K разів.  Вартість проїзду для кожної ділянки певним видом транспорту задано в таблиці T_NM, де N – номер ділянки, M - номер виду транспорту. Потрібно визначити мінімальну вартість витрат на подолання шляху.

Вхідні дані. Вхідний текстовий файл містить три рядки. В першому рядку три цілих числа N, M, K (1≤N, M, K≤1000)). В наступних M рядках містяться по N цілих чисел, які задають вартість проїзду (0≤T_MN ≤2147483647).

Вихідні дані. Вихідний текстовий файл містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду.

Приклад файлів