Заняття 5 (05.10.2016) Печать
Добавил(а) Administrator   
11.10.16 10:00

Заняття 5 (05.10.2016)

 

Базові структури алгоритмів (структура циклу)

 

1. Прості числа

 

http://www.e-olymp.com/uk/problems/830

 

Вивести всі прості числа від M до N включно.

 

Вхідні дані

 

У першому рядку знаходяться відокремлені пропуском M і N (2 ≤ M ≤ N ≤ 300 000).

 

Вихідні дані

 

Вивести числа у порядку зростання, по одному у рядку. Якщо між M і N включно немає простих - вивести "Absent" (без лапок).

 

Вхідні дані

 

Sample 1

 

2 5

 

Sample 2

 

4 4

 

Вихідні дані

 

Sample 1

 

2

 

3

 

5

 

Sample 2

 

Absent

 

2. Решето Ератосфена

 

http://www.e-olymp.com/en/problems/4739

 

За введеним числам A і B вивести всі прості числа в інтервалі від A до B включно.

 

Вхідні дані

 

У єдиному рядку вводяться два числа 1 ≤ A≤ B≤ 100000.

 

Вихідні дані

 

Вивести в один рядок всі прості числа в інтервалі від A до B включно.

 

Input example

 

Sample 1

 

2 2

 

Sample 2

 

1 100

 

Output example

 

Sample 1

 

2

 

Sample 2

 

$12        3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

 

 

 

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

 

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

 

Два підрядки

 

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

 

Вхідні дані

 

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

 

Вихідні дані

 

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

 

приклади тестів

 

вхідні дані

 

ABA

 

вихідні дані

 

NO

 

вхідні дані

 

BACFAB

 

вихідні дані

 

YES

 

вхідні дані

 

AXBYBXA

 

вихідні дані

 

NO

 

Примітка

 

У першому прикладі вхідних даних, незважаючи на те, що є підрядка "AB" і "BA", їх входження перетинаються, тому відповідь - "NO".

 

У другому прикладі вхідних даних є наступні входження подстрок: BACFAB.

 

У третьому прикладі немає ні підрядка "AB", ні підрядка "BA".

 

Для додаткового опрацювання

 

$11.      Турнір Базові структури алгоритмів http://134.249.159.199/cgi-bin/new-client?contest_id=23

 

Логін school01-2016-school10-2016. Пароль 1.

 

Зауваження.

 

Структурапрограми

#include "iostream"
#include <math.h>
using namespace std;
int main()
{
int a,b;

double c;
cin>>a>>b;
c=a/b;
cout.precision(2);
cout<<fixed<<c<<endl;
}

Заокруглення

double r;
cout.precision(2);
cout<<fixed<<r<<endl;

Роботазфайлами

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

 

 

 

$12.      Турнір Методика складання алгоритмів http://134.249.159.199/cgi-bin/new-client?contest_id=24  

 

Логін school01-2016-school10-2016. Пароль 1.

 

Зауваження.

 

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

 

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

 

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

 

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

 

$1-          Перебір

 

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

 

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

 

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

 

$13.      Всеукраїнськ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

#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;

}

Задача DEMO_B

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

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

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

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

#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;

}

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

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

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

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

#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;

}

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

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

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

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

#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;

}

Задача DEMO_E

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

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

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

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

#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;

}

Задача 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 

#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;

}

 

Додатково

 

ІІ етап Всеукраїнської учнівської олімпіади з інформатики (м.Луцьк) 2015-2016н.р.  - http://134.249.159.199/cgi-bin/new-client?contest_id=21

 

Логін school01-2016-school10-2016. Пароль 1.