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

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

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

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

school2018-1school2018-30

пароль 1

Задача

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

Два підрядка

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

Вхідні дані

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

Вихідні дані

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

Три варіанти розбирав 

ABA або ВАВ і АВ або ВА

АВіВА

ВАіАВ

#include "iostream"

#include  "string.h"

using namespace std;

int main()

char *s=new char [500000];

cin>>s;

int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0;

int i=1;

while (i<strlen(s))

{

if (((s[i-1]=='B' && s[i]=='A' && s[i+1]=='B') || (s[i-1]=='A' && s[i]=='B' && s[i+1]=='A') ) && e==0) {e=1;i=i+3;}

if (((s[i-1]=='A' && s[i]=='B') || (s[i-1]=='B' && s[i]=='A'))  && e==1  )f=1;

if (s[i-1]=='A' && s[i]=='B' && a==0) {a=1;}

if (s[i-1]=='B' && s[i]=='A' && a==1)b=1;

if (s[i-1]=='B' && s[i]=='A' && c==0) {c=1;}

if (s[i-1]=='A' && s[i]=='B' && c==1  )d=1;

i++;

if (a==1 && b==1) {cout<<"YES"<<endl;return 0;} else

if (c==1 && d==1) {cout<<"YES"<<endl;return 0;} else

if (f==1 && e==1) {cout<<"YES"<<endl;return 0;}

}

cout<<"NO"<<endl;

///

return 0;

}

 
Заняття (07.03.2018) PDF Печать E-mail
Добавил(а) Administrator   
23.03.18 10:51

Завдання 1

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

Два підрядка

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

Вхідні дані

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

Вихідні дані

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

Завдання 2

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

Поворот

Задано масивn×m. Потрібно повернути його за годинниковою стрілкою на90градусів.

Вхідні дані

У першому рядку задано натуральні числаnтаm(1n,m50). У наступнихnрядках записано поmневід'ємних чисел, які не перевищують109- сам масив.

Вихідні дані

Виведіть перевернутий масив у форматі вхідних даних.

Ліміт часу1секунда

Ліміт використання пам'яті64MiB

Вхідні дані #1

3 4

1 2 3 4

5 6 7 8

9 10 11 12

Вихідні дані #1

4 3

9 5 1

10 6 2

11 7 3

12 8 4

Завдання 3 (http://kpi-open.org/tasks/ )

Недобросовісний МЕНЕДЖЕР

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

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

Вхідний файл складається з одного рядка, що містить три цілих числа, відокремлених один від одного пробілом: N - кількість міст (10 <= N <= 25000), D - відстань між містами, F - витрата палива на одиницю шляху.

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

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

Введення

Виведення

12 1 5

 

125 5 10

 

325 5 1

 

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

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

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

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

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

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

 

 
Заняття (28.02.2018) PDF Печать E-mail
Добавил(а) Administrator   
23.03.18 10:50

Вступ

Приклад 1

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

1 спосіб.

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

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 згідно з формулою

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

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

 

Математика (формули)

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

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

https://www.e-olymp.com/uk/contests/9746/problems/85777

Числові ряди (техніка написання)

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

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

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

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


Системи числення

Цікаве число

Input file name:

numbers.in

Output file name:

numbers.out

Time limit:

100 ms

Memory limit:

256 M

Степан на факультативі з програмування почав вивчати системи числення. На першому уроці вчитель розповів про систему числення з основою два, дуже популярною в комп'ютерному світі. На другому уроці Степан дізнався про систему числення з основою три. І так далі на кожному наступному уроці він дізнавався про нові системи числення, так що на i-му уроці була розглянута система числення з основою i+1.

Щоб краще запам'ятати, Степан на кожному уроці бере одне і те ж число X і записує його в зошит в останній вивченій системі числення. Приклад переведення числа 81 в систему числення з основою 6:

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

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

Формат вхідних даних. Єдиний рядок вхідного файлу містить одне ціле число X (1 ≤ X ≤ 1012) – число записане в десятковій системі числення.

Формат вихідних даних. Вихідний файл повинен містити одне ціле число B (2 ≤ B) – шукана система числення.

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

numbers.in

numbers.out

3

2

219

8

1009

1008

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

$11.       «3» – це «11» в системі числення з основою 2.

$12.       «219» – це «333» в системі числення з основою 8.

$13.       «1009» – це «11» в системі числення з основою 1008.

$1· 

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

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

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


Геометрія

Задача VIОLАТION (20 балів)

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

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

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

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

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

Приклад:

 

VIOLATION.DAT

VIOLATION.SOL

550

 

50

00

   

20

   

1 1

   

51

   

5-1

   
 

Задача FOREST

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

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

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

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

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

Приклад:

FOREST.DAT

FOREST.SOL

1 2 -2 3

1.50

 

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

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

https://www.e-olymp.com/uk/problems/1038 (Формула Піка)

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

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

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

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

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

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

Площа многокутника з цілочисловими вершинами рівна сумі

A=i+b/2-1

де i — кількість цілочислових точок усередині многокутника, b — кількість цілочислових точок на межі многокутника.

bшукаємо як НСД(x1-x2,y1-y2)

Площу за формулою

Додаткові задачі

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

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

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

 
Заняття (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 - Матриця інцендентності

 


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

Статистика

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

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

Нет