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

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

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

1.      Методика складання алгоритмів

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

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

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

$1-          Довга арифметика

$1-          Системачислення

$1-          Сортування, пошук

$1-          Перебір

$1-          Бінарні дерева

$1-          Графи (пошук, жадібні, динамічне)

$1-          Обчислювальна геометрія

2.      Змагання сортування http://www.e-olymp.com/ru/contests/5852

Теорія

Методи сортування:

$11)      Бульбашка

$12)      Вибір максимального (мінімального)

$13)      Швидке

$14)      Вектором

Сортування

Перестановки

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int i,j,n;

int main()

{cin>>n;

vector<int> a(n);

for (int 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;

}

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

vector<int> a;

int n;

int main()

{cin>>n;

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

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

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

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

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

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

}

 return 0;

}

 
Заняття 23.09.2015 PDF Печать E-mail
Добавил(а) Administrator   
30.09.15 09:16

   Методика складання алгоритмів

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

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

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

$1-          Довга арифметика

$1-          Системачислення

$1-          Сортування, пошук

$1-          Перебір

$1-          Бінарні дерева

$1-          Графи (пошук, жадібні, динамічне)

$1-          Обчислювальна геометрія

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

 


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

Статистика

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

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

Нет