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

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

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

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=59

school2018-1school2018-30

пароль 1

 

Розвязки

Проста задача?

Time limit: 1c

Memory limit: 64m

reeWorld любить садити Таріка. Якось reeWorld задав Таріку дуже цікаву задача.

На здивування Тарік зробив її достатньо швидко, тому reeWorld вирішив знову все узагальнити.

Чи справитесь з новою задачею ви?

Вхідні дані:

В першому рядку задано 1<=T<=20 - кількість груп тестів.

В наступних T рядках знаходиться по одному числу 1<=A_i<=10^18.

Вихідні дані:

Для кожного заданого чила необхідно перевірити парність кількості дільників.

В кожному окремому рядку необхідно вивести Yes, якщо кількість дільників даного числа непарна, або No, якщо кількість дільників парна.

Приклад 1:

4

1

3

4

7

--------

Yes

No

Yes

No

#include <fstream>
#include <math.h>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

int main()
{
        int t;
        cin>>t;

        while(t)
        {
                long long a, b;
                cin>>a;
                b = sqrt((double)a);

                if(b*b==a || (b+1)*(b+1)==a)
                {
                        cout<<"Yes\n";
                }else
                {
                        cout<<"No\n";
                }

                t--;
        }
        return 0;
}


Точки на прямій

Timelimmit: 1c

MemoryLimit: 64m

Визначемо діаметр мультимножини(набору) точок на прямій як максимальна відстань між двома точками цієї мультимножини(набору).

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

Задано N точок. Яку мінімальну кількість точок потрібно видалити, щоб діаметр мультимножини точок які залишилися не перевищував d.

Вхідні дані:

В першому рядку задано два цілих числа N і d(1 ≤ n ≤ 100, 0 ≤ d ≤ 100) - кількість точок і обмеження на діаметр.

В другому рядку задано N чисел(1 ≤ Xi ≤ 100) - координати точок.

Вихідні дані:

Одне число - мінімальна кількість точок, які потрібно видалити.

Приклад 1:

3 1

2 1 4

------

1

Приклад 2:

3 0

7 7 7

------

0

Приклад 3:

6 3

1 3 4 6 9 10

------

3

Пояснення:

В першом тесті вигідно видалити точку з координатою 4. Новий діаметр буде рівний 2-1=1.

В другому тесті діаметр одразу рівний 0.

В третьому вигідно видалити точки з координатами 1, 9 і 10.

#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

int main()
{
        int n, m[105], ma = -1000000, mi = 100000, i, tr = 10000, d, j;

        cin >> n >> d;
        for (i = 0; i < n; i++)
        {
                cin >> m[i];
                ma = max(ma, m[i]);
                mi = min(m[i], mi);
        }

        if (ma - mi <= d)
        {
                cout << 0;
                return 0;
        }

        sort(m, m + n);

        for (i = 0; i < n; i++)
        {
                for (j = i; j < n; j++)
                {
                        if (m[j] - m[i] > d)
                        {
                                break;
                        }
                }
                tr = min(tr, n - (j - i));
        }

        cout << tr;

        return 0;
}


Ізіч

Time limmit: 1c

Memory Limit: 64m

*Наші тести не готові. Скоро 3 тур. Але ж головна ціль авторів контеста - зробити ще одну задачу.*

Дехто з ніком reeWorld хотів дати задачу на цетроїдну декомпозицію. Нехай задано граф, який є деревом.

Очевидно, що в такому графі всі вершини, крім листків, є шарнірами. Центроїдом даного графа буде такий шарнір, який розділяє даний граф на компонент-зв'язності розмірами в 2 і більше разів меншими ніж початковий.

Отже, постало Q запитань. Скільки серед заданих N чисел менших за A_i.

Вхідні дані:

В першому рядку знаходиться число 5<=N<=100000 - кількість заданих чисел.

В другому рядку знаходяться задані числа 0<=M_i<=1000000007.

В наступному рядку знаходиться кількість запитів 5<=Q<=100000.

В наступних Q рядках знаходяться по одному числу 0<=A_i<=1000000007.

Вихідні дані:

Для кожного i-ого запиту необхідно вивести кількість заданих чисел менших за A_i.

Приклад:

10

2 4 13 14 16 12 4 12 15 10

10

16

3

9

1

0

10

14

11

6

16

-----------------------

9

1

3

0

0

3

7

4

3

9

#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <time.h>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

//ofstream dat("dat1.txt");
//ofstream ans("ans1.txt");

#define N 100
#define Q 10
#define MOD 10007
//#define MOD 1000000007

vector<int> v;
set <pair<int, int> > s;
set <pair<int, int> >::iterator it;

int main()
{
        srand(time(NULL));

        if (1)
        {
                int n, i, a, q;

                cin >> n;
                for (i = 1; i <= n; i++)
                {
                        cin >> a;
                        v.push_back(a);
                }

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

                for (i = 0; i < n; i++)
                {
                        s.insert(make_pair(v[i], i));
                }

                cin >> q;

                for (i = 0; i < q; i++)
                {
                        cin >> a;
                        it = s.lower_bound(make_pair(a, -1));

                        if (it == s.end())
                        {
                                cout << n << "\n";
                        }
                        else
                        {
                                cout << it->second << "\n";
                        }
                }

                return 0;
        }
        else
        {
                /*long long i, j, a, b;
                dat << N<<"\n";
                for (i = 0; i < N; i++)
                {
                        a = rand()*rand()*rand()%MOD + rand() - rand();
                        a %= MOD;
                        if (a < 0) { a += MOD; }
                        dat << a<<" ";
                }
                dat << "\n" << Q << "\n";

                for (i = 0; i < Q; i++)
                {
                        a = rand()*rand()*rand() % MOD + rand() - rand();
                        a %= MOD;
                        if (a < 0) { a += MOD; }
                        dat << a << "\n";
                }*/
        }
}


 

Рядочки

Time limit: 1c

Memory limit: 64m

Вам задано рядок довжиною від 4 до 5000 символів, який складається лише з малих літер анлійського алфавіту.

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

Вхідні дані:

В єдиній стрічці знаходиться вхідний рядок.

Вихідні дані:

Виведіть Yes, якщо рядок можна розділити на 4 непусті паліндроми або No інакше.

Приклад 1:

abaaaa

------------

Yes

Приклад 2:

abacaba

------------

No

#include <fstream>

#include <algorithm>

#include <math.h>

#include <vector>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

vector <int> primeNumbers;

long long n, i, answer;

int *productComposition;

long long minAns;

bool isPrime(int number)

{

      int i;

      for (i = 2; i*i <= number; i++)

      {

            if (number%i == 0)

            {

                  return false;

            }

      }

      return true;

}

void nextProducts(unsigned long long product, int productCompositionPosition, long long numberOfDividers)

{

      for (; productComposition[productCompositionPosition - 1] > productComposition[productCompositionPosition];)

      {

            productComposition[productCompositionPosition]++;

            numberOfDividers = numberOfDividers / productComposition[productCompositionPosition] * (productComposition[productCompositionPosition] + 1);

            product *= primeNumbers[productCompositionPosition - 1];

            if (product >= n)

            {

                  break;

            }

            if (answer < numberOfDividers)

            {

                  answer = numberOfDividers;

                  minAns = product;

            }

            if (product*primeNumbers[productCompositionPosition] < n)

            {

                  nextProducts(product, productCompositionPosition + 1, numberOfDividers);

            }

      }

      productComposition[productCompositionPosition] = 0;

}

int main()

{

      answer = 1;

      cin >> n;

      //lets find all necessary prime numbers

      unsigned long long timeN = 1;

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

      {

            if (isPrime(i))

            {

                  timeN *= i;

                  primeNumbers.push_back(i);

            }

      }

      // 1 = (1^BIG) * (2^0) * (3^0) * (5^0) * (7^0)...

      productComposition = new int[primeNumbers.size() + 1];

      productComposition[0] = log2(n) + 1;

      for (i = 1; i <= primeNumbers.size(); i++)

      {

            productComposition[i] = 0;

      }

      //main search

      nextProducts(1, 1, 1);

      //lets cout answer

      cout << answer << "\n" << minAns;

      return 0;

}


Дільники

Time limmit: 1c

Memory Limit: 64m

Ви знаєте китайські теореми про остачі???

От і добре, в цій задачі вони не потрібні.

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

Вхідні дані:

Число 2<=N<=10^17

Вихідні дані:

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

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

Приклад 1:

10

-------

4

6

Приклад 2:

1000000

-------

240

720720

Пояснення

У другому прикладі є 5 чисел менших за 10^6, які мають 240 дільників: 720720, 831600, 942480, 982800, 997920.

Примітка

Якби N=10^60 то відповідь була би:

521838526464

955140758164680860628432565596792358941635407885397923872000

#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

vector <int> primeNumbers;
long long n, i, answer;
int *productComposition;
long long minAns;

bool isPrime(int number)
{
        int i;
        for (i = 2; i*i <= number; i++)
        {
                if (number%i == 0)
                {
                        return false;
                }
        }
        return true;
}

void nextProducts(unsigned long long product, int productCompositionPosition, long long numberOfDividers)
{

        for (; productComposition[productCompositionPosition - 1] > productComposition[productCompositionPosition];)
        {
                productComposition[productCompositionPosition]++;
                numberOfDividers = numberOfDividers / productComposition[productCompositionPosition] * (productComposition[productCompositionPosition] + 1);
                product *= primeNumbers[productCompositionPosition - 1];
                if (product >= n)
                {
                        break;
                }

                if (answer < numberOfDividers)
                {
                        answer = numberOfDividers;

                        minAns = product;
                }
                if (answer == numberOfDividers)
                {
                        if (minAns>product)
                        {
                                minAns = product;
                        }
                }

                if (product*primeNumbers[productCompositionPosition] < n)
                {
                        nextProducts(product, productCompositionPosition + 1, numberOfDividers);
                }
        }
        productComposition[productCompositionPosition] = 0;
}

int main()
{
        answer = 1;
        cin >> n;

        //lets find all necessary prime numbers
        unsigned long long timeN = 1;
        for (i = 2; timeN < n; i++)
        {
                if (isPrime(i))
                {
                        timeN *= i;
                        primeNumbers.push_back(i);
                }
        }

        // 1 = (1^BIG) * (2^0) * (3^0) * (5^0) * (7^0)...
        productComposition = new int[primeNumbers.size() + 1];
        productComposition[0] = log2(n) + 1;
        for (i = 1; i <= primeNumbers.size(); i++)
        {
                productComposition[i] = 0;
        }

        //main search
        nextProducts(1, 1, 1);

        //lets cout answer
        cout << answer << "\n" << minAns;

        return 0;
}


Гроб

Time limmit: 1c

Memory Limit: 64m

*reeWorld вирішив що 5 ізічів на один контест вже і так достатньо, тому добавив ще один.*

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

У нього є безліч плиток Г-подібного троміно. Йому потрібно замостити кімнату розміроv 4*3N.

Скількома способами він може це зробити?

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

Проте, ви то точно вмієте виводити формулу в послідовності :) gggl

Вхідні дані:

Одне число 1<=N<=10^18

Вихідні дані:

Кількість можливих замощень кімнати.

Оскільки відповідь може бути достатньо великою, потрібно вивести її по модулю 1000000007

#include <fstream>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");

#define MOD 1000000007

struct mat
{
        long long a[3][3];
};

mat mult(mat a, mat b)
{
        mat c;
        long long i, j, l;
        for(i=0;i<3;i++)
        {
                for(j=0;j<3;j++)
                {
                        c.a[i][j]=0;
                        for(l=0;l<3;l++)
                        {
                                c.a[i][j]+=a.a[i][l]*b.a[l][j];
                                c.a[i][j]%=MOD;
                        }
                }
        }

        return c;
}

mat sqr(mat a)
{
        return mult(a, a);
}

mat binpow(mat a, long long n)
{
        if(n==1)
        {
                return a;
        }else if(n%2==0)
        {
                return sqr(binpow(a, n/2));
        }else
        {
                return mult(sqr(binpow(a, n/2)), a);
        }
}

int main()
{
        long long n, i, j;

        cin >> n;

        if(n==1)
        {
                cout<<4;
                return 0;
        }else if(n==2)
        {
                cout<<18;
                return 0;
        }else if(n==3)
        {
                cout<<88;
                return 0;
        }

        mat m;

        m.a[0][0] = 0; m.a[0][1] = 0; m.a[0][2] = -4;
        m.a[1][0] = 1; m.a[1][1] = 0; m.a[1][2] = -22;
        m.a[2][0] = 0; m.a[2][1] = 1; m.a[2][2] = 10;

        mat res = binpow(m, n-3);

        long long result = res.a[0][2]*4 + res.a[1][2]*18 + res.a[2][2]*88;
        result%=MOD;

        cout<<result;

        return 0;
}

 
ІІІ етап Всеукраїнської олімпіади з інформатики 2017-2018 PDF Печать E-mail
Добавил(а) Administrator   
07.02.18 21:08

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

Протоколи олімпіади

Завдання 1 туру

Завдання 2 туру


 

Дорозв'язування олімпіади


Сайт:http://sbs2.km.ua/olymp/ 

!!!Таблиця з логінами і  паролями!!!

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

ІІІ (обласний) етап олімпіади з інформатики 3-4 лютого 2018 року  (І та ІІ тури)

Матеріали олімпіад минулих років

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

Турніри для тестування

Логін

Пароль

Точка входу

school2017-1

...

school2017-30

1

http://134.249.159.199/cgi-bin/new-client?contest_id=23

http://134.249.159.199/cgi-bin/new-client?contest_id=24

http://134.249.159.199/cgi-bin/new-client?contest_id=41

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

http://134.249.159.199/cgi-bin/new-client?contest_id=56

 

Задачі на  E-Olymp

https://www.e-olymp.com/ru/problems/7234

https://www.e-olymp.com/ru/problems/4288

https://www.e-olymp.com/ru/problems/7401

https://www.e-olymp.com/ru/problems/7239

https://www.e-olymp.com/ru/problems/7343

https://www.e-olymp.com/ru/problems/5207

https://www.e-olymp.com/ru/problems/491

https://www.e-olymp.com/uk/problems/1608

https://www.e-olymp.com/uk/problems/491

https://www.e-olymp.com/uk/problems/621

https://www.e-olymp.com/uk/problems/2709

https://www.e-olymp.com/uk/problems/4728

 

 

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

http://134.249.159.199/cgi-bin/new-client?contest_id=23

Логін school2016-1 . . . school2016-10  (пароль - 1)

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=24

Логін school2016-1 . . . school2016-10  (пароль - 1)

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

Логін school2016-1 . . . school2016-10  (пароль - 1)

http://134.249.159.199/cgi-bin/new-client?contest_id=22

Логінschool1-school10 (пароль - 1)

http://134.249.159.199/cgi-bin/new-client?contest_id=14

Логін school2016-1 . . . school2016-10  (пароль - 1)

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

Логін school2016-1 . . . school2016-10  (пароль - 1)

 
Заняття 6 (11.10.2017) PDF Печать E-mail
Добавил(а) Administrator   
13.10.17 10:28

Теорія графів (скачати)

Codeforces  (http://codeforces.com/)

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

Два підрядка

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

Вхідні дані

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

Вихідні дані

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

$11.      Турнір http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=11

Задачі А

Неуважність

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

Input format

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

Output format

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

Examples

Input in text.in

Output in text.out

sCHOOL

School

Задача F

Арифметика

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

Input format

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

Output format

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

Examples

Input in count.in

Output in count.out

1233

3

 

 

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

Основні алгоритми роботи з графами:

http://www.e-olymp.com/uk/problems/4764 - Матриця суміжності, степінь вершин

http://www.e-olymp.com/uk/problems/4763 - Від списку ребер до матриці суміжності

http://www.e-olymp.com/uk/problems/625 - Пошук в глибину на графах

http://www.e-olymp.com/uk/problems/975  - Флойд (зчитування матриці)

http://www.e-olymp.com/uk/problems/983 - Флойд (створення матриці)

http://www.e-olymp.com/uk/problems/2968Флойд (Форд)

http://www.e-olymp.com/uk/problems/1365 -  Дейкстри

http://www.e-olymp.com/uk/problems/2965 -   Дейкстра

http://www.e-olymp.com/uk/problems/981 - мінмальне остове дерево (алгоритм Прима)

http://www.e-olymp.com/uk/problems/964 - Матриця інцендентності

 
Заняття 5 (04.10.2017) PDF Печать E-mail
Добавил(а) Administrator   
13.10.17 10:23

 Codeforces  (http://codeforces.com/)

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

Два підрядка

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

Вхідні дані

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

Вихідні дані

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

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

1.     Фрагменти програмних кодів (С++)

Завдання

Програмний код

$11.               

Зчитування до кінця рядка

while (cin.peek()!='\n')

 { n++;

cin>>a[n];

 }

$12.               

Зчитування до кінця файлу

while (!cin.eof())

 { m++;

cin>>b[m];

 }

$13.               

Зчитування рядка з пропусками

string str;

getline(cin,str,'\n');

$14.               

Зчитування рядка з пропусками (тип string)

#include "fstream"

#include "string.h"

#include "string"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{string s;

getline(cin,s);

cout<<s;

}

$15.               

Зчитування рядка з пропусками (тип char)

#include "fstream"

#include "string.h"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{char str[100];

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

cout<<str;

}

$16.               

Кількість цифр в числі

#include "string"

int main()

{string s;

cin>>s;

cout<<s.length();}

 

#include "iostream"

#include "math.h"

using namespace std;

int main()

{

unsigned long long number;

cin>>number;

cout.precision(0);

cout<<fixed<<log10(double (number))+1;

}

 

2.    Функції для роботи з рядками

Більшість функцій для роботи з рядками містяться в бібліотеці cstring .(#include <cstring>)

Функція

Дія

memset(str, c, n)

перші n символів рядка str заповнює значеннями c

strnset(str, c, n)

перші n символів рядка str заповнює значеннями c

strlen(str)

визначення довжини рядка

strcpy(str1, str2)

в рядок str1 копіює рядок str2

strncpy(str1, str2, n)

в рядок str1 копіює не більше, ніж n символів рядка str2

strcat(str1, str2);

до рядка str1 дописує рядок str2

strncat(str1, str2, n)

до рядка str1 дописує не більше, ніж n символів рядка str2

strchr(str, c)

визначає перше входження літери c  в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)

strrchr(str, c)

визначає останнє входження літери c  в рядок str; повертає вказівник на знайдену літеру (або NULL, якщо її нема)

strstr(str1, str2)

визначає перше входження підрядка str2 в рядок str1; повертає вказівник на першу літеру знайденого підрядка (або NULL, якщо він не зустрічається)

strrev(str)

записує рядок str у зворотному порядку

strupr(str)

перетворює всі літери рядка у великі літери

strlwr(str)

перетворює всі літери рядка у малі літери

strcmp(str1, str2)

порівнює рядки str1 та str2; якщо рядки рівні, то повертає 0;

якщо відмінні – то повертає різницю між першими відмінними літерами: с1 – с2

stricmp(str1, str2)

аналогічна до strcmp(...), тільки ігнорує величину літер

strcspn(str1,str2)

повертає число – позицію першого входження в рядок str1 символу  із набору str2

strdup(str1)

розподіляє пам’ять і копіює рядок str1 за виділеною адресою; повертає адресу початку виділеної пам’яті

Приклади:

strcmp("abcdefgh","abcabc") = 3;

stricmp("Abcd","abcD")       = 0;

strlen("alpha")                    = 5;

cout<<strchr("University", 'v')          –>  "versity";

cout<<strstr("MicroLab Studio", "Lab")   –> "Lab Studio";

cout<<strupr("My first Program")               –> "MY FIRST PROGRAM".

 

Робота з масивами

Операція з масивом

Лінійний масив

Прямокутна таблиця

Опис

int a[100];

int i, n;//індекс, кількість елементів

int a[100][100];

int i,j, n,m;//індекс, кількість елементів

Введення

cin>>n;

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

cin>>n>>m;

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

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

cin>>a[i][j];

Виведення

for(i=0;i<n;i++)cout<<a[i]<<” “;

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

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

cout<<a[i][j]<<” “;

Сумування

s=0;

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

s=0;

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

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

s=s+a[i][j];

Пошук

cin>>k;

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

cin>>k;

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

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

if (a[i][j]==k)

cin<<i<<” “<<j;

Пошук максимального

max=a[0];nmax=0;

for(i=1;i<n;i++)if  (a[i]>max) {max=a[i];nmax=i;}

max=a[0][0];imax=1;jmax=1;

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

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

if  (a[i][j]>max) {max=a[i][j];

imax=i;jmax=j;}

Сортування

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

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

if  (a[j]>a[j+1])

{temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;}

 

Стирання

n=n-1;

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

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

 

Вставка

n=n+1;

for(i=n-1;i>k;i--)

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

a[k]=x;

 
 
Заняття 4 (27.09.2017) PDF Печать E-mail
Добавил(а) Administrator   
13.10.17 10:21

Заняття 4. Структура циклу

Повторення

Розгалуження

https://www.e-olymp.com/uk/problems/905 (Трикутник)

https://www.e-olymp.com/uk/problems/918  (Координатна чверть)

https://www.e-olymp.com/uk/problems/911 (Квадратне рівняння)

Структура циклу

https://www.e-olymp.com/uk/problems/910 (Середнє арифметичне додатних)

https://www.e-olymp.com/uk/problems/908 (Ті що діляться на 6)

https://www.e-olymp.com/uk/problems/906 (Добуток цифр)

https://www.e-olymp.com/uk/problems/7338 (Постійна сума)

Масиви

Задачі

Сортування часу - http://www.e-olymp.com/uk/problems/972

Велике сортування - http://www.e-olymp.com/uk/problems/973

Хитре сортування - http://www.e-olymp.com/uk/problems/1462

Багатокутникиhttp://www.e-olymp.com/uk/problems/2987

Два массиваhttp://www.e-olymp.com/uk/problems/2099

Результати олімпіадиhttp://www.e-olymp.com/uk/problems/1962

Фібоначі https://www.e-olymp.com/uk/problems/1378

Теорія

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

1)      Бульбашка

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

3)      Швидке

4)      Вектором

 
Заняття 3 (20.09.2017) PDF Печать E-mail
Добавил(а) Administrator   
22.09.17 07:52

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

Приклад 1

Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в  даній послідовності.

1 спосіб.

Посортувати і відшукати  різницю, рівну два між сусідніми елементами.

n=5

0 2 1 5 3

0 1 2 3 5

4

2 спосіб.

Перевірити, чи  існує кожне з чисел від 0 до N у послідовності, використовуючи два вкладених цикли.

3 спосіб.

Скористатися формулою суми арифметичної прогресії.

Приклад:

N=5;

Послідовність А[1..N]  4 2 3 0 5

Сума елементів послідовності рівна S1=4+2+3+0+5=14

Сума арифметичної прогресії (0..N) 0 1 2 3 4 5 згідно з формулоюS=(An+A1)*n/2

S2=(5+0)*15/2

Результат R=S2-S1=15-14=1

Отже, не існує числа 1.

Приклад 2

                Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.

Спосіб 1

Кожне наступне знаходити як суму двох попередніх.

1 1 2 3 5 8 ...

k1 перше число

k2 друге число

k3:=k1+k2;

k1:=k2;

k2:=k3;

Спосіб 2

Використаємо рекурентну формулу  чисел Фібоначі.

 F_n = \frac{ \left( \frac{1+\sqrt{5}}{2} \right)^[...]

http://e-maxx.ru/algo/fibonacci_numbers

 

Кожне число Фібоначі знаходять за формулою:

xy exp(y*ln(x))

Приклад 3

Перестановка значення змінної місцями

a,b 2,3 3,2

c=a;a=b;b=c;

c=2;a=3;b=2;

a=a+b; b=a-b; a=a-b;

a=5;b=5-3=2;a=5-2=3;

2.    Розгалуження

Приклад 3

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

Існують різні способи розв’язку даного завдання

1 спосіб 

var a,b,c,max:integer;

begin

readln(a,b,c);

if (a>=b && a>=c) max=a;

if (b>=a)and(b>=c) then max:=b;

if (c>=a)and(c>=b) then max:=c;

writeln(max);

end.

2 спосіб

Вкладені розгалуження

IF умова THEN IF умова THEN оператори ELSE оператори ELSE оператори

var a,b,c,max:integer;

begin

readln(a,b,c);

if a>b then if a>c then max:=a else max:=c else if b>c then max:=b else max:=c;

writeln(max);

end.

3 спосіб

var a,b,c,max:integer;

begin

readln(a,b,c);

max:=a;

if b>max then max:=b;

if c>max then max:=c;

writeln(max);

end.

Третій спосіб найраціональніший

 

C++

max(a, max(b,c);


 

3.   Цикл

Приклад 3

                Знайти найбільший спільний дільник

 (HCD)  a,b,

 HCD(0,0)=0

 HCD(a,0)=(a)

HCD(а,в)=HCD(b,r1)=HCD(r1,r2)=HCD(rn-1,rn)=|rn-1|, де rі- остача від ділення?

 Знайти найменше спільне кратне (HCD) цілиx чисел аШ0,вШ0

                HCK(a,b)=a*b/HCD(a,b)

 HCD(а,в)=HCD(b,r1)=HCD(r1,r2)=HCD(rп-1,rn)=|rn-1| 

     4.Знайти досконалі числа на проміжну [1,n].

6=1+2+3 (досконале - рівне сумі всіх своїх дільників, крім останнього)

45 15  ------- 2 3 4 5 6 7 8 9 10 11 12 13 14 15

45 % 15=0

15

15 25

  1. b

15%25=25

25 % 15=10

15 %10 =5

10%5=0

5

0

while (b>0)

{temp=a%b;

a=b;

b=temp;

}

nsd=a

Алгоритм Евкліді

Приклад 4

Знайти дільники числа.

Знайти кількість дільників числа.

 

Практикум

$11.   Фібоначі

Турнір «Методика складання алгоритмів – 24» Задача B

$12.   НСД.

https://www.e-olymp.com/uk/problems/137

https://www.e-olymp.com/uk/problems/136

https://www.e-olymp.com/uk/problems/7239

https://www.e-olymp.com/uk/problems/4742

https://www.e-olymp.com/ru/problems/4283

Последнее обновление 22.09.17 08:01
 


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

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 108447

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

Нет