Сайт підготовки до олімпіади з інформатики

програмування в С++

Школа олімпійського резерву з інформатики
4. Готуємось до олімпіади з інформатики PDF Печать E-mail
Добавил(а) Administrator   
22.01.15 09:19

ІІIетапВсеукраїнськоїучнівськоїолімпіадизінформатики(м.Луцьк) 2013-2014н.р

http://www.e-olimp.com.ua/problems/7234

http://www.e-olimp.com.ua/ua/problems/7235

http://www.e-olimp.com.ua/ua/problems/7236

http://www.e-olimp.com.ua/ua/problems/7237

http://www.e-olimp.com.ua/ua/problems/7238

http://www.e-olimp.com.ua/ua/problems/7239

http://www.e-olimp.com.ua/ua/problems/7240

http://www.e-olimp.com.ua/ua/problems/7241

http://www.e-olimp.com.ua/ua/problems/7242

http://www.e-olimp.com.ua/ua/problems/7243

Матеріали IІІетапуВсеукраїнськоїучнівськоїолімпіадизінформатики 2013-2014

A. Кондиціонер Степана

В офісі, де Степан працює програмістом, встановили кондиціонер нового типу. Цей кондиціонер відрізняється особливою простотою в управлінні. У кондиціонера є всього лише два керованих параметра: бажана температура і режим роботи.

Кондиціонер може працювати в наступних чотирьох режимах:

- «freeze» - охолодження. У цьому режимі кондиціонер може тільки зменшувати температуру. Якщо температура в кімнаті і так не більше бажаної, то він вимикається.

- «heat» - нагрів. У цьому режимі кондиціонер може тільки збільшувати температуру. Якщо температура в кімнаті і так не менше бажаної, то він вимикається.

- «auto» - автоматичний режим. У цьому режимі кондиціонер може як збільшувати, так і зменшувати температуру в кімнаті до бажаної.

- «fan» - вентиляція. У цьому режимі кондиціонер здійснює тільки вентиляцію повітря і не змінює температуру в кімнаті.

Кондиціонер досить потужний, тому при налаштуванні на правильний режим роботи він за годину доводить температуру в кімнаті до бажаної.

Потрібно написати програму, яка по заданій температурі в кімнаті troom, встановленим на кондиціонері бажаної температурі tcond і режиму роботи визначає температуру, яка встановиться в кімнаті через годину.

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа troom, і tcond, розділених рівно одним пропуском (-50 ≤ troom ≤ 50 , -50 ≤ tcond ≤ 50).
Другий рядок містить одне слово, записане малими літерами латинського алфавіту - режим роботи кондиціонера. 

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

Пояснення до прикладів:

У першому прикладі кондиціонер знаходиться в режимі нагріву. Через годину він нагріє кімнату до бажаної температури в 20 градусів.

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

Приклади вхідних та вихідних даних:

cond.in

cond.out

10 20

heat

20

10 20

freeze

10

#include "fstream"

#include "string.h"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{int t, t1, t2;

char r[10];

cin>>t1>>t2;

cin>>r;

if(t1<=t2 && strcmp(r,"freeze")==0) t=t1;

if(t1>t2 && strcmp(r,"freeze")==0) t=t2;

if(t1<t2 && strcmp(r,"heat")==0) t=t2;

if(t1>=t2 && strcmp(r,"heat")==0) t=t1;

if(strcmp(r,"auto")==0) t=t2;

if(strcmp(r,"fan")==0) t=t1;

cout<<t<<endl;

return 0;

}

#include<fstream>
#include<string>
using namespace std;
ifstream in("cond.in");
ofstream out("cond.out");
string s; int a,b;
int main()
{in>>a>>b;
        in>>s;
        if (s=="heat")
        {
                if (a<=b) out<<b<<endl; else out<<a<<endl;
        }
        else
        {
                if (s=="freeze")
                {
                        if (a>=b) out<<b<<endl; else out<<a<<endl;
                }
                else
                {              if (s=="auto") out<<b<<endl; else
                                if (s=="fan") out<<a<<endl;
                }
        }
}

B. "Поле чудес"

Степан пройшов до суперфіналу новорічного шоу "Поле чудес". На відміну від звичайних ігор новорічна відрізняється тим, що проводиться не за круглим барабаном, а на прямокутному полі, розбитому на квадратики. Кожен такий квадратик містить одне число (числа можуть бути як доданими, так і від'ємними). Гравець розташовується у верхній лівій клітинці і може переміщуватись у три сусідніх клітинки: праву, нижню та праву нижню по діагоналі (див. малюнок) і повинен потрапити до правої нижньої клітинки.  

Звісно, що Степан має бажання виграти гру і набрати якомога більше балів. Якщо набрана сума додатна, то Степан виграв, інакше програв.

Напишіть програму, яка доможе Степану визначити програє чи виграє він у грі і яку суму він зможе набрати.

Формат вхідних даних:Перший рядок вхідного файлу містить два цілих числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) - розміри ігрового поля.

Наступні N рядків містять по М цілих чисел - значення клітинок ігрового поля, по модулю не більші за 1000. 

Формат вихідних даних:Перший рядок вихідного файлу має містити одне слово - winner, якщо Степан виграв гру, або loser - в іншому випадку.

Другий рядок має містити одне число - набрану суму.

Приклади вхідних та вихідних даних:

wonderland.in

wonderland.out

2 3

2 1 1

-1 2 1

winner

6

2 3

1 -2 -1

-2 1 -2

loser

0

#include<fstream>
#include<string>
using namespace std;
ifstream in("wonderland.in");
ofstream out("wonderland.out");
int i,j,n,m,a[101][101],b[101][101],x,y;
int main()
{
        in>>n>>m;
        for (i=1;i<=n;i++)
                for (j=1;j<=m;j++)
                {
                        in>>a[i][j];
                        b[i][j]=-999999;
                }
        b[1][1]=a[1][1];
        for (i=2;i<=n;i++)
                b[i][1]=b[i-1][1]+a[i][1];
        for (j=2;j<=m;j++)
                b[1][j]=b[1][j-1]+a[1][j];
        //for (i=2;i<=min(n,m);i++)
        //        b[i][i]=b[i-1][i-1]+a[i][i];
        i=2;j=2;
        while (i!=min(n,m)+1 || j!=min(m,n)+1)
        {
                b[i][j]=max(max(b[i-1][j]+a[i][j],b[i][j]),max(b[i-1][j-1]+a[i][j],b[i][j-1]+a[i][j]));
                for (x=2;x<=n;x++)
                        b[x][j]=max(max(b[x-1][j]+a[x][j],b[x][j]),max(b[x-1][j-1]+a[x][j],b[x][j-1]+a[x][j]));
                for (y=2;y<=m;y++)
                        b[i][y]=max(max(b[i-1][y]+a[i][y],b[i][y]),max(b[i-1][y-1]+a[i][y],b[i][y-1]+a[i][y]));
                i++;j++;
        }
        i=1;j=1;
        if (b[n][m]>0) out<<"winner"<<endl; else out<<"loser"<<endl;
        out<<b[n][m]<<endl;
}

C. Winter

Країна Ужляндія славиться своїми ідеальними дорогами, але навіть вони не витримали цьогорічної аномально холодної та сніжної зими. Деякі з доріг виявилися заблокованими для руху автомобілістів. Внаслідок цього порушився зв’язок між містами Ужляндії. Два міста країни вважаються з’єднаними, якщо можна дістатися з одного міста в інше, рухаючись не заблокованими дорогами, можливо, через інші міста.

Сусідня братська держава відома на весь світ своїми унікальними обігрівачами. Керівництво країни вирішило надати Ужляндії гуманітарну допомогу. Було вирішено, що обігрівачі доставлятимуться на гвинтокрилі, а далі за допомогою вантажівок розвозитимуться по містах. Оскільки авіаційне паливо не дешеве, потрібно мінімізувати кількість приземлень гвинтокрила так, щоби кожне місто отримало необхідні обігрівачі. Будь ласка, якомога швидше порахуйте цю кількість і врятуйте мешканців Ужляндії.

Формат вхідних даних: В першому рядку записано два числа N і M (1 ≤ N ≤ 100000,0 ≤ M ≤ 200000)– кількість міст в Ужляндії та кількість не заблокованих доріг відповідно. В наступних M рядках записано по два числа i та j (1 ≤ i,j ≤ N), що значить дорога між містами з номерами i та j не заблокована. Міста в Ужляндії нумеруються в 1 до N.

Формат вихідних даних:В єдиному рядку виведіть мінімальну кількість приземлень гвинтокрила.

Пояснення до прикладу:

Міста 1, 2 та 3 з’єднані між собою, а тому щоби забезпечити їх обігрівачами, необхідно здійснити одне приземлення в одному з цих міст, далі обігрівачі доставлять вантажівками. Міста 4 та 5 зв’язані між собою, тому треба ще одне приземлення. І нарешті місто 6, яке ізольоване від інших, щоби доставити обігрівачі в це місто, треба окреме приземлення гвинтокрила. Всього виходить 3 приземлення.

Приклади вхідних та вихідних даних:

winter.in

winter.out

6 4

3 1

1 2

5 4

2 3

3

Winter

За умовою задачі маємо Nміст, деякі з яких з’єднані між собою дорогами. Очевидно, щоби доставити обігрівачі в міста, що утворюють одну компоненту зв’язності, потрібно лише одне приземлення гвинтокрила в будь-якому місті цієї компоненти.

Отже, треба порахувати кількість компонент зв’язності в неорієнтованому графі, що складається з N вершин та M ребер, застосувавши для цього пошук в глибину (Алгоритм пошуку компонент зв'язності у графі - http://e-maxx.ru/algo/connected_components). Отриманий результат задовольняє умову оптимальності, а тому буде відповіддю на задачу.

#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("winter.in");
ofstream out("winter.out");
bool used[100001];
vector<vector<int> > a;
int n,m,i,x,y;
void dfs(int v)
{
        used[v]=1;
        for (vector<int>::iterator q=a[v].begin();q!=a[v].end();++q)
                if (!used[*q]) dfs(*q);
}
int main()
{
        in>>n>>m;
        a.resize(n);
        for (i=1;i<=m;i++)
        {
                in>>x>>y;
                a[x-1].push_back(y-1);
                a[y-1].push_back(x-1);
        }
        int ans=0;
        for (i=0;i<n;i++)
        {
                if (used[i]==0)
                {
                        ans++;
                        dfs(i);
                }
        }
        out<<ans<<endl;
}

#include "stdafx.h"

#include "iostream"

using namespace std;

int a[100][100];

int main()

{int m,n,i,j;

cin>>n>>m;

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

cin>>a[i][j];

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

a[i][j]=max(max(a[i][j]+a[i][j-1],a[i][j]+a[i-1][j]),a[i][j]+a[i-1][j-1]);

cout<<a[n][m]<<endl;

return 0;

}

D. Гарні числа

Школа №1331 в Ужляндії відома дуже високим рівнем знань своїх учнів з математики, тому що більшість учнів відвідують факультативні заняття відомого вчителя Антона Андрійовича.

Сьогодні Антон Андрійович розказав своїм учням про числа, які, на його думку, можуть володіти рядом цікавих властивостей. Він назвав такі числа гарними. Число називається гарним, якщо не існує такого цілого числа, більшого одиниці, на квадрат якого воно б ділилося без залишку. Наприклад, число 12 не є гарним, тому що воно ділиться на 4, тобто на квадрат числа 2. Числа 13 і 14 є гарними числами.

Учні Антона Андрійовича дуже гарні в усному рахунку, тому в першому завданні необхідно було визначити: чи є деяке число гарним.

Однак, Марися, краща його учениця, швидко впоралась з цим завданням. Щоб якось її зайняти, вчитель написав на дошці N чисел і дав їй нове завдання : визначити, чи є добуток цих чисел гарним числом. Дуже скоро Марися отримала відповідь, однак вона хоче перевірити себе. Тому вона просить Вас написати програму, яка перевіряє: чи є добуток чисел гарним числом, а якщо ні, то їй потрібно знати яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток цих чисел.

Формат вхідних даних:Перший рядок вхідного файлу містить число N (1 ≤ N ≤ 100) - кількість чисел, які вчитель написав на дошці для Марисі. Другий рядок містить N натуральних чисел - самі числа. Кожне з чисел не перевершує 1018.

Формат вихідних даних:Якщо число є гарним, виведіть єдиний рядок, що складається з слова Beautiful. Інакше, виведіть яке-небудь число, відмінне від одиниці, на квадрат якого ділиться добуток N чисел.

Пояснення до прикладів:

Перший приклад: 5*6*7 = 210. Не існує числа, більшого за одиницю, на квадрат якого 210 ділилось би без залишку, тому 210 - гарне число.

Другий приклад: 35*12 = 420. 420 ділиться на 4, тобто на квадрат числа 2. 

Оцінювання:

A1 * A2 * ... * AN ≤ 106 – неменше 20 балів

A1 * A2 * ... * AN ≤ 1012 – не менше 40 балів

Для усіх іAi ≤ 1012 – не менше 60 балів

Приклади вхідних та вихідних даних:

beautiful.in

beautiful.out

3

5 6 7

Beautiful

2

35 12

2

Гарні числа

                Розглянемо випадки, коли добуток N заданих чисел ( ) ділитиметься без залишку на квадрат цілого числа, що більше одиниці:

$11)       якщо  ( , НСД – найбільший спільний дільник двох чисел (Алгоритм Евкліда знаходження НСД)). Тобто  та  діляться на без залишку, тоді  ділитиметься на  без остачі. Отже,  є відповіддю на задачу.

$12)       якщо  - точний квадрат, тоді  – відповідь.

$13)       якщо , тоді  - відповідь на задачу.
Щоби знайти таке
, достатньо перебрати всі дільники числа  до кубічного кореня з цього числа ( ) і перевірити наступні умови:
a) якщо , то  – відповідь;
б) якщо
 - точний квадрат, то  - відповідь.

Якщо жодна з умов не виконується, потрібно вивести “Beautiful”.

#include<fstream>
#include<set>
using namespace std;
ifstream in("beautiful.in");
ofstream out("beautiful.out");
int n,i;
long long x,j;
set<long long > a,b,c;
int main()
{
        in>>n;
        for (i=1;i<=n;i++)
        {
                in>>x;
                for (j=2;j*j<=x;j++)
                {
                        if (x%j==0)
                        {
                                x=x/j;
                                b=c=a;
                                b.insert(j);
                                if (b==c)
                                {
                                        out<<j<<endl;
                                        return 0;
                                }
                                a.insert(j);
                                if (x%j==0)
                                {
                                        out<<j<<endl;
                                       return 0;
                                }
                        }
                }
                if (x!=1)
                {
                j=x;
                if (x%j==0)
                        {
                                b=c=a;
                                b.insert(j);
                                if (b==c)
                                {
                                        out<<j<<endl;
                                        return 0;
                                }
                                a.insert(j);
                                if ((x/j)%j==0)
                                {
                                        out<<j<<endl;
                                      return 0;
                                }
                        }
                }
        }
        out<<"Beautiful"<<endl;
}

E. Вправи Степана

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

Придумати вправи для тренувань виявилося непросто, тому Степан вирішив пошукати ідеї в Інтернеті. Він знайшов сайт, на якому пропонувалася кілька серій тренувальних вправ. Кожна серія тренувань за планом займає N днів. У кожен з цих N днів пропонується робити одну «вправу дня», а також до нього додаються рекомендації щодо виконання у вигляді "Ai - Bi". Це позначає, що для підвищення рівня сили потрібно виконувати вправу від Ai до Bi раз. Якщо виконувати вправу менш, ніж Ai, або більш, ніж Bi раз, то це принесе скоріш за шкоду, ніж користь. Степан не хоче завдавати собі шкоди, тому буде робити від Ai до Bi раз, або зовсім не робити цю вправу.

Почитавши всі описи вправ, Степан зрозумів, що цей курс не розрахований на новачків, але вирішив не здаватися і адаптувати курс вправ під себе. Він знає, що при вивченні i-ї вправи йому доведеться втратити Ki рівнів сили, зате за виконання вправи X раз його рівень сили зросте на Fi*X. Степан не може вивчити і виконати вправу, якщо його поточний рівень сили менший за Ki. У дні, коли Степану не вистачає сил або часу тренуватись, він може пропускати тренування, і рівень його сили залишається без зміни. Знаючи свої можливості, Степан розуміє, що якщо в якийсь день він виконає вправу більш T разів, то наступні D днів він буде занадто втомленим, щоб займатися.

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

Степан хоче отримати від занять максимум користі, тому він планує витратити на них N днів! Для кожної серії тренувань допоможіть йому визначити максимальної рівень сили, який він зможе досягти в кінці тренувань. До початку тренувань рівень сили Афанасія дорівнює нулю.

Формат вхідних даних:Перший рядок вхідного файлу містить єдине ціле число N (1 ≤ N ≤ 105) - кількість днів тренувань.

Другий рядок містить два цілих числа T, D (1 ≤ T ≤ 106, 1 ≤ D ≤ 105), якщо в якийсь день Степан виконає вправу більш T разів, то йому доведеться відпочивати D наступних днів.
Наступні N рядків описують вправи, i+2-ий рядок містить опис вправи в день i. Кожна вправа описується числами Ai, Bi, Ki, Fi, (0 ≤ Ki ≤ 109, 1 ≤ Ai ≤ Bi ≤ 106, 1 ≤ Fi ≤ 106), розділеними одиночними пробілами, - де Ai, Bi відповідно рекомендований мінімум і максимум кількості разів виконання вправи, Ki-кількість втрачаються рівнів сили при вивченні вправи, Fi- кількість рівнів сили, одержуваних за кожен раз виконання вправи.

Формат вихідних даних:Перший рядок вихідного файлу має містити одне ціле число S - максимальний рівень сили, який Степан може досягти до кінця тренувань.
Наступний рядок повинен містити N цілих чисел Xi - кількість разів виконання вправи в день і, якщо в і-ий день він відпочивав, то виведіть 0.

Пояснення до прикладів:

Щоб досягти максимального рівня сили, треба в перший день виконувати вправу 4 рази, щоб не довелося пропускати наступний день. У другий день Афанасій зможе збільшити свій рівень ще на 790 (втрачає 10 рівнів при вивченні та виконує вправу 8 разів), але тоді він не зможе займатися 1 день (третій день).

У четвертий день він збільшує свій рівень на 48, так як Степан виконав вправу більше 4 разів, він змушений пропустити п'ятий.

Приклади вхідних та вихідних даних:

exercises.in

exercises.out

5

4 1

3 5 0 10

6 8 10 100

2 8 10 15

5 6 0 8

2 2 1 7

878

4 8 0 6 0

Вправи Степана

                За умовою задачі є N днів, в кожен з яких можна виконувати або не виконувати задану вправу. Вправу можна виконувати від  до  разів, та якщо рівень сили перед її виконанням не менше . Якщо виконати вправу  разів, то рівень сили зросте на , при цьому якщо , то наступні D днів потрібно буде відпочивати.

Для розв’язання даної задачі скористаємося методом динамічного програмування. Потрібно помітити, що для оптимального накопичення сили, вправу потрібно виконувати або , або , або  разів, інша кількість не покращить результат. Зберігатимемо динаміку  - максимальний рівень сили, якого можна досягти в день . Отже матимемо наступні переходи:

$11)       , тобто і-го дня вправа не виконується;

$12)       ( , ), якщо і-го дня Степан виконає вправу  разів, при чому ;

$13)       ( , ), якщо і-го дня Степан виконає вправу  разів, при чому ;

$14)       ( , ), якщо і-го дня Степан виконає вправу  разів, при чому ;

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

A. "Все, Степан! Ти мене дістав!"

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок "три - чотири" хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час t1, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робе те ж саме за час t2.

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

Визначте, скільки часу хлопці можуть насолоджуватись надуванням бульбашок, не замічені викладачем.

Наприклад, якщо t1 = 2, t2 = 3, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу t = 0 до моменту часу t = 2, потім бульбашка лопається, і він надуває бульбашку заново - з моменту часу t = 2 до моменту часу t = 4, а потім ще раз - з моменту часу t = 4 до t = 6

Товариш Степана надуває бульбашку з t = 0 до t = 3 і ще раз з t = 3 до t = 6.

В момент часу t = 6 бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: "Все, Степан! Ти мене дістав!".

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа t1, t2 (1 ≤ t1, t2 ≤ 109).

Формат вихідних даних: Вихідний файл повинен містити одне ціле число - час, протягом якого Степан з товаришем можуть насолоджуватись надуванням бульбашок.

Приклад вхідних та вихідних даних:

bubble.in

bubble.out

2 3

6

1 16

16

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{long long  a, b, a1, b1, t;

cin>>a>>b;

a1=a; b1=b;

while(b!=0)

{t=a%b;

a=b;

b=t;

}

long long nsd=a;

long long nsk=a1*b1/nsd;

cout<<nsk<<endl;

return 0;

}

#include<fstream>
using namespace std;
ifstream in("bubble.in");
ofstream out("bubble.out");
int gcd(int a,int b)
{
        while (b)
        {
                a%=b;
                swap(a,b);
        }
        return a;
}
long long a,b;
int main()
{
        in>>a>>b;
        out<<a/gcd(a,b)*b<<endl;

B. Степан - бізнесмен

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп'ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

Степан дізнався, що кожен продавець продає один комп'ютер, і кожен покупець готовий купити рівно один комп'ютер. Всього на ринку торгують N продавців, вартість комп'ютера у i-го з них дорівнює Ai Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе M потенційних покупців, кожен з яких хоче купити комп'ютер за Bi монет. При цьому сам Степан може купити і продати будь-яку кількість комп'ютерів.

Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас - кращому програмісту Ужляндії.

Формат вхідних даних:Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа N, M (1 ≤ N, M ≤ 105) - кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить N цілих чисел Ai (0 ≤ Ai ≤ 109) - вартості, за якими продавці готові продавати комп'ютери.
Третій рядок містить M цілих чисел Bi (0 ≤ Bi ≤ 109) - суми, які потенційні покупці готові віддати при покупці комп'ютера.

Формат вихідних даних:Перший рядок вихідного файлу має містити одне ціле число S - розмір максимальної вигоди в монетах, яку може отримати Степан.

Пояснення до прикладів:

У першому прикладі Степан купує комп'ютери у 1-го і 2-го продавців і продає їх будь-яким двом покупцям.
У другому прикладі Степану найбільш вигідно купити комп'ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям. 

Оцінювання:

N + M ≤ 20, для усіхі: Ai, Bj≤ 1000– не менше 40 балів

N + M ≤ 2000, для усіхі: Ai, Bj≤ 1000– не менше 50 балів

N + M ≤ 2000– не менше 75 балів

Приклад вхідних та вихідних даних:

businessman.in

businessman.out

2 3

1 1

3 3 3

4

6 5

5 10 8 4 7 2

3 1 11 18 9

27

#include<vector>
#include<algorithm>
using namespace std;
ifstream in("businessman.in");
ofstream out("businessman.out");
vector<long long> a,b;
long long n,m,ans,x;
int main()
{
        in>>n>>m;
        for (int i=0;i<n;i++)
        {
                in>>x;
                a.push_back(x);
        }
        for (int i=0;i<m;i++)
        {
                in>>x;
                b.push_back(x);
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        for (int i=0;i<min(n,m);i++)
        {
                long long temp=b[m-(i+1)]-a[i];
                if (temp>0) ans+=temp; else break;
        }
        out<<ans<<endl;
}

C. Transit

КраїнаУжляндіямаєвигіднегеографічнерозташуванняїїтериторіязнаходитьсянаперетиніважливихторгівельнихшляхів. Однимізтакихєторгівельнийшлях, якимсусіднябратськадержавадоставляєсвоїунікальніобігрівачідоіншихкраїн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі N днів. Згідно з новим договором має обратися певне число m – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує Ai обігрівачів, буде відвантажено рівно Ai-m одиниць іноземної продукції (звичайно, якщо Ai > m, інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за N днів обігрівачів повинна бути не менша K, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із N днів (ця інформація надається за умовами контракту). Знайдіть максимальне число m, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних:В першому рядку записано два числа N, K (1 ≤ N ≤ 106, 1 ≤ K ≤ 2*109). В наступному рядку задано N чисел – кількість обігрівачів у потязі в кожен з N днів, що не перевищує 109.

Формат вихідних даних:В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу:

Всього територією Ужляндії пройде 4 потяги з 11, 6, 1 та 8 обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше 7 обігрівачів. Очевидно, що максимальне можливе m, яке задовольнить цю умову, буде рівне 6, тоді з потягів буде відвантажено відповідно 5, 0, 0, 2 обігрівачів, що в сумі дорівнює 7 і задовольняє умову.

Оцінювання:

N ≤ 300 – не менше 20 балів

N ≤10000 – не менше 40 балів

Приклад вхідних та вихідних даних:

transit.in

transit.out

4 7

11 6 1 8

6

Transit

                Для розв’язання задачі достатньо зрозуміти, якщо при якомусь  загальна сума відвантажених обігрівачів не менше заданого , то і при будь-якому  ця сума також буде не менше . Тому застосуємо алгоритм бінарного пошуку по  (Бінарний пошук - http://informatics.mccme.ru/file.php/3/binary-search.pdf).

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

#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream in("transit.in");
ofstream out("transit.out");
vector<long long> a;
long long n,k,ans,x,j;
int main()
{        in>>n>>k;
        for (int i=0;i<n;i++)
        {
                in>>x;
                a.push_back(x);
        }
        sort(a.begin(),a.end());
        x=0;
        for (int i=n-1;i>=0;i--)
        {
                j++;
                x+=a[i];
                ans=max(ans,   (  (x-k)/j   )  );
        }
        out<<ans<<endl;
}

D. Дорожня система Ужляндії

Велика і прекрасна країна Ужляндія! Вона складається з N міст, пронумерованих від 1 до N, і M доріг між ними. Кожна дорога пов'язує між собою два різних міста та забезпечує пересування між ними. Дорожня система в Ужляндії вельми специфічна. Всі дороги мають двосторонній рух, і між кожною парою міст проходить не більше однієї дороги.

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

Скінчену послідовність номерів міст C1,..., CK(K ≥ 2)будемо називатишляхом, якщо для будь-якої сусідньої пари елементів послідовність Ci, Ci+1(Ci Ci+1, для 1 ≤ i < K)існує дорога між містами з номерами Ci Ci+1. Якщо C1= CK, то такий шлях будемо називати замкнутим. Довжину шляху C1, ..., CKбудемо вважати рівною довжині послідовності, тобто рівній K. Отже, правилонепарностіговорить,що всі замкнуті шляхи в Ужляндії мають непарну довжину, тобто не існує замкнутого шляху парної довжини.


Дорожня мережа, зображена на рисунку №1, має властивість непарності, а дорожня система на рисунку №2 не володіє цією властивістю через наявність у ній замкнутого шляху парної довжини 4: 1 2 4 1.

Нещодавно Міністр транспорту Ужляндії вирішив, що існуюча дорожня система неефективна, і необхідно побудувати кілька нових доріг. Причому нова дорожня система, отримана зі старої додаванням деякого числа доріг, повинна мати властивість непарності. Всі нові дороги повинні зв'язувати між собою різні міста. Крім цього, в новій дорожній мережі між кожною парою міст має проходити не більше однієї дороги.

Для поліпшення ефективності дорожньої системи було виділено багато грошей, тому Міністр Ужляндії вирішив побудувати якомога більше нових доріг таким чином, щоб отримана дорожня система задовольняла описаним вище умовам. Але це завдання виявилося досить складним, і міністерство транспорту Ужляндії вирішило звернутися до Вас за консультацією.

Отже, вам дано опис існуючої дорожньої мережі. Вам необхідно знайти максимальне число доріг, яке можна додати до існуючої мережі, не порушуючи вищеописаних властивостей.

Формат вхідних даних: Перший рядок вхідного файлу містить цілі числа N (1 ≤ N ≤ 10 000)і M (0 ≤ M ≤ 100000). Наступні M рядків описують дороги Ужляндії. У кожному рядку знаходиться опис рівно однієї дороги. Кожна дорога описується двома цілими числами X і Y (1 ≤ X, Y ≤ N, X ≠ Y). Ці числа відповідають номерам міст, зв'язаних дорогою. Міста нумеруються послідовно цілими числами від 1 до N.

Гарантується, що задана дорожня система задовольняє властивості непарності, а також будь-які два міста з'язані не більш ніж однією дорогою .

Формат вихідних даних:Вихідний файл повинен містити одне ціле число - максимальну кількість доріг, яку можна додати в існуючу дорожню мережу.

Пояснення до прикладів:

Дорожня мережа з першого прикладу приведена на малюнку № 1. Задана дорожня мережа з другого прикладу представлена н​​малюнку №3, а її стан після додавання до неї нових доріг зображено на малюнку №4.

У другому прикладі можна добавити 5 нових доріг: 2 5, 1 4, 1 6, 3 4, 3 6. 

Оцінювання:

M = 0 – не менше 20 балів

N ≤ 10, M > 0 – не менше 20 балів

N ≤ 100, M > 0 – не менше 40 балів

N ≤ 1000, M > 0 – не менше 60 балів

Приклад вхідних та вихідних даних:

roads.in

roads.out

4 4

1 2

2 3

3 4

1 4

0

6 4

1 2

6 5

3 2

4 5

5

Дорожня система Ужляндії

                Дводольний граф містить цикли лише з парною кількість вершин, скористаємося цією властивістю для розв’язання задачі. Виходить потрібно додати в граф ребра так, щоби він залишився дводольним.

                Спочатку маємо граф, що складається з кількох компонентів зв’язності, кожна з яких є окремим дводольним графом. Порахуємо для кожної компоненти кількість вершин в першій та другій долях. Очевидно, що додавши ребро між вершинами з різних підмножин, якщо його ще не існує, властивість дводольності не порушиться, тому порахуємо кількість таких ребер і додамо це значення до відповіді.
                На наступному кроці за допомогою динамічного програмування будемо об’єднувати різні компоненти в один зв’язний граф так, щоби зберегти властивість дводольності. Зрозуміло, якщо на даному етапі маємо граф з
 вершинами у першій долі та  у другій, і треба об’єднати його з компонентою, в якій  вершин у першій долі та  у другій, то можна отримати граф з  вершин у першій долі та  у другій, тоді кількість ребер, що можна додати, буде рівне . Або ж навпаки, вершин у першій долі та  у другій, тоді кількість ребер, що можна додати, буде рівне . Отже, рахуватимемо динаміку  - максимальна кількість доданих ребер, якщо в першій долі графа є  вершин. Тоді матимемо наступні переходи:

$11)       , де  – загальна кількість вершин у графі, який об’єднуємо з i-ою компонентою;

$12)       ;

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

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

E. Відео-кафе Ужляндії

Як відомо, чемпіонат світу з хокею в 2014 році пройде в Ужляндії. Для успішного проведення заходу приймаючій стороні належить виконати ряд вимог, що пред'являються Міжнародної хокейної федерацією. Хокейні матчі планується провести в м.Ужкачево та м.Ужковель (в Ужляндіїї усі міста починаються на Уж). Дані міста пов'язані між собою прямою автомагістраллю Ужкачево - Ужковель.

Голова Міжнародної хокейної федерації зазначив, що ні на одному з N кемпінгів, розташованих на автомагістралі Ужкачево - Ужковель немає відео-кафе. Відео-кафе - це елемент придорожнього сервісу, практично нічим не відрізняється від звичайного придорожнього кафе, але в якому створені умови для відео перегляду спортивних подій. Міжнародна хокейна федерація ухвалила, що на К з N існуючих кемпінгів необхідно побудувати відео-кафе. Міжнародна хокейна федерація також встановила такі вимоги до розташування кожного відео-кафе:

1. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе іпопереднімна автомагістралі відео-кафе (якщо таке є) повинно бути не меншеАкм і не більшеВкм.

2. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і наступним на автомагістралі відео-кафе (якщо таке є) повинно бути не менше А км і не більше В км.

3. Відстань від м.Ужкачево та м.Ужковель до найближчого відео-кафе не повинно бути менше А км і не більше В км.
 
Рисунок до прикладу №1: N=5, K=3, A=20, B=70.

Для кожного i-го побудованого відео-кафе введемо коефіцієнт Zi - відстань від даного відео-кафе до всіх інших. Міжнародна хокейна федерація встановила, що чим більша сума коефіцієнтів Zi, тим cвоєчасніше мандрівники зможуть отримувати інформацію про проведення хокейних матчів.

Ваше завдання визначити максимальну суму Zi, яка може бути досягнута шляхом зведення K відео-кафе, що задовольняють всім вимогам Міжнародної хокейної федерації. Відомо що, кожен кемпінг може містити на своїй території не більше одного відео-кафе. Вірне і зворотнє - відео-кафе може розташовуватися тільки на території кемпінгу.

Формат вхідних даних:Перший рядок вхідного файлу містить два цілих числа - N, K (1 ≤ K ≤ N ≤ 1000) відповідно.

Другий рядок вхідного файлу містить два цілих числа A, B (1 ≤ A < B ≤ 109).
Третій рядок вхідного файлу містить одне ціле число S (1 ≤ S ≤ 109) - відстань між м.Ужкачево та м.Ужковель.
Четвертий рядок вхідного файлу містить N цілих чисел Ci (0 < Ci < S, Ci < Cj якщо i < j) - відстань i-го кемпінгу від м.Ужкачево.

Формат вихідних даних:Вихідний файл повинен містити одне ціле число - максимальну суму коефіцієнтів Zi побудови K відео-кафе. Рішення завжди існує.

Пояснення до прикладів:

У першому прикладі кемпінги {1, 2, 4} 

У другому прикладі кемпінги {2, 5, 8, 10}. 

Оцінювання:

K ≤ 2 – не менше 15 балів

NK ≤ 106 – не менше 30 балів

N ≤ 50 – не менше 45 балів

N ≤ 300 – не менше 60 балів

Приклад вхідних та вихідних даних:

video_cafe.in

video_cafe.out

5 3

20 70

195

30 70 90 135 170

420

10 4

10 28

100

10 19 23 32 47 51 62 74 82 89

474


Матеріали IІІетапуВсеукраїнськоїучнівськоїолімпіадизінформатики 2012-2013

http://www.e-olimp.com.ua/ua/problems/4281

http://www.e-olimp.com.ua/ua/problems/4282

http://www.e-olimp.com.ua/ua/problems/4283

http://www.e-olimp.com.ua/ua/problems/4284

http://www.e-olimp.com.ua/ua/problems/4285

http://www.e-olimp.com.ua/ua/problems/4286

http://www.e-olimp.com.ua/ua/problems/4287

http://www.e-olimp.com.ua/ua/problems/4288

http://www.e-olimp.com.ua/ua/problems/4289

http://www.e-olimp.com.ua/ua/problems/4250

Завдання 1 туру ІІІ (обласного) етапу Всеукраїнської олімпіади з інформатики

А  - Неуважність

Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із самих престижних ІТ компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, все виконує у останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав не звернувши уваги, що випадково натиснув клавішу caps lock. Таким чином великі букви були набрані маленькими, а маленькі великими. Інші символи він набрав вірно. Степан настільки стомився, що немає сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить, напишіть програму, яка виправляє неуважно набраний текст.

Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.

Формат вихідних даних: вихідний файл має містити виправлений текст.

Приклади

Вхідні дані розміщені у файліtext.in

Результат роботи знаходиться у файліtext.out

sCHOOL
School

Var S: ansiString;

    i: LongInt;

  begin

    Assign(Input,'text.in');

    Reset(Input);

    Assign(Output,'text.out');

    Rewrite(Output);

    ReadLn(S);

    For i:=1 to LengTh(s) do

       If s[i] in ['A'..'Z'] then s[i]:=CHR(ORD(s[i])+32)

                             else if s[i] in ['a'..'z'] then s[i]:=CHR(ORD(s[i])-32);

    WriteLn(S);

    Close(Input);

    Close(Output)

  End.

B - День святого Валентина

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали. Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є N однокольорових (що поробиш – бідні студенти) кульок, діаметр i-ї кульки (1 ≤ i ≤ N) дорівнює Di міліметрів. Згідно новим вимогам профкому, залу необхідно прикрасити не менше ніж K кульками. Оскільки профоргу університету не подобається свято закоханих, то вона ввела своє поняття – так званий показник некрасивості – рівний максимально можливому числу Di – Dj при 1 ≤ i, j ≤ M, де M – кількість кульок для зали, а Di – їх діаметр. Допоможіть Степану із N іграшок вибрати М (M ≥ K) так, щоб для вибраних M кульок показник некрасивості був мінімальним.

Формат вхідних даних: перший рядок вхідного файлу містить два натуральних числа N (2 ≤ N ≤ 100 000) і K (2 ≤ K ≤ N) відповідно. Другий рядок містить N цілих чисел Di (1 ≤ Di ≤ 109) – діаметр i-ї кульки.

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

Пояснення: Приклад 1 - Існує кілька різних варіантів вибору. Степан може вибрати, наприклад, 6 кульок: 3, 5, 6, 4, 7 і 8
Приклад 2- Степан вибере 4 кульки: 1, 5, 3 і 6.

Приклади

Вхідні дані розміщені у файліholy.in

Результат роботи знаходиться у файліholy.out

8 5
10 20 10 20 10 10 20 20
10
6 4
21 12 17 28 16 21
5

Var a: array[1..100000] of LongInt;

    i, j, n, k, min, temp: LongInt;

        procedure sort(l,r: longint);

      var

         i,j,x,y: longint;

      begin

         i:=l;

         j:=r;

         x:=a[(l+r) div 2];

         repeat

           while a[i]<x do

            inc(i);

           while x<a[j] do

            dec(j);

           if not(i>j) then

             begin

                y:=a[i];

                a[i]:=a[j];

                a[j]:=y;

                inc(i);

                j:=j-1;

             end;

         until i>j;

         if l<j then

           sort(l,j);

         if i<r then

           sort(i,r);

      end;

  Begin

    Assign(Input,'holy.in');

    Reset(Input);

    Assign(Output,'holy.out');

    Rewrite(Output);

    Read(n,k);

    For i:=1 to n do

       Read(A[i]);

    Sort(1,n);

    min:=maxlongInt;

    for i:=1 to n-k+1 do

     if A[i+k-1]-A[i]<min then min:=A[i+k-1]-A[i];

    WriteLn(min);

    Close(Input);

    Close(Output)

  End.

C - Степан і Пари

Останнім часом Степан дуже цікавиться парами чисел, а крім пар чисел його цікавить найбільший спільний дільник пари чисел, позначимо його як НСД(x, y). Зараз у Степана є ціле число n і його цікавить така інформація: скільки існує пар цілих чисел (i,j), таких що 1 ≤ i, j ≤ n і виконується рівність i = НСД(i, j). Допоможіть йому у вирішенні нелегкої задачі.

Формат вхідних даних: у першому рядку дано ціле число n (1 ≤ n ≤ 106).

Формат вихідних даних: єдиний рядок має містити відповідь на задачу.

Зауваження: У першому прикладі підходящою парою є пара (1, 1), так як НСД(1, 1) = 1.
У другому прикладі підходять 8 пар чисел: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Приклади

Вхідні дані розміщені у файліpair.in

Результат роботи знаходиться у файліpair.out

1
1
4
8
10
27

 

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <algorithm>

#include <map>

#include <vector>

#include <cstdio>

#include <cmath>

using namespace std;

int n,i,ans,j;

int main()

{

        freopen("pair.in", "r", stdin);

        freopen("pair.out", "w", stdout);

    cin >> n;

    for (i=1;i<=n;i++)

        for (j=1;j*j<=i;j++)

        {

            if (i%j == 0)

            {

                    ans++;

                    if (j*j!=i) ans++;

            }

        }

    cout << ans << endl;

    return 0;

}

    for (i=1;i<=n;i++)

      k=k+n/ i;

 

 

D - Спадок Степана

Степан отримав у спадок від дідуся стоянку з N місць, пронумерованих від 1 до N. Стоянка розбита на дві частини. Перші M місць знаходяться з лівого боку, а інші N - M місць з правого. Кожного дня N жителів цього району паркують свої автомобілі на стоянці Степана. Відомо, що перший житель приходить раніше усіх, потім другий, і так далі, тобто k-й приходить k-м. Також для кожного жителя i відомо, скільки він буде платити, якщо його машину поставлять на j-е місце. Степан придбав розподільник місць, який кожному автомобілю, що приїздить вказує, на який бік паркуватись, після чого автомобіль паркується на мінімальне за номером вільне місце відповідного боку. При цьому Степан вирішив зекономити і не придбав програмне забезпечення для розподільника, тому він працює не оптимально. Степан просить Вас написати програму для цього розподільника, яка максимізує доходи Степана.

Формат вхідних даних: у першому рядку записані два цілих числа N (2 ≤ N ≤ 1000) і M (1 ≤ M < N) – загальна кількість місць на стоянці і кількість місць з лівого боку відповідно. У кожному із наступних N рядків записано по N цілих додатних чисел. j-е число i-го рядка означає, скільки буде платити i-ий житель за місце з номером j на цій стоянці. Кожне з цих чисел не перевищує 106.

Формат вихідних даних: єдиний рядок має містити одне число – максимальний прибуток стоянки.

Зауваження: Не менш чим у 50% тестів N ≤ 30.

Приклади

 

Вхідні дані розміщені у файліlegacy.in

Результат роботи знаходиться у файліlegacy.out

2 1
3 2
6 4
8
4 1
4 3 1 1
3 1 1 1
1 1 4 1
1 1 1 2
12

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <set>

#include <map>

#include <vector>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <stack>

#include <algorithm>

#include <sstream>

using namespace std;

#define f first

#define s second

#define mp make_pair

#define sz(a) int((a).size())

#define pb push_back

#define all(c) (c).begin(),(c).end()

#define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)

#ifdef WIN32

        #define I64d "%I64d"

#else

        #define I64d "%lld"

#endif

typedef pair <int, int> pi;

int n, m, pay[2222][2222];

int dp[2222][2222];

int calc(int i, int j) {

        if (i + j == n)

                return 0;

        int &res = dp[i][j];

        if (res != -1) return res;

        res = 0;

        int num = i + j;

        if (i < m)

                res = max(res, calc(i + 1, j) + pay[num][i]);

        if (j < n - m)

                res = max(res, calc(i, j + 1) + pay[num][m + j]);

        return res;

}

int main() {

        freopen("legacy.in", "r", stdin);

        freopen("legacy.out", "w", stdout);

        scanf("%d%d", &n, &m);

        for (int i = 0; i < n; ++i)

                for (int j = 0; j < n; ++j)

                        scanf("%d", &pay[i][j]);

        memset(dp, -1, sizeof(dp));

        int res = calc(0, 0);

        printf("%d\n", res);

        return 0;

}

E- Конфетна проблема Степана

Степан закохався і вирішив привернути увагу дівчини великою коробкою цукерок. За порадою друзів він поїхав на саму відому кондитерську фабрику ShenRo і дізнався, що великі коробки цукерок мають трикутну форму. Цукерки в цих коробках розташовуються у кілька рядів. У першому ряду знаходиться одна цукерка, у другому – дві, у третьому – три цукерки і так далі. На фабриці випускаються коробки цукерок з любим числом рядів у межах від 1 до N. Степан хоче купити одну із таких коробок. Але є одна проблема: його дівчина засмутиться, якщо кількість цукерок у коробці не буде ділитись націло на M, тому що у цьому випадку комусь із друзів дівчини дістанеться більше цукерок, чим іншим, або ж якісь цукерки залишаться лишніми. Тому Степан вирішив, що число цукерок у коробці має обов’язково ділитись націло на M.

При виборі подарунка Степан зіткнувся з проблемою придбання відповідної коробки цукерок, оскільки можливих варіантів вибору коробки цукерок виявилося надто багато. Не довго думаючи, Степан вирішив звернутись за допомогою до учасників олімпіади.

Вам необхідно по заданих числах N і M знайти число способів вибору коробки цукерок із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів цукерок.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N - максимальна кількість рядів цукерок у коробці і M – кількість друзів дівчини Степана (1 ≤ N, M ≤ 2*109) відповідно.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість різних способів вибору коробки цукерок.

Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 105– не менше 55 балів.

Приклади

 

Вхідні дані розміщені у файліproblem.in

Результат роботи знаходиться у файліproblem.out

20 10
4
53 199
0
5705 145
157

var i,j,cnt:longint;

    ans,s,q,x,n,m:int64;

    ok:boolean;

    a,b:array[0..100001]of longint;

  Begin

    Assign(input,'problem.in');

    Reset(input);

    Assign(output,'problem.out');

    Rewrite(output);

    Read(n,m);

    cnt:=0;

    a[0]:=0;

    ans:=0;

    for i:=1 to n do

      begin

        x:=i;

        s:=(x*(x+1))div 2;

        ok:=false;

        if s mod m=0 then begin

                            cnt:=cnt+1;

                            a[cnt]:=i-b[cnt-1];

                            b[cnt]:=i;

                            ans:=ans+1;

                            if cnt mod 2=0 then begin

                                                  ok:=true;

                                                  for j:=1 to cnt div 2 do

                                                    if a[j]<>a[cnt div 2+j] then begin

                                                                                   ok:=false;

                                                                                   break;

                                                                                 end;

                                                  if ok then break;

                                                end;

                            if ok then break;

                          end;

        if ok then break;

      end;

    q:=i;

    if ok then begin

    ans:=(n div q)*cnt;

    i:=1;

    q:=n div q*q+a[1];

    While q<=n do

      begin

        ans:=ans+1;

        i:=i+1;

        q:=q+a[i];

      end;

      end;

    Writeln(ans);

    Close(input);

    Close(output);

  End.

Завдання 2 туру ІІІ (обласного) етапу Всеукраїнської олімпіади з інформатики

А - Арифметика

Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 101000), записане Мишком.

Формат вихідних даних: вихідний файл має містити одне число – кількість різних цифр у числі.

Приклади

Вхідні дані розміщені у файліcount.in

Результат роботи знаходиться у файліcount.out

1233
3

#include "string"

#include "fstream"

using namespace std;

int main()

{ifstream cin ("count.in");

ofstream cout ("count.out");

string a;

                int h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,k,i;

                h0=0;

                h1=0;

                h2=0;

                h3=0;

                h4=0;

                h5=0;

                h6=0;

                h7=0;

                h8=0;

                h9=0;

                h0=0;

                k=0;

                getline(cin,a);

                for(i=0;i<a.length();i++)

                {

if(a[i]=='0')h0++;else

if(a[i]=='1')h1++;else

if(a[i]=='2')h2++;else

if(a[i]=='3')h3++;else

if(a[i]=='4')h4++;else

if(a[i]=='5')h5++;else

if(a[i]=='6')h6++;else

if(a[i]=='7')h7++;else

if(a[i]=='8')h8++;else

if(a[i]=='9')h9++;

                }

                if(h0>0)k++;

                if(h1>0)k++;

                if(h2>0)k++;

                if(h3>0)k++;

                if(h4>0)k++;

                if(h5>0)k++;

                if(h6>0)k++;

                if(h7>0)k++;

                if(h8>0)k++;

                if(h9>0)k++;

                cout<<k<<"\n";

                return 0;}

char a[1000];

int b[10];

cin>>a;

for(i=0;i<strlen(a);i++)

b[a[i]-48]=1;

s=0;

for(i=0;i<=9;i++)

s=s+b[i]

#include "fstream"

using namespace std;

ifstream cin ("count.in");

ofstream cout ("count.out");

int a[10];

int s;

int main()

{

                char c;

while (!cin.eof())

{cin>>c;

a[c-48]=1;

}

for(int i=0;i<=9;i++)

s=s+a[i];

cout<<s<<endl;

return 0;

}

B- Степан і сірники

Степан дуже полюбляє гратись із сірниками. Але він не балується ними, не розпалює вогонь, а розв'язує різні головоломки. Наприклад, він уміє прирівнювати число дев'ять до числа одинадцять, переклавши лише один сірник. Нещодавно батьки Степана подарували йому декілька наборів, кожен з яких складається з дванадцяти сірників. Хлопчик почав збирати з них різні геометричні фігури. Він вже зібрав багато різних фігур, але тепер йому стало цікаво: з яких наборів можливо склеїти каркас паралелепіпеда за допомогою дванадцяти сірників з набору та клею? Ламати сірники не можна і жоден із сірників не повинен виступати за каркас.

Ваше завдання полягає в тому, щоб за відомими довжинами сірників для кожного набору перевірити, чи можна з них склеїти каркас паралелепіпеда.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 100), яке представляє кількість наборів. Далі йдуть N рядків, кожен з яких містить у собі опис набору сірників - дванадцять цілих додатніх чисел не перевищують 109.

Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору сірників виведіть “yes”, якщо з нього можливо склеїти каркас паралелепіпеда, і “no” в іншому випадку.

Приклади

Вхідні дані розміщені у файліmatches.in

Результат роботи знаходиться у файліmatches.out

2
1 1 1 1 2 2 2 2 3 3 3 3
1 1 1 1 2 2 2 2 3 3 3 4
yes
no

C - Задача від Степана

Перебираючи свої дитячі іграшки, Степан знайшов набір із N різних прямокутників і згадав задачу, яку йому колись задав старенький вчитель математики. Назвемо прямокутник маленьким, якщо знайдеться інший прямокутник з даного набору, яким можна повністю накрити цей прямокутник. При цьому прямокутники можна повертати, але відповідні сторони мають бути паралельними.

Наприклад, прямокутник зі сторонами 1 і 10 можна повністю накрити прямокутником 10 і 3, але не можна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити не можна, відповідно в наборі із цих трьох прямокутників тільки один маленький. Напишіть програму, яка вирішить згадану Степаном задачу – визначить кількість маленьких прямокутників у даному наборі.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000). У кожному з наступних N рядків міститься два цілих додатних числа – розміри одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників немає однакових.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість маленьких прямокутників у даному наборі.

Приклади

Вхідні дані розміщені у файліtask.in

Результат роботи знаходиться у файліtask.out

3
1 10
9 9
10 3
1
4
1 7
2 6
3 5
4 4
0

D - Штрафи

Степан нещодавно купив автомобіль, але водійські права ще не отримав. В зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить в ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що ДАІ стоять не на всіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (в країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 карбованців. Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.

Формат вхідних даних: Перший рядок містить два числа N, M (2 ≤ N ≤ 105, 1 ≤ M ≤ 105). Інші М рядків містять два числа Xi і Yi, які описують дорогу між містом Xi і містом Yi. В останньому рядку написано число A (2 ≤ A ≤ N) – місто в якому живе Степан.

Формат вихідних даних: Виведіть в одному рядку єдине число – кількість карбованців які Степан має мати при собі.

Приклади

Вхідні дані розміщені у файліpenalty.in

Результат роботи знаходиться у файліpenalty.out

6 7
1 2 
2 3
3 1
3 4
4 5
4 6
5 6
6
1000

E - Ремонт

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд все просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати малюнки на сусідніх полосах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином. Кожну полосу шпалер можна описати її частиною – прямокутником довжиною N і шириною M (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось N рядків і М стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами ”.” і ”*” (крапка і зірочка), по одному символу в кожній клітинці.

Вам дано опис двох полос шпалер. Допоможіть Степану, напишіть програму, яка визначатиме, на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі. Степан придбав такі шпалери, що гарантовано завжди можна це зробити.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N і M(1 ≤ N ≤ 20, 1 ≤ M ≤ 100000). Наступні N рядків містять по М символів кожна – опис першої полоси шпалер. Наступні N рядків містять по М символів кожна – опис другої полоси шпалер. Кожен рядок опису шпалер містить тільки символи ”.” і ”*”.

Формат вихідних даних: вихідний файл має містити одне число – на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі.

Приклади

Вхідні дані розміщені у файліrepair.in

Результат роботи знаходиться у файліrepair.out

2 5
.*.*.
*.*.*
*.*..
.*.**
1
1 5
***..
*..**
2
 
3. Готуємось до олімпіади з інформатики PDF Печать E-mail
Добавил(а) Administrator   
21.01.15 09:18

Готуємось до олімпіади з інформатики

$11.                   Сума арифметичної прогресії

int s=0;

for(int i=a1;i<=an;i=i+d)s=s+i;

.

int s=(a1+an)*n/2;

$12.                   Числа Фібоначі

int a1(1),a2(1);

for (int i=3;i<=n;i++)

{a3=a1+a1;

a1=a2;

a2=a3;

}

int a[100];

a[1]=1; a[2]=1;

for (int i=3;i<=n;i++)

a[i]=a[-1]+a[i-2];

#include "stdafx.h"

#include <iostream>

#include <math.h>

using namespace std;

 int main(){

  double n,f;

 cin>>n;

f=1/sqrt(5.0)*(pow((1+sqrt(5.0))/2.0,n)+pow((1-sqrt(5.0))/2.0,n));

cout.precision(0);

cout<<fixed<<f<<endl;

    return 0;

}

Exp(y*ln(x)

Power(x,y)

A:=strtoint(‘123’);

$13.                   Алгоритм Евкліда

#include "stdafx.h"

#include <iostream>

using namespace std;

 int main(){

int a,b,a1,b1,t;

 cin>>a>>b;

 a1=a;b1=b;

 while (b!=0)

 {t=a%b;

 a=b;

 b=t; }

 int nsd=a;

 int nsk=a1*b1/nsd;

cout<<nsd<<endl;

cout<<nsk<<endl;

    return 0;

}

$14.                   Прості числа (решето Ератосфена)

#include "iostream"

#include "math.h"

using namespace std;

int main()

{int n,p;

cin>>n;

for(int i=2;i<=n; i++)

{p=0;

for(int j=2;j<=int(sqrt(double (i)));j++)

if (i%j ==0)p=1;

if (p==0) cout<<i<<endl;

}

return 0;

}

#include "iostream"

#include "math.h"

using namespace std;

int a[10000];

int main()

{int n,p,i,j;

cin>>n;

for(i=1;i<=n; i++)a[i]=i;

a[1]=0;i=1;

while (i<=n/2)

{

while (a[i]==0)i++;

j=i+a[i];

while (j<=n)

{a[j]=0;

j=j+a[i];}

i++;

}

for(i=1;i<=n;i++)

if (a[i]!=0 ) cout<<a[i]<<" ";

}

$15.                   Зчитування та порівняння рядків та символів

 char a;

cin>>a;

if (a=='A') cout<<"ok"<<endl;else cout<<"no"<<endl;

#include string.h

char a[1000],b[1000];

cin.getline(a,sizeof(a));

cin.getline(b,sizeof(b));

if (strcmp(a,b)==0)cout<<”ok”<<endl;

{Менше нуля a менше b

Нульa  рівне b

Більше нуляa більше b

}

#include <fstream>

#include <string>

using namespace std;

int main(){

ifstream cin(“input.txt”);

ofstream cout(“output.txt”);

string s1, s2;

getline (cin, s1);

getline (cin, s2);

cout<<s1<<endl;

cout<<s2<<endl;

if(s1==s2)

        cout << "Ok..\n";

    return 0;

}

$16.                   Швидке сортування

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int main()

{int n,i;

cin>>n; vector<int> a(n);

for (i=0; i<n; i++)cin>>a[i];

sort(a.begin(),a.end());

for (i=0; i<n-1; i++)cout<<a[i]<<" ";

cout<<a[n-1]<<"\n";

       return 0;

}

$17.                   Повний перебір

#include <fstream>

#include <iostream>

#include <math.h>

#include <vector>

#include <algorithm>

#include <time.h>

using namespace std;

vector <int> a;

// ifstream cin("input.dat");

 //ofstream cout("output.ans");

   

void printper(int n);

int main()

{

    int n;

    cin >> n;

    for (int i=1;i<=n;i++){a.push_back(i);

    }

               

    printper(n);

               

                clock_t start = clock();

    while (next_permutation(a.begin(),a.end())){

     //  printper(n);

    };

                // час перебору

long double r=(clock() - start)*1. / CLOCKS_PER_SEC;

cout<<"times work = "<<r<<endl;

    return 0;

}

void printper(int n)

{

    for (int i=0;i<n-1;i++){

        cout << a[i] << " ";

    }

    cout << a[n-1] << endl;

}

$18.                   Векторний добуток

#include<fstream>

using namespace std;

ifstream cin("input.txt");

  • ofstream cout("output.txt");

int main()

{

        int i,n,m,k=0,x[10001],y[10001],a[10001],b[10001],v[10001];

        cin>>n>>m;

        for(i=1;i<=n;i++) cin>>x[i]>>y[i];

        for(i=1;i<=n-1;i++)

        {

                a[i]=x[i+1]-x[i];

                b[i]=y[i+1]-y[i];

        }

        for(i=1;i<=n-2;i++){

                v[i]=a[i]*b[i+1]-a[i+1]*b[i];

                if(v[i]>0) k++;}

        cout<<k*m<<endl;

}

$19.                   Повний обхід дерева

#include "iostream"

using namespace std;

int c[100],n;

void p(int i,int v)

{c[i]=v;

if(i==n)

{for(int j=1;j<=n;j++)

cout<<c[j];cout<<endl;}

else{p(i+1,0);p(i+1,1);}}

int _tmain()

{cin>>n;

p(1,0);

p(1,1);

}

$110.               Рекурсивний пошук шляху в графі

#include "iostream"

using namespace std;

int a[100][100],c[100],n;

void p(int i, int v)

{c[i]=v;

if (v==n || i>n)

{for(int j=1;j<=n;j++)

cout<<c[j]<<" ";

cout<<endl;

}

else

for(int j=1;j<=n;j++)

if(a[v][j]>=1) p(i+1,j);

}

int main()

{

cin>>n;

for(int i=1;i<=n;i++)

for (int j=1;j<=n;j++)cin>>a[i][j];

p(1,1);

}

$111.               Побудова остового дерева

#include <iostream>

#include <math.h>

using namespace std;

int main()

{int n,int p=0;

int a[n][n];

int x[1000],y[1000],kol_ver[1000],v[1000];

int k,i,j,vi,vj,min,s;

int ver[1000][3];

int f;

for(i=0;i<n;i++)

for (j=0;j<n;j++)

cin>>a[i][j];

k=0; v[k]=p;s=0;

while (k<n-1) {

min=100000;

for (i=0;i<=k;i++)

for(j=0;j<n;j++)

if (a[v[i]][j]<min) {min=a[v[i]][j];vi=v[i];vj=j;}

f=1;

for (i=0;i<=k;i++)if (vj==v[i])f=0;

if (f==1) {k=k+1;

ver[k][1]=vi;

ver[k][2]=vj;

v[k]=vj;

kol_ver[vj]=kol_ver[vj]+1;

kol_ver[vi]=kol_ver[vi]+1;

s=s+a[vi][vj];

}

a[vi][vj]=1e30;a[vj][vi]=1e30;

}

cout<<s<<endl;

for(i=1;i<n;i++) cout<<ver[i][1]<<' '<<ver[i][2]<<endl;

return 0;

}

$112.                Пошук мінімального шляху (Флойд)

  for (int k=0; k<n; ++k)

                for (int i=0; i<n; ++i)

                               for (int j=0; j<n; ++j)

                                               if (d[i][j]< d[i][k] + d[k][j])

                                                               d[i][j] = d[i][j]; else d[i][j]=d[i][k] + d[k][j];

 

 

ІІI етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2012-2013н.р

http://176.31.28.231/cgi-bin/new-client?contest_id=11  

ІІIетапВсеукраїнськоїучнівськоїолімпіадизінформатики(м.Луцьк) 2013-2014н.р

http://www.e-olimp.com.ua/problems/7234

http://www.e-olimp.com.ua/ua/problems/7235

http://www.e-olimp.com.ua/ua/problems/7236

http://www.e-olimp.com.ua/ua/problems/7237

http://www.e-olimp.com.ua/ua/problems/7238

http://www.e-olimp.com.ua/ua/problems/7239

http://www.e-olimp.com.ua/ua/problems/7240

http://www.e-olimp.com.ua/ua/problems/7241

http://www.e-olimp.com.ua/ua/problems/7242

http://www.e-olimp.com.ua/ua/problems/7243

 
Завдання IІ етапу Всеукраїнської учнівської олімпіади з інформатики 2014-2015 н.р. PDF Печать E-mail
Добавил(а) Administrator   
04.12.14 09:17

Завдання 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

 
Динамічне програмування PDF Печать E-mail
Добавил(а) Administrator   
12.11.14 09:15

Динамічне програмування . Купування квитків

Ім'я файлу програми:

Bilet.*

Ім'я вхідного файлу:

Bilet.dat

Ім'я вихідного файлу:

Bilet.dat

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

5 секунд

Максимальна оцінка за завдання:

100 балів

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

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

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків — Bi секунд, трьох квитків — Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

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

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

У вхідному файлі записано спочатку число N — кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

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

У вихідний файл виведіть одне число — мінімальний час в секундах, за яке могли бути обслужені всі покупці.

Приклади

Bilet.dat

Bilet.sol

5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

12

2

3 4 5

1 1 1

4

N=5

i

Ai

Bi

Ci

1

5

10

15

2

2

10

15

3

5

5

5

4

20

20

1

5

20

1

1

D[i]= min ( D[i-1]+Ai,  D[i-2]+ Bi-1,  D[i-3]+ Ci-2 )

D[1]

D[2]

D[3]

D[4]

D[5]

5

7

5

6

12 – відповідь завдання

d[0]= 0;

d[1]= а[1];

d[2]= Мінімальне(а[1]+a[2], b[1]);

Для i від 3 до n  пц

d[i]= Мінімальне(d[i-1]+ а[i],Мінімальне(d[i-2]+ b[i-1], d[i-3]+ с[i-2]));

d[0]= 0;

d[1]= а[1];

d[2]= min(а[1]+a[2], b[1]);

for(int i=3;i<=n;i++)

d[i]= min(d[i-1]+ а[i],min(d[i-2]+ b[i-1], d[i-3]+ с[i-2]));

#include<fstream>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{

int n,i,a[5000],b[5000],c[5000],d[5000];

in>>n;

for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];

d[0]= 0; d[1]= a[1]; d[2]= min(a[1]+a[2],b[1]);

for(i=3;i<=n;i++) d[i]=min(d[i-1]+a[i],min(d[i-2]+b[i-1],d[i-3]+c[i-2]));

cout<<d[n]<<endl;

}

 
Практикум з розв'язування задач PDF Печать E-mail
Добавил(а) Administrator   
22.10.14 02:00

Ремонт кораблів (DOCKS)

На судоремонтний завод для докового ремонту одночасно прийшло N кораблів. В док на ремонт може зайти тільки одне судно. Необхідний час стоянки в доці для кожного судна різний. Після ремонту судно одразу йде в рейс.

Скласти програму, що визначає порядок постановки кораблів у док, при якій сумарний час, протягом якого кораблі чекають своєї черги, мінімальний.

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

У першому рядку файлу міститься число N – кількість кораблів, що прийшли на ремонт (1£N£10000). В наступних N рядках – пари чисел – номер судна та через пропуск – час ремонту (натуральні числа, не більші 10000).

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

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

Між числами має бути по одному проміжку. Наприкінці рядка проміжок не ставте.

Приклад вхідних та вихідних даних:

DOCKS.DAT

DOCKS.RES

3

3 6

1 12

2 4

2 3 1

Працівники (STAFF)

(XVІІ Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: A або B. Кожна деталь має порядковий номер від 1 до N. До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.

Існують правила, за якими визначається, чи можна обробляти деталь на певному верстаті.

$11)      Якщо на поточний момент на верстаті B була оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.

$12)      У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Напишіть програму STAFF, яка за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.

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

Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2N≤28) – кількість деталей яку необхідно обробити.

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

Єдиний рядок вихідного файлу STAFF.RES має містити ціле число – максимальну можливу кількість працівників заводу.

Приклад вхідних та вихідних даних:

STAFF.DAT

STAFF.RES

4

2

Перший працівник вважає що на верстаті A необхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий  має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станку B – деталі 2 та 4. Інших варіантів послідовності обробки немає.

Затори на дорогах (JAMMING)

Автомобільні затори трапляються усюди, навіть у нашому невеличкому містечку. Дороги у нас мають дві смуги в одному напрямку, а автомобілі є лише двох типів габаритів: легкові (у пробці займають квадрат 1х1, якщо за 1 взяти ширину смуги) та вантажні (у пробці займають місце 2х1 вздовж смуги).

Водії дуже дисципліновані у тому плані, що вони не стають поперек смуги, не займають чужу площу, але й не залишають вільних місць.

Визначте, скільки існує різних за послідовністю типів машин (легкова - вантажна) заторів між мерією міста та моїм будинком, якщо вони на одній вулиці, а відстань між ними S.

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

Вхідний файл містить єдине число S (1£S£10000) – задана відстань.

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

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

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

JAMMING.DAT

JAMMING.RES

2

4

Приклад вхідних та вихідних даних:

Кубики (CUBES)

(XV Всеукраїнська олімпіада з інформатики, 2002 рік, Чернівці)

Тривимірна фігура складається з одиничних кубиків. За фігурою можна побудувати її фронтальну та праву проекції. Очевидно, що за цими двома проекціями не завжди можна відтворити фігуру.

Напишіть програму CUBES, що отримує на вхід фронтальну та праву проекції фігури та визначає мінімальну та максимальну кількість кубиків, яку можна було б використати для побудови фігури із заданими проекціями.

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

У першому рядку вхідного файлу CUBES.DAT знаходиться три числа N, M та К, що задають розміри проекцій (1N, M, K ≤100). Далі задаються дві проекції: спочатку фронтальна, а потім права. Проекція задається N рядками, кожний з яких складається з чисел 0 та 1, що розділені прогалиною. Для фронтальної проекції таких чисел буде M, а для правої — K. 0 означає вільну клітинку проекції, 1 — заповнену.

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

У єдиному рядку вихідного файлу CUBES.SOL повинно знаходитися два числа: мінімальна та максимальна кількість кубиків, які можна було б використати для побудови фігури із заданими проекціями.

Приклад вхідних та вихідних даних:

CUBES.DAT

CUBES.RES

2 2 3

1 0

1 1

0 0 1

1 1 1

4 7

Последнее обновление 30.03.15 09:16
 
Практикум з розв'язування задач PDF Печать E-mail
Добавил(а) Administrator   
15.10.14 09:09

1 тур - з 20.10 по 26.10.2014

точка входу для відправлення розв'язків http://176.31.28.231/cgi-bin/new-client?contest_id=15

Задача 1. Особливі числа (20 балів)

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

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

Ліміт часу: 1с.

Петрик любить створювати і досліджувати числові послідовності. Одного разу він досліджував послідовність 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011, .... і помітив, що деякі елементи цієї послідовності діляться на 3. Такі числа він назвав «особливими».

Допоможіть Петрику підрахувати, скільки елементів цієї послідовності серед перших n діляться на 3.

Вхідні дані.

Натуральне число n (1n4000000 ).

Вихідні дані.

Вивести одне знайдене число.

Приклад.

Приклад вхідних даних

Приклад вихідних даних

4

2

Задача 2. Суми в ромбі (100 балів)

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

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

Ліміт часу: 2с.

Вам задано таблицю N*M, у кожній клітинці якої написане деяке число. Ромбом з центром в клітинці (x0,y0) і розміром k будемо називати набір клітинок, координати (x,y) яких задовольняють наступну умову: |x-x0|+|y-y0|<k.

На малюнку в таблиці 5*6 зображено ромб з центром в клітинці (3,2) і розміром 2.

У заданій таблиці знайдіть ромб з найбільшою можливою сумою чисел.

Формат вхідного файлу.

Перший рядок вхідного файлу містить два цілих числа N і M(1N,M500). НаступніNрядків містять Mчисел. Числа в рядках розділені пробілами. Числа лежать в межах від -105 до 105.

Формат вихідного файлу.

Виведіть одне ціле число – суму чисел в знайденому ромбі.

Приклади

Input.txt

Output.txt

5 6

11-10111

121111

2221 11

1211 11

111-1011

10

 
Задачі з теми Графи PDF Печать E-mail
Добавил(а) Administrator   
15.10.14 09:06

№1. ЗАДАЧА «МІЖНАРОДНА КОНФЕРЕНЦІЯ»(100 БАЛІВ)

Вас найняли для того, щоб визначити місця дипломатів за столом обговорень міжнародної конференції. На конференцію запрошено по одному дипломату з N різних країн світу. Ко­жен дипломат знає від однієї до п'яти мов. Дип­ломати, які не знають спільної мови, не можуть розмовляти один з одним. До того ж, деякі краї­ни проголосили, що не будуть підтримувати дипломатичних стосунків з деякими іншими, тобто представники цих країн не будуть роз­мовляти один з одним. Ваше завдання полягає в розробці програми DIPLOMAT.pas/.c/.cpp, що визначає місця за столом для дипломатів таким чином, щоб кожен мав можливість розмовляти з обо­ма своїми сусідами, які сидять ліворуч та пра­воруч від нього.

Стіл, що використовується, — круглий і розрахований на N персон (N£20). Дипломат може спілкуватися з дипломатом, який сидить ліво­руч, однією мовою, а з дипломатом, що сидить праворуч, — іншою.

Технічні вимоги:

Вхідний файл: DIPLOMAT. DAT.

Вихідний файл: DIPLOMAT. SOL.

    Програма: diplomat.pas/.c/.cpp

Формат вхідних даних. У першому рядку текстового файла DIPLOMAT. DAT — число N. Далі — N рядків, по одному рядку на диплома­та. Кожен рядок — послідовність слів. Сусідні слова відокремлені пробілом. Кожне слово — це послідовність великих латинських літер. Перше слово — код країни — складається з трьох літер. Друге слово має довжину від 1 до 5 літер і являє собою перелік мов, якими може спілкуватися дипломат. Кожна мова позначена однією літерою. Далі — список з не більш ніж N трилітерних слів — кодів країн, з якими уряд дипломата підтримує дипломатичні стосунки.

Формат вихідних даних. До файла DIPLOMAT. SOL треба вивести список дипломатів у порядку розміщення за столом (по одному дипломату в рядку). Кожен рядок складається з трьох слів: перше — код мови, якою дипломат може спілкуватися з сусідом ліворуч, друге — код країни дипломата, третє — код мови для спілкування з сусідом праворуч. Мож­ливе існування кількох розв'язків. Вам по­трібно знайти один. Якщо розв'язку не існує, то ваша програма має видати таке повідомлен­ня: «NO  SOLUTION EXIST»

Приклад:

DIPLOMAT. DAT

DIPLOMAT. SOL

4

USA EC UCR CHN

CHN GC USA GBR

GBR EG UCR CHN

UCR E USA GBR

C USA E

E UCR E

E GBR G

G CHN C

2

USA ER CHN

CHN CP USA

NO SOLUTION EXIST

Подарунок (uoi2011)

У королівстві Олімпія знаходиться N міст та M двосторонніх доріг, кожна з яких з’єднує рівно два міста. Між двома містами може бути більше однієї дороги. Усі дороги постійно грабуються розбійниками. Останнім часом розбійникам набридло витрачати сили на пограбування і вони звернулися до могутнього і справедливого короля Олімпії з комерційною пропозицією. За цією пропозицією король повинен надіслати розбійникам подарунок, що складається з золотих та срібних монет. У відповідь на люб’язність короля розбійники припинять грабувати певні дороги. Для кожної з доріг встановлена мінімальна кількість золотих і мінімальна кількість срібних монет у подарунку, щоб її пограбування скінчились. Тобто, якщо у подарунку K золотих та L срібних монет, то припиняється пограбування усіх доріг, для яких необхідна кількість золотих монет менша або рівна K, а  кількість срібних монет менша або рівна L.

В скарбниці короля немає жодної золотої або срібної монети, але є Олімпійські Тугрики. Ціна однієї золотої монети в тугриках – G, а срібної – S. Король дуже хоче, щоб після відправлення подарунку розбійникам між кожною парою міст існував хоча б один безпечний шлях, який, можливо, проходить через інші міста.

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

Вхідні дані Перший рядок вхідного файлу gift.dat містить два цілих числа N і М (2≤N≤200, 1≤М≤50 000) – кількість міст і кількість доріг у королівстві Олімпія.  Другий рядок містить числа G і S (1≤GS≤109). Наступні М рядків містять інформацію про дороги та опис пропозиції розбійників. У і+2-му рядку вхідного файлу розташовано 4 натуральних числа, перші два з яких – номери міст, що з’єднані і-ою дорогою (міста нумеруються від 1 до N), наступні два – мінімальна кількість золотих і мінімальна кількість срібних монет, що треба вислати розбійникам в подарунку, щоб і-ту дорогу припинили грабувати. Обидва числа не перевищують 109.

Вихідні дані Єдиний рядок вихідного файлу gift.sol має містити одне ціле число – мінімальну кількість тугриків, що потрібно витратити королю на купівлю золотих та срібних монет, щоб досягнути своєї мети, або -1, у випадку, якщо жодна кількість тугриків не допоможе.

Оцінювання Щонайменше у 30% тестів N не буде перевищувати 30 та M не буде перевищувати 150. Щонайменше у 70% тестів M не буде перевищувати 4000.

Приклад вхідних та вихідних даних

gift.dat

gift.sol

3 3

2 1

1 2 10 15

1 2 4 20

1 3 5 1

30

Пояснення: достатньо покласти у подарунок розбійникам 5 золотих та 20 срібних монет і вони відкриють другу та третю дороги. На купівлю цих монет король витратить 30 тугриків.

Музей (uoi2010)

У столиці країни Олімпія збудований Музей Олімпійської Слави, де виставлено нагороди школярів країни з різних предметних олімпіад. Будівля музею складається з виставкових залів, з’єднаних коридорами. Коридор сполучає рівно два зали. Відомо, що кожного залу музею можна дістатися з будь-якого іншого залу, прямуючи коридорами. Також відомо, що кількість коридорів дорівнює кількості залів.

                Вночі музей патрулюється охоронцями. Кількість охоронців дорівнює кількості залів, та у кожен момент часу охоронець доглядає за своїм залом. Кожну годину згідно плану патрулювання деякі з охоронців переходять в іншу залу, а інші залишаються на місті. План патрулювання відповідає таким вимогам:

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

2. Після переходів охоронців, у кожній залі повинен опинитися рівно один охоронець.

3. Кожну годину застосовується один і той самий план патрулювання.

Наприклад, на рисунку наведений один з можливих планів патрулювання. Згідно йому кожну годину охоронець, що знаходиться у залі 1, переходить до залу 2; охоронець з залу 2 – до залу 3; з залу 3 – до залу 1; охоронці з залів 4 та 5 міняються місцями, а охоронець з залу 6 всю ніч проводить у цьому залі.

Завдання Напишіть програму MUSEUM, яка за інформацією про кількість залів музею і їх сполучення коридорами знайде кількість різних планів патрулювання музею за модулем P.

Вхідні дані Перший рядок вхідного файлу MUSEUM.DAT містить пару цілих чисел N (3N≤50 000) – кількість залів у музеї, та P (2P≤10 000). Наступні N рядків містять пари цілих чисел від 1 до N – номери залів, що з’єднані коридором.

Вихідні дані Єдиний рядок вихідного файлу MUSEUM.SOL має містити ціле число – кількість планів патрулювання музею, за модулем P (остачу від ділення шуканої кількості на P).

Оцінювання Щонайменше в 20% тестів буде виконуватись додаткове обмеження N≤20.

Щонайменше в 60% тестів буде виконуватись додаткове обмеження N≤1000.

Приклад вхідних та вихідних даних

MUSEUM.DAT

MUSEUM.SOL

6 1000

1 2

2 3

3 1

3 4

4 5

4 6

20

Існує 20 різних планів патрулювання: (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 2, 3, 6, 5, 4), (1, 2, 4, 3, 5, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 3, 2, 6, 5, 4), (2, 1, 3, 4, 5, 6), (2, 1, 3, 5, 4, 6), (2, 1, 3, 6, 5, 4), (2, 1, 4, 3, 5, 6), (2, 3, 1, 4, 5, 6), (2, 3, 1, 5, 4, 6), (2, 3, 1, 6, 5, 4), (3, 1, 2, 4, 5, 6), (3, 1, 2, 5, 4, 6), (3, 1, 2, 6, 5, 4), (3, 2, 1, 4, 5, 6), (3, 2, 1, 5, 4, 6), (3, 2, 1, 6, 5, 4). На рисунку з умови зображено план (2, 3, 1, 5, 4, 6).

Торговець (uoi2009)

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

В країні, де живе торговець, є N міст, які пронумеровані від 1 до N. Рідне місто торговця має номер 1, а столиця – номер N. Щоб дістатися столиці, де торговець може продати товар, йому потрібно проїхати певним маршрутом через інші міста. Між деякими парами міст існують дороги, проїзд по яким коштує певної кількості золотих. У кожному місті стягується податок за провезення кожного з видів товару, заданий у відсотках від вартості провезеного через місто товару. Відомо, що виїхавши з будь-якого міста, торговець не може до нього повернутися. Будь-які два міста з’єднані не більше ніж однією дорогою.

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

Завдання

Напишіть програму SALESMAN, що за інформацією про кількість одиниць ваги різних видів товару у торговця, ціни на ці товари у столиці, податки у містах, дороги між містами та вартість проїзду  по цих дорогах встановить максимальний прибуток, що може отримати торговець від реалізації товару.

Вхідні дані

Перший рядок вхідного файлу SALESMAN.DAT містить два цілих числа N (2N≤500) та M (M³1) – кількість міст та доріг між ними. Другий рядок містить три цілих невід’ємних числа, що відповідають кількостям одиниць ваги алмазів, яблук та шовку, що належать торговцю. Третій рядок містить три цілих невід’ємних числа – вартість одиниці ваги алмазів, яблук та шовку відповідно. Наступні рядки з 4-го по N+1 містять по три цілих числа від 0 до 100 включно, що відповідають відсоткам від вартості алмазів, яблук та шовку, що стягується у відповідно у містах від 2 до N-1 у якості податку. У списку міст не враховані рідне місто торговця 1 та столиця N, як такі, що не стягують податок. Наступні M рядків містять по три цілих невід’ємних числа, перші два з яких від 1 до N задають пару міст, між якими прокладено дорогу, а третє – вартість проїзду цією дорогою. Дороги ведуть в напрямку від міста, яке вказано першим, до того, яке вказано другим. Кількості одиниць ваги кожного з видів товару у торговця, вартості товарів та ціни проїзду по дорогам не перевищують 100.

Вихідні дані

Єдиний рядок вихідного файлу SALESMAN.SOL має містити одне число – точне значення знайденого максимального прибутку від поїздки до столиці. Відповідь завжди повинна містити рівно два знаки після крапки. У випадках коли торговець не може отримати прибутку чи дістатися столиці існуючими дорогами, потрібно вивести 0.00

Приклад вхідних та вихідних даних

SALESMAN.DAT

SALESMAN.SOL

4 4

10 5 20

100 5 12

15 40 25

90 20 10

1 2 5

1 3 10

3 4 10

2 4 15

1025.00

 
2 Готуємось до олімпіади з інформатики 2014-2015 PDF Печать E-mail
Добавил(а) Administrator   
06.10.14 11:53

Готуємось до олімпіади  з інформатики- 2

«Класичні алгоритми для роботи з масивами та рядками, їх реалізація у вигляді програм»

1.                   Перевірити, чи є одномірний числовий масив упорядкованим за зростанням.

2.                   Дано натуральна таблиця A[10]. В таблицю B[] записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2

3.                   Вивести числовий ряд Фібоначі (a[i]=a[i-1]+a[i-2];)

Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від'ємними числами, а дівчаток — додатними у вигляді цілих значень α1,α2,…, αN ? Окрім того, у всіх дівчаток на голівках зав'язані бантики заввишки 10 см, а висота паркану H см.

4.                   . «День народження»  – 30 балів.

Учень на своє день народження роздав учням класу цукерки, в тому числі і собі. Хлопцям давав парну кількість, а дівчатам непарну кількість. Підрахувати кількість дівчат та хлопців в класі.

Вхідні дані

Перший рядок містить загальну кількість учнів, натуральне число N.

В наступних рядках кількість розданих цукерок.

Усі числа вхідного файлу не перевищують 1 000 000 000.

Вихідні дані

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

Приклад

 

input.txt

output.txt

5

3

1

2

4

3

3 2

5.                   Новорічна гра

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

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

На новорічному святі Дід Мороз вирішив провести цікаву гру для двох найвеселіших дітлахів.

У мішку Діда Мороза знаходяться не подарунки, а N карток, на кожній із яких написано деяке ціле число Ai. У гру грають двоє дітей. На початку гри обидва гравці навмання витягують по одній картці з мішка Діда Мороза. Учасник, який вийняв картку з більшим числом, отримує від Діда Мороза цукерки, до того ж кількість отриманих цукерок дорівнює різниці чисел, написаних на картках, що вийняли діти.

Наприклад, Сергій та Роман грають у цю гру. Сергій вийняв картку з числом 7, а Роман з числом 3. Після цього Сергій бере собі 4 (7 - 3 = 4) цукерки.

Дід Мороз стомився і не може визначити, скільки цукерок йому слід купити на свято. Допоможіть йому. Його цікавить максимальна кількість цукерок, яку може отримати дитина в результаті гри.  

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N(2 ≤ N ≤ 1000), яке представляє кількість карток.

Другий рядок вхідного файлу містить рівно N цілих чисел Ai(1 ≤ Ai ≤ 32767). Числа у рядку розділені одиночними пробілами. Ai – число, написане на і-й картці.

Формат вихідних даних: єдиний рядок вихідного файлу має містити одне число – максимальна кількість цукерок, яку може отримати дитина за гру.

Приклад вхідних і вихідних даних:

game.in

game.out

2

7 3

4

5

4 2 7 9 5

7

4

3 3 3 3

0

 


Страница 10 из 26

Статистика

Пользователей : 152
Статей : 220
Просмотрено статей : 88159

Вход/Регистрация

Нет