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

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

Школа олімпійського резерву з інформатики
Заняття 16.09.2015 PDF Печать E-mail
Добавил(а) Administrator   
16.09.15 00:00

Всеукраїнськiй олімпіадi з інформатики NetOI-2015 (http://www.olymp.vinnica.ua/)

Тренувальний тур

//a

#include <iostream>

using namespace std;

int main()

{int x1,y1,x2,y2,x3,y3,x4,y4;

    cin>>x1>>y1;

    cin>>x2>>y2;

    cin>>x3>>y3;

    cin>>x4>>y4;

int x20=max(x1,x2);

int x10=min(x1,x2);

int x40=max(x3,x4);

int x30=min(x3,x4);

int v=min(x20,x40)-max(x30,x10);

    if (v>=0)cout << v << endl; else cout<<-1;

    return 0;

}

//d

#include <iostream>

#include <string.h>

#include <string>

using namespace std;

int main()

{

    char *n=new char[200000000];

    cin>>n;

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

        for(int j=0;j<strlen(n)-1;j++)

        if(n[j]>n[j+1])swap(n[j],n[j+1]);

int k=0;

while(n[k]=='0')k++;

swap(n[0],n[k]);

    cout << n << " ";

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

        for(int j=0;j<strlen(n)-1;j++)

        if(n[j]<n[j+1])swap(n[j],n[j+1]);

    cout << n << endl;

    return 0;

}

//b

#include <iostream>

using namespace std;

int main()

{long long int n,m,temp;

int k=0;

cin>>n>>m;

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

{

    temp=i;

    while (temp%2==0) temp=temp/2;

        while (temp%3==0) temp=temp/3;

            while (temp%5==0) temp=temp/5;

            if (temp==1) k++;

}

    cout << k << endl;

    return 0;

}

//e

#include <iostream>

#include <string.h>

#include <string>

using namespace std;

int main()

{

    char *n=new char[200000000];

    cin>>n;

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

        if(n[j]>='0'&&n[j]<='9')cout<<n[j];

    cout <<  endl;

    return 0;

}

//c

#include <iostream>

using namespace std;

int main()

{long long int n,minn;

int a[100000];

cin>>n;

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

minn=2000;

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

    if(a[i]<minn && a[i]>0)  minn=a[i];

 if(minn==2000)    cout << 0 << endl; else  cout << minn << endl;

    return 0;

}

//f

#include <iostream>

using namespace std;

int main()

{long long int n,k,f,a,b,black,white;

int r[10000];

cin>>n;

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

 cin>>k;

white=0;black=0;

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

    {

        cin>>a>>b;

        if ((a%2==0 && b%2==0 )|| (a%2==1 && b%2==1 )) black++; else white++;

    }

    if (white==k || black==k)r[i]=1;else r[i]=0;

}

for(int i=1;i<=n;i++)cout<<r[i];

    cout <<  endl;

    return 0;

}

 
Заняття 09.09.2015 PDF Печать E-mail
Добавил(а) Administrator   
09.09.15 00:00

1.      Базові структури.

Розв’язати і протестувати задачі в системі (http://134.249.159.199/cgi-bin/new-client?contest_id=23)

Логін user1-user5(пароль - 1)

2.      Codeforces  (http://codeforces.com/)

http://codeforces.com/problemset/problem/550/A

Два підрядка

Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два  підрядка, якы не пертинаються "AB" і "BA" (ланцюжків можуть йти в будь-якому порядку).

Вхідні дані

На вхід подається рядок s довжиною від 1 до 105 символів, що складається з великих літер латинського алфавіту.

Вихідні дані

Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше

3.      Всеукраїнськiй олімпіадi з інформатики NetOI-2015 (http://www.olymp.vinnica.ua/

Задача DEMO_A
         На площині задано координати двох відрізків AB і CD. Знайти спільну частину проекцій цих відрізків на вісь абсцис.

Вхідні дані

         Ви вводите з клавіатури 8 цілих чисел - координати точок  A, B, C, D. Кожне число не перевищує за абсолютною величиною 1000. 

Вихідні дані
         Ви виводите на екран одне число - спільну частину проекцій. Якщо спільна частина - порожня множина, вивести -1, якщо це одна точка - вивести 0. 

Приклад вхідних та вихідних даних 
Вхід: 2 2 7 5 3 4 8 1 
Вихід: 4

Задача DEMO_B

         Скільки натуральних чисел виду 2a3b5ca,b,c - невід'ємні цілі числа) належать відрізку [M;N]

Вхідні дані
         Ви вводите з клавіатури 2 цілих числа M та N. Кожне з чисел не перевищує за абсолютною величиною 10000.

Вихідні дані 
         Ви виводите на екран одне число - шукану кількість чисел. 

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

Задача DEMO_C

         Дана послідовність N цілих чисел. Знайти найменший додатній елемент цієї послідовності. 

Вхідні дані 
         Ви вводите з клавіатури кількість чисел N та N цілих чисел - елементів цієї послідовності. Число N не перевищує 10000, кожний елемент послідовності не перевищує за абсолютною величиною 1000. 

Вихідні дані 
         Ви виводите на екран одне число - шуканий елемент послідовності. Якщо у послідовності немає додатніх елементів - вивести 0. 

Приклад вхідних та вихідних даних 
Вхід: 7 -4 4 -7 3 0 8 2 
Вихід: 

Задача DEMO_D

         Задано натуральне число N. Знайти найменше та найбільше число, яке складається з тих самих цифр та у такій самій кількості, що і N

Вхідні дані 
         Ви вводите з клавіатури число N (1
£ N £2000000000). 

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

Приклад вхідних та вихідних даних 
Вхід: 7051 
Вихід: 1057 7510 

Задача DEMO_E

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

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

Вихідні дані 
         Ви виводите на екран шуканий рядок. 

Приклад вхідних та вихідних даних 
Вхід: Ф11р88н 
Вихід: 1188 

Задача DEMO_F

         Дано K клітин шахової дошки. З'ясувати, чи всі вони одного кольору. 

Вхідні дані 
         Ви вводите з клавіатури кількість контрольних прикладів, потім число К - кількість клітин шахової дошки,а у наступних К рядках - координати клітин (натуральні числа, не більші 8). 

Вихідні дані 
         Ви виводите на екран для кожного приклада 1, якщо всі клітини одного кольору і 0, якщо це не так. 

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

Вхід:

3

 

3

 

1

2

8

1

8

5

2

 

1

1

1

2

2

 

1

1

2

2


Вихід: 101 


Парне+парне, непарне-непарне –чорна

Парне+непарне, непарне-парне –біла

$14.      Дистанційне навчання  *(http://dystosvita.mdl2.com/ )

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

Основи програмування (Python)

 
Турнір з програмування PDF Печать E-mail
Добавил(а) Administrator   
06.05.15 10:30

Повідомляємо, що 12 травня стартує проект з програмування «9 витків спіралі» пам’яті Присяжнюка Анатолія Васильовича. Саме під такою назвою цей проект розробив та реалізовував awpis.

Кожен день учасникам буде запропоновано від 5 до 10 задач, починаючи з елементарних і до складних. Лекції будуть розміщуватись на http://www.e-olimp.com/discuss/11 .

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

Кожен етап буде тривати рівно тиждень (7 днів), для того, щоб всі учасники встигли розв’язати всі задачі.

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

Етапи будуть відкритими для всіх, проходити в "Змагання" (не в закритій групі).

Прохання до всіх учасників проекту в профілі подати повні дані    (місто, ПІБ, місце навчання, вік).

 
15.04.2015 Площа многокутника PDF Печать E-mail
Добавил(а) Administrator   
15.04.15 00:00

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

Площа многокутника

   Задано координати n послідовних вершин многокутника. Знайти його площу.


Технічні умови

   Вхідні дані

   Перший рядок містить кількість вершин многокутника n. У наступних n рядках через проміжок задано цілочисельні координати його послідовних вершин xiyi. Відомо, що 3 ≤ n ≤ 1000-1000≤ xiyi ≤ 1000.

   Вихідні дані

   Площа многокутника S, обчислена з точністю до трьох десяткових знаків.

Последнее обновление 27.04.15 13:54
 
22.04.2015 Опукла оболонка PDF Печать E-mail
Добавил(а) Administrator   
27.04.15 13:48

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

Опукла оболонка

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

Технічні умови

   Вхідні дані

   Перший рядок містить кількість точок n (3 ≤ n ≤ 1000) на площині. Далі йдуть n рядків, кожний з яких містить пару координат xiyi (-10000 ≤ xiyi ≤ 10000). Усі числа цілі, усі точки різні.

   Вихідні дані

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

Последнее обновление 27.04.15 13:52
 
Обчислювальна геометрія PDF Печать E-mail
Добавил(а) Administrator   
11.03.15 09:30

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

Задача 1

Від’їжджаючи з домівки, поет залишив коту, прикутого до дуба ланцюгом довжиною L, N рибин. Знаючи координати голови та хвоста кожної з них, порахуйте, на яку добу у кота виникне почуття голоду, якщо він починає голодувати тоді, коли за добу з’їсть менше, ніж К рибин. Рибину кіт може з’їсти тільки тоді, коли зможе дотягнутися хоча б до однієї її точки. Координати дуба (0, 0). Усі числа цілі, не перевищують за модулем 100. (Автор задачі Присяжнюк А.В.)

Задач 2.

FOREST. Сергійко заблукав в лісі і вийти з нього він може тільки потрапивши на шосе, яке має вигляд нескінченної прямої, що задається рівнянням ax + by =1. В початковий момент часу Сергійко знаходиться в точці (хоо) і щоб остаточно не заблукати він вирішив йти по компасу в одному з чотирьох напрямків: "Північ", "Південь", "Захід" або "Схід". В довільний момент часу він може змінити напрямок руху на інший з вказаних чотирьох.

Осі координатної системи в умові задачі направлені по сторонам світу.

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

Вхідні дані: Єдиний рядок вхідного файлу FOREST.DAT містить числа a, b, хо та уо. Всі числа цілі та знаходяться в межах від -1000 до 1000, a і b одночасно не дорівнюють 0.

Вихідні дані: Єдиний рядок вихідного файлу FOREST.SOL має містити довжину найкоротшого шляху з точністю до двох знаків після коми.

Задач 3

VIОLАТION. В деякому місті шоферам заборонено при русі робити ліві повороти. За кожен такий поворот шофер повинен сплачувати штраф в розмірі М гривень. Для спостереження за рухом транспорту в місті встановлена комп'ютерна система, яка фіксує координати автомобіля на початку руху, в кінці та при кожному повороті.

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (хi, уi), і=1,2,...,М, де (х1, у1) - точка початку руху, (хNN) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані:Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

 

VIOLATION.DAT

VIOLATION.SOL

5 50

 

50

0 0

   

2 0

   

1 1

   

5 1

   

5 -1

   

Задач 4.

 Вписаний трикутник

Дано опуклий N-кутник. Знайдіть площу максимального трикутника, який лежить всередині (або на межі) цього N-кутника.

Формат вхідних даних: у першому рядку записано число N – кількість вершин многокутника (3 ≤ N ≤ 2000). Далі йдуть N рядків, у кожному з яких записані два цілих числа, що не перевищують по модулю 107 - координати вершини многокутника. Координати йдуть в порядку обходу многокутника або за часовою стрілкою, або проти.

Формат вихідних даних: виведіть площу знайденого трикутника з точністю до трьох знаків.

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

triangle.in

triangle.out

4

0 0

10 0

12 12

0 10

70.000

Задача 5.

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

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

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

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

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

У першому рядку міститься N (3 <= N <= 1000) - число вершин багатокутника. У наступнихN рядках йдуть координати (Xi, Yi) вершин багатокутника в порядку обходу за годинниковоюстрілкою. Xi і Yi - цілі числа, по модулю не перевищують 1000000.

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

У вихідний файл вивести одне число - шукану кількість точок.

Приклади:

POINT.DAT

POINT.SOL

4

-1 -1

-1 1

1 1

1 -1

1

3

0 0

0 2

2 0

0

Задача 6

Нова держава.Іваном Річкоплавцем і його командою був відкритий новий багатий континент, який назвали Іванія, де вони вирішили оселитися. Кожним членом команди було засноване нове поселення і назване його іменем.  Їхні нащадки вирішили утворити нову державу і побудувати кордон, таким чином щоб границя була мінімальної довжини у вигляді прямих відрізків, які з’єднають поселення, біля яких пройде кордон при умові, що в середині будуть всі інші поселення і площа країни буде найбільшою. Яка довжина границі утвореної держави і її площа?

Вхідні дані

В першому рядку знаходиться натуральне N (3<=N<=50) – число поселень. В наступних рядках координати кожного поселення X,Y, які записуються через пропуск. X,Y – цілі числа (-1000<=X<=1000; -1000<=Y<=1000).

Вихідні дані

В першому рядку Р, а в другому S. P i S – дійсні числа із виведеними двома розрядами після коми.

Приклад вхідного файлу Input.txt

Приклад вихідного файлу Output.txt

5

0 0

0 2

1 1

2 2

2 0

8.00

4.00

 

Задача 7

 „STARWAR“. Давним-давно, в одній далекій-далекій галактиці, Лукас Скайуокер разом із своїми товаришами вирішив штурмувати планету військ Імперії Корусант. І яка ж війна без карт? Зрозуміло, що Лукас з товаришами використав дроїдів, які склали N карт. Отже, мапи вже були, але все ще залишалась одна проблема: «Якими силами потрібно проводити штурм?» А для цього треба знати загальну площу, яку покривають карти повстанців. Тут Лукас з товаришами кинулись шукати людину, яка б допомогла їм... і знайшли Вас. Вам же ж потрібно допомогти Лукасу  та його товаришам і  скласти програму, яка знаходить загальну площу території, яку  штурмуватимуть друзі.

Формат вхідних даних:  У вхідному файлі  Corusant.DAT перший рядок містить єдине натуральне число N (1<=N<=10 000) – кількість карт, що має у розпорядженні Лукас. Кожен з наступних N рядків описує єдину карту і містить чотири цілих числа x1, y1, x2,y2 (0<=x1<x2<=30 000, 0<=y1<y2<=30 000). Значення (x1, y1) і (x2,y2) – координати, у вказаному порядку, лівого нижнього і правого верхнього кута карти. Кожна карта має форму прямокутника і її сторони паралельні до осей Декартової системи координат.

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

Наприклад:

Corusant.DAT

Corusant.SOL

1

0 0 15 45

675

2
10 10 20 20

15 15 25 30

225

 Задача 8

 “Зона досяжності”. Нещодавно на ринок операторів мобільного зв’язку вийшла нова компанія – NOVOTEL. Щоб відразу ж стати конкурентоспроможною, підприємство відразу ж намагається укласти контракти з органами місцевої влади на права встановлення своєї зони покриття. Компанія NOVOTEL встановлює сітку зв’язку в кожному місті за таких умов: оператор мобільного зв’язку зобов’язується надати зв’язок як мінімум K домівкам в певному місті, тобто, щоб K будинків були в зоні досяжності. Оскільки компанія NOVOTEL – дебютат на ринку зв’язку, то їх невеликий бюджет дозволяє встановити лише базову станцію стільникового зв’язку з певним радіусом дії сигналу на ній. При цьому економісти компанії наполягають, щоб гроші всіх акціонерів використовувалися найраціональнішим чином. І тому, оскільки кошторис робіт пропорційний величині зони покриття, яка встановлюється оператором, то, звичайно, підприємці дали директиву встановити базову станцію стільникового зв’язку так, щоб зона її покриття була найменш можливою, але неодмінно покривала щонайменше K домівок. (Дім вважається в зоні досяжності, якщо відстань від нього до базової станції стільникового зв’язку менша або рівна, ніж радіус досяжності станції передачі).

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

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

Формат вхідних даних: Перший рядок вхідного файла містить два цілих числа N і K (1<K<N<500), де – N кількість домівок у місті, а K – кількість домівок, які повинні бути забезпечені зв’язком. Тоді у наступних N рядках міститься по два цілих числа (X,Y) (0<X,Y<10000) координати домів.

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

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

  Наприклад:

NOVOTEL.DAT

NOVOTEL.SOL

4 3

2 2

2 8

6 5

6 2

2.50000

4.0000 3.5000

 


9 5

2 2

8 5

5 3

1 8

2 6

4 8

3 3

4 6

4 1

2.236068

3.0000 4.0000

 
   


Задача 9

Розділення многокутників http://www.e-olimp.com.ua/ua/problems/4518

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

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

   Наприклад, на рисунку зображена пряма, що задає певне розділення многокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D) + (C + E) та (A + D) + (B + C). З рисунку, D + C + E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D + C + E.

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



Технічні умови

   Вхідні дані

   Перший рядок містить одне ціле число (≤ ≤ 20) - кількість вершин першого многокутника. Наступні N рядків містять пари цілих чисел – координати вершин першого многокутника у порядку обходу. (N + 2) -ий рядок файлу містить число (≤ ≤ 20) - кількість вершин другого многокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого многокутника. Координати точок додатні і не перевищують 1000.

   Вихідні дані

   Вивести в одному рядку дві пари чисел - координати двох точок, які однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x1 y1 x2 y2. Координати потрібно виводити з точністю 10-3. Координати точок повинні бути додатними і не перевищувати 1000.



Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за тест: 4.7619
Автор: Богдан Рубльов,Тарас Галковський
Джерело: 2007 XX Всеукраїнська олімпіада з інформатики, Кременчук, Квітень 10 - 16, тур 2


Приклад

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

3

2 1

3 3

4 1

3

5 2

3 2

4 3

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

2 5 4 1

 
Тематика задач PDF Печать E-mail
Добавил(а) Administrator   
04.03.15 09:29

Тематика задач

Зміст

Тема: Сортування

Тема: Формула (рекурентна, загального елемента)

Тема: Повний перебір

Тема: Обчислювальна геометрія

Тема: Теорія графів

Тема: Динамічне програмування

Тема: Жадібні алгоритми

Тема: Робота з рядками (синтаксичний і лексичний розбір виразів)

Тема: Дерева (бінарні, остові)

Тема: Сортування

XXI Всеукраїнська олімпіада з інформатики (2008)

Другий тур

Знижки

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

1. При купівлі трьох товарів ви платите за них як за два найдорожчих з них.

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

Таким чином, певні товари можна об’єднати у трійки або четвірки і заплатити за них менше. Треба визначити найменшу можливу суму грошей, яка буде витрачена на придбання усіх подарунків.Наприклад, якщо ціни п’яти обраних подарунків складають: 50, 80, 50, 100, 20, то можна окремо придбати чотири перших товари, отримати за них знижку, та потім купити подарунок, що залишився за його номінальну ціну. Загалом вся покупка буде коштувати 250 грошових одиниць, замість 300.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DISCOUNT.DAT містить одне ціле число N (0≤N≤10 000). Другий рядок містить N натуральних чисел – ціни подарунків. Сума цін усіх подарунків менша за 109. Об’єднувати можна не лише ті товари, що йдуть підряд у вхідних даних.

Вихідні дані

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

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

DISCOUNT.DAT

DISCOUNT.SOL

5

50 80 50 100 20

250

 

Тема: Формула (рекурентна, загального елемента)

XXI Всеукраїнська олімпіада з інформатики

Перший тур

Гірлянда

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

Завдання

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

Вхідні дані

Єдиний рядок вхідного файлу GARLAND.DAT містить одне ціле число N (1N≤109) – номер секунди.

Вихідні дані

Єдиний рядок вихідного файлу GARLAND.SOL має містити ціле число – кількість лампочок, що будуть горіти на секунді N.

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

GARLAND.DAT

GARLAND.SOL

5

2

Тема: Повний перебір

Щасливий білет

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

$11.     Спочатку номер розбивають на цифри, та певні сусідні цифри об’єднують у числа.

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

$13.     Неможна міняти місцями цифри.

$14.     Якщо вдається скласти такий вираз, який після обчислення дорівнюватиме шуканому числу k, то білет вважається щасливим.

Операцію «розділити» можна використовувати тільки у випадках, коли в наслідок ділення буде отримано ціле число.

                Наприклад, розглянемо білет номер: 182836. Візьмемо k=840. Розіб’ємо число на чотири: 1, 8, 2, 836. Число k можна отримати, наприклад, таким чином: 1*(8/2+836)=840.

Завдання

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

Вхідні дані

Єдиний рядок вхідного файлу LUCKY.DAT містить два числа: ціле k (1k≤1000) та номер білету. Номер білету складається з шести цифр, та може починатися з 0.

Вихідні дані

Єдиний рядок вихідного файлу LUCKY.SOL повинен містити будь-який з можливих наборів чисел на які може бути розбитий номер білету для отримання числа k. Якщо число не може бути отримане, то єдиний рядок вихідного файлу повинен містити число 0 (нуль).

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

LUCKY.DAT

LUCKY.SOL

840 182836

1 8 2 836

120 000001

0

Тема: Обчислювальна геометрія

Відстань

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

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DIST.DAT містить єдине ціле число – кількість точок N
(3
N700) заданих на площині. Далі йдуть N рядків, кожен з яких задає точку площини у форматі “x y” (-5000x, y≤5000), x та y – цілі числа. Жодні дві точки не мають однакових координат.

Вихідні дані

Єдиний рядок вихідного файлу DIST.SOL повинен містити найбільшу відстань від однієї з заданих точок, до прямої побудованої на двох інших точках, з точністю до 10-6. Відповідь повинна бути записана у форматі з точкою (<ціла частина>.<дрібна частина>)

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

DIST.DAT

DIST.SOL

5

14

2 0

2 4

3 5

4 4

4.242641

Розділення багатокутників

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

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

Наприклад, на рисунку зображена пряма, що задає певне розділення багатокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D)+(C+E) та (A+D)+(B+C). З рисунку, D+C+E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D+C+E.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DIVIDE.DAT містить одне ціле число N (3N≤20) – кількість вершин першого багатокутника. Наступні Nрядків містять пари цілих чисел – координати вершин першого багатокутника у порядку обходу. (N+2)-й рядок файлу містить число M (3M≤20) – кількість вершин другого багатокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого багатокутника. Координати точок додатні та не перевищують 1000.

Вихідні дані

Єдиний рядок вихідного файлу DIVIDE.SOL має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x1 y1 x2 y2. Координати потрібно виводити з точністю 10-3. Координати точок мають бути додатні та не більші за 1000. 

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

DIVIDE.DAT

DIVIDE.SOL

3

2 1

3 3

4 1

3

5 2

3 2

4 3

2 5 4 1

Тема: Теорія графів

Робочий стіл

На робочому столі операційної системи розташовано N ярликів, кожен з яких заданий цілими координатами x та y, а також назвою. Назва ярлику складається з маленьких символів латинського алфавіту (a-z). Необхідно перейти (тобто перемістити виділення) з виділеного ярлика S до ярлика F, за допомогою клавіатури, використавши найменшу можливу кількість натискань. Перехід здійснюється за допомогою натискань на клавіші з літерами a-z, або на стрілки “”,“”,“” та “”.

При натисканні на клавіші з літерами перехід відбувається за такими правилами:

$11.     Якщо на робочому столі є ярлики, назва яких починається на натиснуту літеру, та виділено однин з них, то перехід відбувається на ярлик, з назвою наступною у лексикографічному порядку серед тих, які починаються на цю букву (після останнього, виділення переходить на перший). Тобто, якщо є ярлики a, ab, b, то при натисканні a виділення буде переходити лише між aта ab.

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

$13.     Якщо на робочому столі немає ярликів, назва яких починається на натиснуту літеру, перехід не відбувається.

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

Наприклад, якщо виділено ярлик a (див. рисунок), то при натисканні стрілок можуть відбутись такі переходи:

$11.      Стрілка “”. Виділення переходить на ярлик b, оскільки він є найближчим у секторі цієї стрілки. При наступному натисканні “” виділення перейде на c.

$12.      Стрілка “”. В секторі стрілки знаходяться ярлики d та e. Виділення перейде на d – цей ярлик ближче.

$13.      Стрілка “”. В секторі “” знаходиться тільки ярлик g, який і буде виділено.

$14.      Стрілка “”. В цьому секторі знаходяться ярлики f та h, які рівновіддалені від a. Виділення переходить на ярлик h, оскільки x-координата цього ярлика менша. Якщо після цього натиснути “”, то виділення залишається на h,оскільки у секторі знизу немає жодного ярлику.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу DESKTOP.DAT містить три цілих числа N (1N≤1000) – кількість ярликів на робочому столі, S (1SN) – номер обраного ярлика, F (1FN) – номер ярлика на який потрібно перейти. Кожен з наступних N рядків задає окремий ярлик у такому форматі «x y text», x,y – цілі числа  (0x, y106), а текст складається з не більш ніж 50, та не менше ніж з одного маленького символу латинського алфавіту a-z.

                Жодні два ярлика не мають однакових координат, або ж однакових назв. Координатна сітка – стандартна, тобто “” збільшується y-координата, а “x-координата.

Вихідні дані

Єдиний рядок вихідного файлу DESKTOP.SOL має містити одне ціле число – мінімальну кількість натискань на клавіатуру що дозволять перейти з ярлика S до ярлика F.

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

DESKTOP.DAT

DESKTOP.SOL

8 1 4

5 4 a

2 3 b

3 2 h

0 3 c

4 6 d

7 6 e

7 2 f

9 6 g

1

 

Острови

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

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

Завдання

Напишіть програму ISLANDS, що за картою островів знаходить мінімальну вартість будівництва групи мостів, що з’єднують всі острови.

Вхідні дані

Перший рядок вхідного файлу ISLANDS.DAT містить два цілих числа N та M (1N, M≤500) – розміри карти островів. Кожен з наступних N рядківмістить Mсимволів 0 (вода) або 1 (суша).

Вихідні дані

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

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

ISLANDS.DAT

ISLANDS.SOL

5 5

01110

00100

10010

00100

10001

8

 

Тема: Динамічне програмування

Альтернативні шляхи (100  балів)

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

Будемо поблажливими до Мандрівника, і вважатимемо «гарними» не лише шляхи, на котрих в точності досягається максимально можлива сума, а ще й шляхи, сума котрих відрізняється від макси­маль­ної не більше ніж на K.

Кількість «гарних» шляхів гарантовано не перевищує 109.

Завдання

Напишіть програму GOODWAYS, що знаходить значення макси­ма­льно можливої суми та кількість «гарних» шляхів.

Вхідні дані

Перший рядок вхідного файлу GOODWAYS.DAT містить три цілих числа M (2M≤200), N (2N≤200) та K (0K≤200). Кожен з наступних Mрядків містить N чисел, записаних у відповідних клітинках.

Вихідні дані

Перший рядок вихідного файлу GOODWAYS.SOL має містити максимальну можливу суму; другий рядок – кількість маршрутів, сума чисел котрих відрізняється від максимальної не більш ніж на K.

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

GOODWAYS.DAT

GOODWAYS.SOL

2 3 3

1 9 7

2 5 3

20

2


Тема: Жадібні алгоритми

Доставка

Місто Прямий Ріг являє собою одну пряму вулицю. У місті працює компанія, що займається доставкою товарів. Для зручності, адреси доставки надані у вигляді чисел, що задають відстань від офісу компанії. Додатні числа в один бік, а від’ємні – в інший. Замовлення на доставку виконуються компанією послідовно, у тому порядку, в якому вони були задані.

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

Завдання

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

Вхідні дані

Перший рядок вхідного файлу ORDER.DAT містить ціле число N (1N≤100000) – кількість замовлень. Далі слідує N рядків, кожен з яких містить єдине ціле число – відстань від офісу до адресата. Якщо відстань додатня – то адресат знаходиться у одній частині міста відносно офісу компанії, а якщо від’ємна, то у іншій. Відстані за модулем не перевищують 108.

Вихідні дані

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

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

ORDER.DAT

ORDER.SOL

5

1

-1

2

-2

3

5

Тема: Робота з рядками (синтаксичний і лексичний розбір виразів)

Пошук рядку

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

Завдання

Напишіть програму SUBSTR, що за заданою послідовністю знаходить першу підпослідовність, яка складається з різних символів.

Вхідні дані

Вхідний файл SUBSTR.DAT містить послідовність, яка, для зручності, розбита на декілька рядків. Кожен рядок містить не більше 100 символів. Загальна довжина послідовності – не більше 10000 000символів.

Вихідні дані

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

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

SUBSTR.DAT

SUBSTR.SOL

abcabcdabc

bacdbca

abcd

Тема: Дерева (бінарні, остові)

Катакомби

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

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

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

Завдання

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

Вхідні дані

Вам надано 10 вхідних файлів, що мають назви CATACOMB.D01, CATACOMB.D02,…, CATACOMB.D10, у такому форматі. Перший рядок містить одне ціле число D– глибину катакомб. Другий рядок містить 2D різних цілих чисел від 1 до 2D. Кожне i-те з них ідентифікує номер печери до якої повинен попасти сундук, що находиться спочатку у печері i.

Вихідні дані

Створіть 10 файлів CATACOMB.S01,…, CATACOMB.S10. Ці файли повинні містити відповіді для відповідних вхідних файлів. Перший рядок файлу має містити єдине ціле число – мінімальну сумарну відстань, яку пройдуть пірати зі скарбами. Другий рядок: ціле число K – відповідна кількість обмінів. Кожен наступний з K рядків: два числа, що є номерами печер, між якими відбувається обмін. Обміни повинні бути вказані у тому порядку, в якому вони мають відбуватися.

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

CATACOMB.D00

CATACOMB.S00

2

4 3 1 2

20

3

3 4

1 4

3 2

Наприклад, можна проводити обміни таким чином. Спочатку поміняти місцями скарби у печерах 3 та 4. Пройдена відстань 4 (по 2 для кожного сундука). Потім поміняти скарби у печерах 4 і 1, та 3 і 2. Відстань в обох випадках – 8. Таким чином – усі встануть на свої місця, а сумарна відстань буде 20.

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

http://ejudge.ippo.dn.ua/cgi-bin/new-register?contest_id=59

8-9 класи

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

У єдиному рядку задаються два натуральних числа а і b, що НЕ перевищують 109.

Виведіть "Yes", якщо Сторінки а i b розташовані на одному Аркуші, і "No",якщо на різних.

введення

виведення

5 6

Yes

31 13

2. Гра. Вітя і Льоня грають в гру. Спочатку кожен записує на аркуші паперу число від 1 до 6 - прогноз, а потім вони кидають гральну кістку, грані якої пронумеровані числами від 1 до 6. Результат гри визначається тим наскільки близько випало на кістки число до того, яке записано гравцем на аркуші . Чий прогноз виявиться ближче до результату кидка, той і вважається переможцем. Потрібно написати програму для виявлення переможця.

У єдиному рядку задаються три числа - прогноз Віті, прогноз Пені та результат кидка кістки. Всі числа цілі і знаходяться в діапазоні від 1 до 6.

Виведіть "W", якщо перемогу слід присудити Віті, або "L", якщо переможцем є Льоня, або ж "D", якщо результат гри нічийний (тобто обидва прогнози виявилися однаково близькі до результату кидка).

   

введення

виведення

3

4

5

L

1

6

2

W

4

4

3

D

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

У першому рядку задаються два цілих числа s і N (1 ≤ s <3, 0 <N <100), які позначають відповідно початкову позицію в ряду наперстка, під який був покладений кулька ведучим, і кількість обмінів, які він зробив. У кожному з наступних N рядків задаються по два цілих

числа а і b (1 ≤ а, b ≤ 3, а ≠ b) - номери позицій, наперстки з яких ведучий міняв місцями на відповідному кроці.

Виведіть одне число - позицію наперстка, який повинен вибрати гравець, щоб виграти.

введення

виведення

13

3

12

 

13

 

32

 

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

У єдиному рядку задаються три цілих числа х, у, z (-109 <х, у, z <109).

Виведіть "Yes", якщо коник побуває в якийсь момент на позначці z, і "No" в іншому випадку.

введення

виведення

1 2 5

Yes

136

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

  У єдиному рядку задається чотири невід'ємних цілих числа а1, а2, а3, К, що не перевищують 109, де а - кількість цукерок, яке спочатку було у г-го брата.

Виведіть одне число - мінімальну кількість цукерок, яке брати повинні подарувати один одному, щоб ніхто не посварився. Якщо це неможливо, виведіть одне число -1.

       

введення

 

виведення

1

6

3

2

 

2

 


10-11 класи

1. Приготування яєць. Петя любить їсти варені яйця. Для того, щоб приготувати яйце некруто потрібно варити його Х хвилин. Щоб приготувати яйце круто, потрібно спочатку приготувати його некруто, а потім варити ще Y хвилин. Петя любить їсти яйце, коли воно наполовину приготовлено круто, тобто коли яйце спочатку приготовлено некруто, а потім ще пройшла половина часу, необхідного для того, щоб це яйце стало приготованим круто. Знайдіть скільки хвилин Петі потрібно варити яйце.

У єдиному рядку задаються два цілих числа Х і У (1 ≤ Х, У <1018).

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

 

введення

 

виведення

10 11

 

15.5

 

2. Годинник. Є свідчення N годин. Відомо, що До з них показують неправильний час, показання інших - вірні. Потрібно написати програму для визначення точного часу.

У першому рядку задається два цілих числа N і К (0 <К GNG 1000). У кожному з наступних N рядків задаються по два числа - кількість годин (від 0 до 23) і хвилин (від 0 до 59), які показують відповідні години.

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

введення

виведення

53

1320

13 20

 

20 13

 

9 00

 

13 20

 

13 21

 

З. Транспортна задача. У країні Інформландія є всього два види міського транспорту: метро і автобус. Грошова одиниця в Інформландіі - природно, біт. Одна поїздка на метро коштує 3 біта, а на автобусі - 2 біти. При цьому можна купити місячний проїзний на необмежену кількість поїздок: на метро - 40 бітів, на автобус - 30 бітів, на автобус і метро - 60 бітів. Яку найменшу суму потрібно витратити на проїзд у місяць жителю Інформландіі, якщо в тому місяці належить зробити х поїздок на метро і у на автобусі.

У єдиному рядку задаються два цілих числа х і у (0 <х, у <100).

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

 

введення

 

виведення

930

 

57

 

4. Морозиво. Є N морозив. Дитина з'їдає будь морозиво за 1 хвилину. Для кожного морозива відомо, через скільки хвилин воно розтане. Потрібно визначити мінімальну кількість дітей, які можуть з'їсти ці всі ці морозива так, щоб ні одне з них не встигло розтанути. Кожну хвилину одна дитина може їсти лише одне морозиво, і кожне морозиво може їсти лише одна дитина.

У першому рядку задано ціле число N (1 ≤N ≤ 105). Другий рядок містить N натуральних чисел, що не перевищують 106, кожне з яких визначає час, через який розтане відповідне морозиво.

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

     

введення

виведення

4

     

2

1

2

3

2

 

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

У єдиному рядку задано ціле число N (1≤N≤1000).

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

 

введення

       

виведення

3

 

3

2

3

1

2 1

 

Зауваження. При виконанні наведеної в прикладі послідовності натискань ліфт здійснить такі поїздки: {(1 - + 3), (3 - + 2), (2 - + 3), (3 - + 1), (1 - + 2), (2 - + 1)}, що є достатнім для перевірки, оскільки містить в собі всі можливі поїздки.

 


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

Статистика

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

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

Нет