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

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

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

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

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

№

Завдання

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

1.                 

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

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

 { n++;

cin>>a[n];

 }

2.                 

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

while (!cin.eof())

 { m++;

cin>>b[m];

 }

3.                 

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

 
string str;

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

 

4.                 

Зчитування рядка з пропусками (тип 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;

}

 

5.                 

Зчитування рядка з пропусками (тип 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;

}

 

6.                 

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

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

 

 

 

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

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

№

Завдання

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

1.                 

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

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

 { n++;

cin>>a[n];

 }

2.                 

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

while (!cin.eof())

 { m++;

cin>>b[m];

 }

3.                 

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

 
string str;

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

 

4.                 

Зчитування рядка з пропусками (тип 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;

}

 

5.                 

Зчитування рядка з пропусками (тип 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;

}

 

6.                 

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

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

 

 
 
Заняття 9 (02.11.2016) PDF Печать E-mail
Добавил(а) Administrator   
29.11.16 09:37

Опорний конспект по с++

№

Завдання

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

1.                  

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

#include "iostream"
#include <math.h>
using namespace std;
int main()
{
double a,b,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");

2.                  

Заокруглення кількості знаків після коми

double a;   a=3.14

cout.precisio(2);

cout<<fixed<<a<<endl;

3.                  

Обчислити площу трикутника за координатами

#Include “iostream”;

#Include “math.h”;

using namespace std;

int mail()

{double x1,y,x2,y2,x3,y3,a,b,c,p,s;

cin>>x1>>y1>>x2>>y2>>x3>>y3;

a=sqrt(pow(x2-x1,2)+pow(y2-y1,2));

b=sqrt(pow(x3-x2,2)+pow(y3-y2,2));

c=sqrt(pow(x3-x1,2)+pow(y3-y1,2));

p=(a+b+c)/2;

s=sqrt(p*(p-a)*(p-b)*(p-c));

cout.precisio(2);

cout<<fixed<<s<<endl;

}

4.                  

Зчитати n чисел

int  n,a[1000];

cin>>n;

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

5.                  

Зчитати рядок з n чисел

int  n,a[1000];

n=0;

while (! cin.eof())

{cin>>a[n];  n++;

}

6.                  

Зчитати рядок цифр і вивести його в зворотному порядку

char  a[1000];

cin>>a;

for(int i=strlen(a)-1; i>=0;i--)cout<<a[i];

7.                  

Вивести масив з n чисел через пропуск

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

cout<<a[n-1[<<endl;

8.

Підрахувати суму цифр в числі

long long n,s;

cin>>n;

s=0;

while (n>0) {

s=s+n%10;

n=n/10;

}

char a[1000];

cin>>a;

int s=0;

for(int i=0;i<strlen(a);i++)

s=s+a[i]-48;

cout<<s<<endl;

9.                  

Підрахувати кількість кожної цифри в числі

long long n;

cin>>n;

int a[10]

while (n>0)

{a[n%10]++;

n=n/10;

}

for(int i=0;i<=9;i++)

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

char a[1000];

cin>>a;

int b[10];

for(int i=0;i<=9;i++) b[i]=0;

for(int i=0;i<strlen(a);i++)

b[a[i]-48]++;’

for(int i=0;i<=9;i++)

cout<<i<<” “<<b[i]<<endl;

10.               

Відсортувати масив в порядку зростання

int a[100000], j, i;

cin>>n;

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

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

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

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

swap(a[j],a[j+1];

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

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

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int i,j,n;

int main()

{cin>>n;

vector<int> a(n);

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

}

11.               

Обчислити суму додатних елементів в парних рядках прямокутної таблиці

int main()

{int n,m,i,j,a[100][100];

cin>>n>>m;

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

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

cin>>a[i][j];

int s=0;

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

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

if(a[i][j]>0 && i%2==0)s=s+a[i][j];

cout<<s<<endl;

}
         
 
Заняття 8 (26.10.2016) PDF Печать E-mail
Добавил(а) Administrator   
29.11.16 09:35

Повторення

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

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

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

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

Опис

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

  

Сортування

swap

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

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

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

swap(a[j],a[j+1]);

  

Сортування

sort

#include <iostream>

#include <algorithm>

int a[100],n;

using namespace std;

int main()

{cin>>n;

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

sort(a,a+n);

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

    cout <<endl;

    return 0;

}

  

Стирання

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;

  

Перебір

#include <iostream>

#include <fstream>

#include <math.h>

#include <vector>

#include <algorithm>

using namespace std;

vector <int> a;

 ifstream f;

 ofstream g;

void printper(int n);

int main()

{

    f.open("input.dat");

    g.open("output.ans");

    int n;

    f >> n;

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

        a.push_back(i);

    }

    printper(n);

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

        printper(n);

    };

    //printper(n);

    f.close();

    g.close();

    return 0;

}

void printper(int n)

{

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

        g << a[i] << " ";

    }

    g << a[n-1] << endl;

}

  
 
Заняття 7 (19.10.2016) PDF Печать E-mail
Добавил(а) Administrator   
29.11.16 09:34

$11.     Динамічне програмування . Купування квитків

Ім'я файлу програми:

Bilet.*

Ім'я вхідного файлу:

Bilet.dat

Ім'я вихідного файлу:

Bilet.dat

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

5 секунд

Максимальна оцінка за завдання:

100 балів

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

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

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків — Bi секунд, трьох квитків — Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

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

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

У вхідному файлі записано спочатку число N — кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

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

У вихідний файл виведіть одне число — мінімальний час в секундах, за яке могли бути обслужені всі покупці.

 

Приклади

Bilet.dat

Bilet.sol

5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

12

2

3 4 5

1 1 1

4

N=5

i

Ai

Bi

Ci

1

5

10

15

2

2

10

15

3

5

5

5

4

20

20

1

5

20

1

1

D[i]= min ( D[i-1]+Ai,  D[i-2]+ Bi-1,  D[i-3]+ Ci-2 )

D[1]

D[2]

D[3]

D[4]

D[5]

5

7

5

6

12 – відповідь завдання

d[0]= 0;

d[1]= а[1];

d[2]= Мінімальне(а[1]+a[2], b[1]);

Для i від 3 до n  пц

d[i]= Мінімальне(d[i-1]+ а[i],Мінімальне(d[i-2]+ b[i-1], d[i-3]+ с[i-2]));

 

Задача 2. На квадратному аркуші паперу в клітинку розміром NхM клітинок намальовано кілька прямокутників. Кожен прямокутник складається з цілих клітинок, різні прямокутники накладаються один на одного.

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

Вхідні дані

В першому рядку N, розмір масиву, в наступних n рядків  масиву, в кожному з яких написані через пробіл n елементів масиву: A [елемент I, J] = 1, якщо клітина [I, J] належить будь-якому прямокутника, і A [I, J ] = 0, в іншому випадку.

Вихідні дані

Необхідно вивести єдине число - кількість прямокутників.

#include <iostream>

using namespace std;

 int a[100][100];

int main()

{

int n,m;

cin>>n>>m;

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

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

    cin>>a[i][j];

int k=0;

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

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

    if (a[i][j]==1)k++;

     cout<<k<<endl;

        return 0;

}

Задача 3.  "Прямокутники" На квадратному аркуші паперу в клітинку розміром NхN клітин намальовано кілька прямокутників. Кожен прямокутник складається з цілих клітинок, різні прямокутники не накладаються один на одного і не дотикаються.

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

Вхідні дані

В першому рядку N, розмір масиву, в наступних n рядків  масиву, в кожному з яких написані через пробіл n елементів масиву: A [елемент I, J] = 1, якщо клітина [I, J] належить будь-якому прямокутника, і A [I, J ] = 0, в іншому випадку.

Вихідні дані

Необхідно вивести єдине число - кількість прямокутників.

#include <fstream>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

    int a[100][100];

int main()

{

int n;

cin>>n;

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

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

    cin>>a[i][j];

int k=0;

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

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

    if (a[i][j]==1 && a[i+1][j]==0 &&a[i][j+1]==0 && a[i+1][j+1]==0)k++;

     cout<<k<<endl;

        return 0;

}


Задача 4. 

Мишка i зернинки

В iндiйському храмi пiдлогу прямокутної форми вимощено однаковими квадратними плитками 1х1, на кожну з яких  насипано вiд 0 до N зернинок (N<30000). Розмiри пiдлоги АхВ. Мишка вибiгає з лiвого нижнього кута пiдлоги  храму i рухається до входу у iншу нiрку, розмiщену у протилежному кутку. Мишка може рухатись лише вправо або вперед, забираючи всi зернинки з клiтини, в                якiй вона знаходиться. Потрiбно:

а)     знайти кiлькiсть можливих маршрутiв руху мишки:

б)     знайти маршрут, рухаючись по якому мишка збере найбiльшу кiлькiсть зернин.

Вхiдний файл MOUSE.DAT у першому рядку мiстить числа А та В – розмiри  пiдлоги (1£A,B£100 ). Далi йде А рядкiв, у кожному з яких розмiщено В чисел – кiлькiсть  зернинок  на вiдповiднiй плитцi.

Програма MOUSE.* повинна вивести на екран  та  записати у  файл MOUSE.SOL у перший рядок кiлькiсть можливих  маршрутiв, у другий  рядок – найбiльшу  кiлькiсть зернинок, що може зiбрати мишка, у третiй рядок – маршрут руху  мишки  у  формi  ППВВВПВ  (В – крок вперед, П – крок вправо).

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

    MOUSE.DAT                                                 MOUSE.SOL

    2 3                                                                                    3

    3 2 4                                                                                 12

    1 5 1                                                                                 ПВП

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

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

a[i][j]=max(a[i][j]+a[i-1][j], a[i][j]+a[i][j-1])

3 тур - з 31.10 по 06.11.2016

точка входу для відправлення розв'язків http://134.249.159.199//cgi-bin/new-client?contest_id=35

Задача 1. Мега реклама (20 балів)

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

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

Ліміт часу: 1с.

На дошці наклеєно декілька листів оголошень. Всі вони прямокутної форми. Деякі листи накладаються частково або повністю. Усі горизонтальні та вертикальні сторони строго взаємо паралельні. Листи, які частково накладаються утворюють многокутник.

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

Вхідні дані

У першому рядку вхідного файлу записано число N - кількість прямокутників. В наступних N рядках записано числа x1 y1 x2 y2 - декартові координати нижнього лівого та правого верхнього кутів прямокутника. Всі координати - цілі числа що по модулю не перевищують 10000.

Вихідні дані

У вихідний файл потрібно записати суму периметрів утворених геометричних фігур (прямокутників, многокутників).

Приклад

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

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

7

-15 0 5 10

-5 8 20 25

15 -4 24 14

0 -6 16 4

2 15 10 22

30 10 36 20

34 0 40 16

228

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int a[2000][2000];

int main()

{

                int s,k, i,j,n,xz,yz;

                cin>>n;

int *x1=new int[n+1];

int *y1=new int[n+1];

int *x2=new int[n+1];

int *y2=new int[n+1];

int maxx=-10000,maxy=-10000,minx=10000,miny=10000;

                for(k=1; k<=n; k++){

                                               cin>>x1[k]>>y1[k]>>x2[k]>>y2[k];

                                               if (x1[k]<minx) minx=x1[k];

                                               if (y1[k]<miny) miny=y1[k];

                                               if (x2[k]<minx) minx=x2[k];

                                               if (y2[k]<miny) miny=y2[k];

                                               if (x1[k]>maxx) maxx=x1[k];

                                               if (y1[k]>maxy) maxy=y1[k];

                                               if (x2[k]>maxx) maxx=x2[k];

                                               if (y2[k]>maxy) maxy=y2[k];

                }

//cout<<minx<<miny<<maxx<<maxy<<endl;

                xz=-minx+1;

                yz=-miny+1;

                minx=minx+xz;

                miny=miny+yz;

                maxx=maxx+xz;

                maxy=maxy+yz;

//cout<<minx<<miny<<maxx<<maxy<<endl;

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

        {

                               x1[k]=x1[k]+xz;

                               x2[k]=x2[k]+xz;

                               y1[k]=y1[k]+yz;

                               y2[k]=y2[k]+yz;

                                                               for(i=x1[k]+1; i<=x2[k]; i++)

                                                                              for(j=y1[k]+1; j<=y2[k]; j++)

                                                                              {a[i][j]=1;}

                               }

/*           for(i=minx;i<=maxx; i++){

                               for(j=miny; j<=maxy; j++)

                                               cout<<a[i][j]; cout<<endl;}

*/

                s=0;

                for(i=minx;i<=maxx+1; i++)

                               for(j=miny; j<=maxy+1; j++){

                               if((a[i][j]==0 && a[i+1][j]==1) || (a[i][j]==0 && a[i-1][j]==1) ||

        (a[i][j]==0 && a[i][j+1]==1) || (a[i][j]==0 && a[i][j-1]==1 )) s++;

    if((a[i][j]==0 && a[i+1][j]==1 && a[i][j+1]==1) || (a[i][j]==0 && a[i+1][j]==1 && a[i][j-1]==1) ||

        (a[i][j]==0 && a[i-1][j]==1 && a[i][j+1]==1 ) || (a[i][j]==0 && a[i-1][j]==1 && a[i][j-1]==1  )) s++;

}

                cout<<s<<endl;

                return 0;

}


Додатково

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

Логін school01-2016-school10-2016. Пароль 1.
 
Заняття 6 (12.10.2016) PDF Печать E-mail
Добавил(а) Administrator   
29.11.16 09:20

Завдання 1. Таймер (20 балів)

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

Вхідні дані

У першому рядку вхідного файлу записано поточний час в форматі Г Х С (без початкових нулів). При цьому він задовольняє обмеженням: Г - від 0 до 23, Х і С - від 0 до 60.

У другому рядку записаний інтервал часу, який повинен бути визначений. Інтервал записується в форматі Г Х  С (де Г, Х і С - від 0 до 109, без початкових нулів).

100 100 100 - 100 годин, 100 хвилин, 100 секунд, що те ж саме, що 101  41 40.

Вихідні дані

У вихідний файл виведіть в форматі Д Г Х  С час, у скільки прозвучить звуковий сигнал (де Д –кількість днів).

Приклади

input.txt

output.txt

1 1 1

48 0 0 

2 1 1 1

1 1 1

0 58 119

0 2 1 0

23 59 59

0 0 1               

1 0 0 0

#include <fstream>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{

    long long  g1,h1,s1, g2,h2,s2, d,g,h,s;

    cin>> g1>>h1>>s1>>g2>>h2>>s2;

    long long t =g1*3600+h1*60+s1+g2*3600+h2*60+s2;

    d=t/(24*3600);

    g=(t-d*24*3600)/3600;

    h=(t-d*24*3600-g*3600)/60;

    s=(t-d*24*3600-g*3600-h*60);

    cout <<d<<" "<<g<<" "<<h<<" "<<s<< endl;

        return 0;

}

Задача 2. Зернини (20 балів)

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

Вхідні дані

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

Вихідні дані

Єдиний рядок вихідного текстового файла має містити колір зернини, що залишилася: white - якщо зернина біла, black - якщо зернина чорна.

input.txt

output.txt

4 3

black

#include <iostream>

//ifstream cin("input.txt");

//ofstream cout("output.txt");

using namespace std;

int main()

{

    long long int gg,hh,ss,kk,k,g,h,s,G,H,S,sum;

    cin>>g>>h>>s;

    cin>>G>>H>>S;

    sum=(G*3600+H*60+SS)-(g*3600+h*60+s);

    ss=sum%60;

    hh=sum/60;

    gg=sum/3600;

    kk=sum/(3600*24);

    cout<<kk<<" "<<gg<<" "<<hh<<" "<<ss<<endl;

        return 0;

}

Задача 3. Паліндром (30 балів)

Перевірити чи введене N-цифрове натуральне число є паліндромом.

Вхідні дані

У єдиному рядку записано натуральне число кількість цифр до 100.

Вихідні дані

Єдиний рядок вихідного текстового файлу має містити “yes”, якщо число паліндром і “no” – якщо ні.

input.txt

output.txt

121

yes

231132

yes

123

no

#include <iostream>

#include <string.h>

using namespace std;

//ifstream cin("input.txt");

//ofstream cout("output.txt");

int main()

{

    char a[100];

cin>>a;

int f=1;

int n=strlen(a);

for (int i=0;i<n/2;i++)

    if(a[i]!=a[n-i-1])f=0;

if (f)

cout<<"yes"<<endl;

else cout<<"no"<<endl;

        return 0;

}

Задача 4.  "Прямокутники" (30 балів)

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

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

Вхідні дані

В першому рядку N, розмір масиву, в наступних n рядків  масиву, в кожному з яких написані через пробіл n елементів масиву: A [елемент I, J] = 1, якщо клітина [I, J] належить будь-якому прямокутника, і A [I, J ] = 0, в іншому випадку.

Вихідні дані

Необхідно вивести єдине число - кількість прямокутників.

input.txt

output.txt

3

0 1 0

0 1 0

0 0 0

1

3

1 1 0

0 0 0

$11         0 1

3

#include <iostream>

#include <string.h>

using namespace std;

//ifstream cin("input.txt");

//ofstream cout("output.txt");

    int a[100][100];

int main()

{

int n;

cin>>n;

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

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

    cin>>a[i][j];

int k=0;

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

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

    if (a[i][j]==1 && a[i+1][j]==0 &&a[i][j+1]==0 && a[i+1][j+1]==0)k++;

     cout<<k<<endl;

        return 0;

}

Додаткова

  1. (http://codeforces.com/)

http://codeforces.com/problemset/problem/550/A
 
Заняття 5 (05.10.2016) PDF Печать E-mail
Добавил(а) 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".
Читать полностью
 
Заняття 4 (28.09.2016) PDF Печать E-mail
Добавил(а) Administrator   
11.10.16 09:58

Заняття 4 (28.09.2016)

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

Група 1 (рівень 1).

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

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 (Постійна сума)

Група 2 (рівень 2).

Задачі

Сортування часу - 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

 

Теорія

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

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

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

$13)      Швидке

$14)      Вектором

Група 3

https://www.e-olymp.com/uk/problems/1906/ (Лампочки)

http://ejudge.itolymp.com/cgi-bin/new-client?contest_id=000092
Последнее обновление 11.10.16 09:59
 
Заняття 3 (21.09.2016) PDF Печать E-mail
Добавил(а) Administrator   
11.10.16 09:53

Заняття 3 (21.09.2016)

Завдання 1

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

Завдання 2

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

- http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=24 (завдання B )

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

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

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

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

 Додаток

 1.    Волинська учнівська Інтернет-олімпіада з програмування у 2016-2017 н. р. http://93.183.238.10/vippoolimp/.

 

2.     Повідомляємо, що а сайті http://netoi.org.ua (http://www.olymp.vinnica.ua) почалася реєстрація учасників відкритої Всеукраїнської Інтернет-олімпіади з інформатики NetOI-2016

    http://www.olymp.vinnica.ua/index_ua.php?lng=ua&amp;cid=1679
    Ви можете самі взяти в ній участь і порекомендувати це зробити тим, кого, на вашу думку, це може зацікавити.Якщо Ви школяр, обов'язково повідомте про олімпіаду своїм учителям інформатики.

3.     Школа з програмування (м. Київ)

Природничо-науковий ліцей №145 оголошує про початок роботи Київської школи олімпійського резерву з програмування. Мета школи – підготовка учнів міста Києва до олімпіад з інформатики (програмування) різних рівнів. Перше (організаційне) заняття відбудеться 24 вересня. Заняття цілком безкоштовні!

https://itolymp.com/

 

4.     Інтелектуальні змагання школярів в мережі Інтернет.
Сервіс підтримки Інтернет-олімпіади з інформаційних технологій ІОІТ-2016

5.     ІОІТ 2017

Відповідно до Положення про Всеукраїнські учнівські Інтернет-олімпіади, затвердженого наказом Міністерства освіти і науки, молоді та спорту України від 11 червня 2012 року № 671, зареєстрованого в Міністерстві юстиції України 27 червня 2012 року за № 1074/21386, наказу Міністерства освіти і науки України від 07.06.2016 №626 «Про проведення Всеукраїнських учнівських Інтернет-олімпіад з математики, фізики, хімії, біології, географії, економіки, інформатики, інформаційних технологій у 2016/2017 навчальному році» Міністерством освіти і науки України, Київським національним університетом імені Тараса Шевченка спільно зУкраїнським фізико-математичним ліцеєм КНУ імені Тараса Шевченка розпочато проведення Всеукраїнської учнівської Інтернет-олімпіади з інформаційних технологій у 2016/2017 навчальному році.

Всеукраїнська учнівська Інтернет-олімпіада проводиться у два етапи в наступні терміни:
І ( заочний) етап:30 червня – грудень 2016 року;
ІІ (очний) етап:січень – лютий 2017 року.

Реєстрація для участі в олімпіаді відбувається за цимпосиланням.

Ознайомитися із умовами реєстрації та етапами проведення олімпіади можна за посиланнямhttp://upml.knu.ua/internet-olimpiada-it-2017/
Читать полностью
 
Другие статьи...


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

Главное меню

Статистика

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

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

Нет