https://chashuk23.wordpress.com/%D1%96%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0-%D0%B2-%D1%88%D0%BA%D0%BE%D0%BB%D1%96/%D0%BE%D0%BB%D1%96%D0%BC%D0%BF%D1%96%D0%B0%D0%B4%D0%B8-%D1%84%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2%D0%B8/
Завдання IІ етапу Всеукраїнської учнівської
олімпіади
з інформатики 2014-2015 н.р.
Задача
1. «Код» (25 балів)
Ім’я файлу програми: kod.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб подолати шлях від початкового
пункту до кінцевого, потрібно пройти
4 ділянки маршруту.
Кожну з ділянок можна перебороти або літаком, або потягом, або автомобілем. Кожним видом транспорту можна скористатися
двічі. За введеним чотирицифровим числом, яке задає код подолання маршруту,
потрібно вивести число, яке задає код кількості
використання транспорту, яким подолали маршрут..
«Ігрове поле» абстрактне, по вертикалі в нас види
транспорту, а по горизонталі - номер прохідної ділянки маршруту Матриця тепер
прямокутна 3х4 (три види транспорту і 4 ділянки
шляху) .
На малюнку
представлене положення покажчиків і фішок до моменту виведення першої і другої послідовності видів
транспорту на маршруті.
Вхідні
дані. Вхідний текстовий файл
містить один рядок з чотирицифровим числом.
Вихідні
дані. Вихідний текстовий файл
містить єдиний рядок з кодом, яке визначає транспорт.
Приклади файлів
input.txt
|
output.txt
|
1122
|
220
|
1123
|
211
|
Задача
2. «Варіанти» (25 балів)
Ім’я файлу програми: variant.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб подолати шлях від початкового
пункту до кінцевого, потрібно пройти
N ділянок маршруту.
Кожну з ділянок можна подолати одним з M видів транспорту (літаком,
або потягом, або автомобілем, …). Кожним з видів транспорту можна
скористуватися K разів. Потрібно визначити кількість способів, якими
можна проїхати маршрут.
Вхідні
дані. Вхідний текстовий файл
містить один рядок з трьома цілини числами N,M,K (1≤M,K,N≤50)).
Вихідні
дані. Вихідний текстовий файл
містить єдиний рядок з цілим числом, яке визначає кількість варіантів проїзду.
Приклад файлів
input.txt
|
output.txt
|
3 3
1
|
6
|
Задача
3. «Транспорт» (25 балів)
Ім’я файлу програми: transport.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб подолати шлях від початкового
пункту до кінцевого, потрібно пройти
N ділянки маршруту.
Кожну з ділянок можна подолати одним з M видів транспорту (літаком,
або потягом, або автомобілем, …). Кожним з видів транспорту можна
скористуватися AM разів і при цьому вартість одного проїзду цим
видом транспорту BM, де M номер виду транспорту. Потрібно визначити
мінімальну вартість витрат на подолання шляху.
Вхідні
дані. Вхідний текстовий файл
містить три рядки. В першому рядку два цілих числа N,M (1≤M≤N≤1000000)). Два
наступних рядки місять по M цілих чисел, які задають кількість можливих
варіантів проїзду і вартість проїзду (0≤2AM,BM ≤2147483647).
Вихідні
дані. Вихідний текстовий файл
містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду.
Якщо проїзд неможливий то вивести “no”.
Приклад файлів
input.txt
|
output.txt
|
3 2
2 2
1 2
|
4
|
Задача
4. «Оптимальний маршрут» (25 балів)
Ім’я файлу програми: optimal.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 5с
Для того, щоб подолати шлях від початкового
пункту до кінцевого, потрібно пройти
N ділянки маршруту.
Кожну з ділянок можна подолати одним з M видів транспорту (літаком,
або потягом, або автомобілем, …). Кожним
з видів транспорту можна скористатися не більше K разів. Вартість проїзду для кожної ділянки певним
видом транспорту задано в таблиці TNM, де N – номер ділянки, M -
номер виду транспорту. Потрібно визначити мінімальну вартість витрат на
подолання шляху.
Вхідні
дані. Вхідний текстовий файл
містить три рядки. В першому рядку три цілих числа N, M, K (1≤N, M, K≤1000)). В
наступних M рядках містяться по N цілих чисел, які задають вартість проїзду
(0≤TMN ≤2147483647).
Вихідні
дані. Вихідний текстовий файл
містить єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду.
Приклад файлів
input.txt
|
output.txt
|
2 2
1
2 2
1 2
|
3
|
Розв'язки
Завдання IІ етапу Всеукраїнської учнівської олімпіади
з інформатики 2014-2015 н.р.
Задача 1. «Код» (25 балів)
Ім’я файлу програми: kod.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб
подолати шлях від початкового пункту до кінцевого, потрібно пройти 4
ділянки маршруту. Кожну з ділянок можна
перебороти або літаком, або потягом, або
автомобілем. Кожним видом транспорту можна скористатися двічі. За
введеним чотирицифровим числом, яке задає код подолання маршруту, потрібно вивести число, яке задає код кількості
використання транспорту, яким подолали маршрут..
«Ігрове поле»
абстрактне, по вертикалі в нас види транспорту, а по горизонталі - номер
прохідної ділянки маршруту Матриця тепер прямокутна 3х4 (три види транспорту і
4 ділянки шляху) .
На малюнку представлене положення покажчиків і фішок
до моменту виведення першої і другої
послідовності видів транспорту на
маршруті.
Вхідні дані. Вхідний текстовий файл містить один
рядок з чотирицифровим числом.
Вихідні дані. Вихідний текстовий файл містить
єдиний рядок з кодом, яке визначає транспорт.
Приклади файлів
input.txt
|
output.txt
|
1122
|
220
|
1123
|
211
|
Розв’язання
1)
В основі алгоритму лежить перебрати всі можливі варіанту
If (n==1122)
cout <<”220”<endl;
2)
Підрахувати кількість цифр числі
char a[4];cin>>a;
for(int i=0;i<4;i++)
b[a[i]-48]=b[a[i]-48]+1;
Задача 2. «Варіанти» (25 балів)
Ім’я файлу програми: variant.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб
подолати шлях від початкового пункту до кінцевого, потрібно пройти N
ділянок маршруту. Кожну з ділянок можна
подолати одним з M видів транспорту (літаком, або потягом, або автомобілем, …). Кожним з видів транспорту можна
скористуватися K разів. Потрібно визначити кількість способів, якими
можна проїхати маршрут.
Вхідні дані. Вхідний текстовий файл містить один
рядок з трьома цілини числами N,M,K (1≤M,K,N≤50)).
Вихідні дані. Вихідний текстовий файл містить
єдиний рядок з цілим числом, яке визначає кількість варіантів проїзду.
Приклад файлів
input.txt
|
output.txt
|
3 3 1
|
6
|
Розв’язання
1)
Якщо n=m, k=1: престановки 
int n;
long long f;
cin>>n;
f=1;
for(i=1;i<=n;i++)f=f*I;
cout<<f<<endl;
2)
Якщо n<=m, k=1: розміщення 
for(int
i=m-n+1;i<=m;i++) f=f*i;
cout<<f<<endl;
3)
Якщо n<=m, k>1:
Задача 3. «Транспорт» (25 балів)
Ім’я файлу програми: transport.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 1с
Для того, щоб
подолати шлях від початкового пункту до кінцевого, потрібно пройти N
ділянки маршруту. Кожну з ділянок можна
подолати одним з M видів транспорту (літаком, або потягом, або автомобілем, …). Кожним з видів транспорту можна
скористуватися AM разів і при цьому вартість одного проїзду цим
видом транспорту BM, де M номер виду транспорту. Потрібно визначити
мінімальну вартість витрат на подолання шляху.
Вхідні дані. Вхідний текстовий файл містить три
рядки. В першому рядку два цілих числа N,M (1≤M≤N≤1000000)). Два наступних
рядки місять по M цілих чисел, які задають кількість можливих варіантів проїзду
і вартість проїзду (0≤2AM,BM ≤2147483647).
Вихідні дані. Вихідний текстовий файл містить
єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду. Якщо
проїзд неможливий то вивести “no”.
Приклад файлів
input.txt
|
output.txt
|
3 2
2 2
1 2
|
4
|
Розв’язання
Пошук мінімальною вартості, та підрахунок суми витрат, поки не
набрано довжину N
//zad3
#include
"fstream"
using
namespace std;
ifstream
cin("input.txt");
ofstream
cout("output.txt");
int main()
{
long n,m,s(0),a[10001],b[10001],k(0),min=0,nm,i;
cin>>n>>m;
for (i=1;i<=m;i++)cin>>a[i];
for (i=1;i<=m;i++)cin>>b[i];
k=0;
while (k<n & min != 2147483647){
min=2147483647;
for (i=1;i<=m;i++)
if(b[i]<min){min=b[i];nm=i;}
//cout<<b[nm]<<"
"<<a[nm]<<endl;
if
(k+a[nm]<=n){k=k+a[nm]; s=s+a[nm]*b[nm];}
else
if
(k+a[nm]>n){s=s+(n-k)*b[nm];n=k;}
b[nm]=2147483647;
}
if (min!=2147483647)
cout<<s<<endl;else cout<<"no"<<endl;
}
Задача 4. «Оптимальний маршрут» (25 балів)
Ім’я файлу програми: optimal.*
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Максимальний час роботи на одному тесті: 5с
Для того, щоб
подолати шлях від початкового пункту до кінцевого, потрібно пройти N
ділянки маршруту. Кожну з ділянок можна
подолати одним з M видів транспорту (літаком, або потягом, або автомобілем, …). Кожним з видів транспорту
можна скористатися не більше K разів.
Вартість проїзду для кожної ділянки певним видом транспорту задано в
таблиці TNM, де N – номер ділянки, M - номер виду транспорту.
Потрібно визначити мінімальну вартість витрат на подолання шляху.
Вхідні дані. Вхідний текстовий файл містить три
рядки. В першому рядку три цілих числа N, M, K (1≤N, M, K≤1000)). В наступних M
рядках містяться по N цілих чисел, які задають вартість проїзду (0≤TMN ≤2147483647).
Вихідні дані. Вихідний текстовий файл містить
єдиний рядок з цілим числом, яке визначає мінімальну вартість проїзду.
Приклад файлів
input.txt
|
output.txt
|
2 2 1
2 2
1 2
|
3
|
Розв’язання
1)
Мінімальне
значення в кожному стовпці без повтору рядків
2)
Перебір
3)
Динамічне
Немає коментарів:
Дописати коментар