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

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

Школа олімпійського резерву з інформатики
Опорний конспект PDF Печать E-mail
Добавил(а) Administrator   
06.12.16 16:07

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

Завдання

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

 

$11.                  

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

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

 

$12.                  

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

double a;   a=3.14

cout.precisio(2);

cout<<fixed<<a<<endl;

 

$13.                  

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

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

}

 

$14.                  

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

int  n,a[1000];

cin>>n;

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

 

$15.                  

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

int  n,a[1000];

n=0;

while (! cin.eof())

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

}

 

$16.                  

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

char  a[1000];

cin>>a;

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

 

$17.                  

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

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

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

 

$18.                   1

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

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;

 

$19.                  

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

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;

 

$110.               

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

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

}

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;

}

 

$111.               

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

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;

}

 

$112.               

Перетворення числа в рядок (char)

#include <iostream>

#include <string>

#include <stdlib.h>

using namespace std;

int main()

{

    char s[100];

    cin >> s;

    int i = atoi(s);

    cout << i << endl;

    itoa(i,s,10);

    cout<<s<<endl;

        return 0;

}

 

$113.               

Перетворення чисов в рядок (string)

#include <iostream>

#include <string.h>

#include <string>

#include <cstring>

#include <stdlib.h>

using namespace std;

int main()

{string s;

cin>>s;

cout<<atoi(s.c_str())<<endl;

/*

int atoi(const char* str)

long atol(const char* str)

double atof(const char* str)

*/

    return 0;

}

 

$114.               

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

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

{ n++;

cin>>a[n];

 }

$115.               

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

while (!cin.eof())

 { m++;

cin>>b[m];

 }

$116.               

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

string str;

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

$117.               

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

}

$118.               

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

}

$119.               

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

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

}

               

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

Більшість функцій для роботи з рядками містяться в бібліотеці 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".

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

Завдання IІ етапу Всеукраїнської учнівської олімпіади

з інформатики 2016-2017 н.р.

(скачати)

Задача A. Олімпіада (100 балів)

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

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

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

З метою якісної підготовки до олімпіади з інформатики учень Степан виділив певний час кожного дня на підготовку. Допоможіть вчителю інформатики визначити загальний час який учень готовився до олімпіади.

Вхідні дані

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

Вихідні дані

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

Приклади

іnput.txt

output.txt

1

13 10 0

15 30 10

0 2 20 10

20

0 0 0

12 0 0

10 0 0 0

#include <fstream>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{

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

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

    long long t =n*(g2*3600+h2*60+s2-(g1*3600+h1*60+s1));

    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;

}

Задача B. Скарб (100 балів)

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

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

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

Знайти закопаний піратами скарб просто: все, що для цього потрібно - це карта. Як відомо, пірати зазвичай малюють карти від руки і описують алгоритм знаходження скарбу так: «Встаньте близько самотньою пальми. Пройдіть тридцять кроків у бік лісу, потім сімнадцять кроків у бік озера, ..., нарешті десять кроків у бік великого каменю. Скарб знаходиться під ним ». Велика частина таких вказівок просто зводиться до проходження якоїсь кількості кроків в одному з восьми напрямків (1 - північ, 2 - північний схід, 3 - схід, 4 - південний схід, 5 - південь, 6 - південний захід, 7 - захід, 8 -. північний захід) (див рис). Довжина кроку в будь-якому напрямку дорівнює 1.

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

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

 Вхідні дані

Перший рядок вхідного файлу містить число N - число вказівок (1≤N≤40). N Наступні рядків містять самі вказівки - номер напрямку (ціле число від 1 до 8) і кількість кроків (ціле число від 1 до 1000). Числа розділені пробілами.

Вихідні дані

У вихідний файл виведіть координати X і Y точки (два дійсних числа, розділені пробілом), де заритий скарб, вважаючи, що вісь Ox спрямована на схід, а вісь Oy - на північ. На початку скарбошукач повинен стояти на початку координат. Координати необхідно вивести з похибкою не більше 103.

Приклад

іnput.txt

output.txt

6

1 3

3 1

1 1

3 3

5 2

7 1

3.000 2.000

1

8 10

-7.071 7.071

#include <fstream>

#include <math.h>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{

    const double pi = atan(1.0)*4;

    double  X, Y,L;

    int N,D;

      cin>>N;

  X=0;

  Y=0;

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

  { cin>>D>>L;

    X=X+sin(pi/4*(D-1))*L;

    Y=Y+cos(pi/4*(D-1))*L;

  }

if (fabs(X)<0.001) X=0;

if (fabs(Y)<0.001) Y=0;

  cout.precision(3);

  cout<<fixed<<X<<" "<<Y<<endl;

        return 0;

}

{$N+,E-}

Var

  I,N:LongInt;

  D,L:LongInt;

  X,Y:Extended;

Begin

  Randomize;

  Assign(Input,'c.in');

  ReSet(Input);

  Read(N);

  X:=0;

  Y:=0;

  For I:=1 To N Do Begin

    Read(D,L);

    X:=X+Sin(Pi/4*(D-1))*L;

    Y:=Y+Cos(Pi/4*(D-1))*L;

  End;

  Close(Input);

  Assign(Output,'c.out');

  ReWrite(Output);

  WriteLn(X:0:3,' ',Y:0:3);

  Close(Output);

End.

Задача С. Дошка (100 балів)

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

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

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

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

 Скласти програму, що підраховує кількість шашок кожного кольору і що виводить результат якщо дані шашки, знаходяться у файлі (Приклад 1, Приклад 2) в першому рядку міститься кількість рядків N, в наступних N рядках записаних по рядках без пропусків у рядку і між рядками;

 результат зберігається у файлі (Приклад 1) у вигляді:

-  дані про місце розташування червоних шашок (в інших місцях знак “-“) ;

- порожній рядок;

- кількість чорних, білих, червоних і зелених шашок через пропуск;

якщо шашка якогось кольору відсутня на дошці то вивести у файл повідомлення BAD ІNPUT LІST (Приклад 2).

0 – колір і місце розташування ЧОРНОЇ шашки

1 – колір і місце розташування БІЛОЇ шашки

2 – колір і місце розташування ЧЕРВОНОЇ шашки

3 – колір і місце розташування ЗЕЛЕНОЇ шашки

 

Приклад 0:

2

1

1

0

3

0

3

1

0

1

1

3

3

1

0

0

1

2

1

3

1

0

1

2

1

1

1

1

2

2

1

0

1

1

1

0

1

2

1

2

0

1

0

1

1

2

1

1

0

0

0

0

0

0

0

0

1

1

1

2

2

2

3

3

Приклади

іnput.txt

output.txt

 

іnput.txt

output.txt

8

21103031

01133100

12131012

11112210

11101212

01011211

00000000

11122233

2-------

--------

-2-----2

----22--

-----2-2

-----2--

--------

---222—

18 28 11 7

 

8

21113131

11133133

12131112

11112213

11121212

11111211

11113111

11122233

BAD ІNPUT LІST

#include <cstdlib>

#include "fstream"

#include "string"

using namespace std;

int main()

{ifstream cin("input.txt");

ofstream cout("output.txt");

string a[100000];

long long int k=0;

long long int k0,k1,k2,k3,i,n;

k0=0;k1=0;k2=0;k3=0;

cin>>n;

while (! cin.eof())

{k++;

cin>>a[k];

for (i=0;i<a[k].length();i++)

{if (a[k][i]=='0') k0++;

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

if (a[k][i]=='2') k2++;

if (a[k][i]=='3') k3++;

if (a[k][i]=='1' || a[k][i]=='3' || a[k][i]=='0') a[k][i]='-';

}

}

if (k0==0 || k1==0 || k2==0 || k3==0) cout<<"BAD INPUT LIST"<<endl;

else

{

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

                                         cout<<a[i]<<endl;

                    cout<<endl;

                    cout<<k0<<" "<<k1<<" "<<k2<<" "<<k3<<endl;

}

                    return 0;

}

program Project2;

{$APPTYPE CONSOLE}

var ch,chr,b,z,i,n: integer;

    c: char;

    inp,outp: text;

begin

   assign(inp,'input.txt');

   assign(outp,'output.txt');

   reset(inp);

   rewrite(outp);

   ch:=0;

   b:=0;

   chr:=0;

   z:=0;

readln(inp,n)

   while not eof(inp)do

      begin

         while not eoln(inp)do

            begin

               read(inp,c);

               case c of

                  '0': begin inc(ch); write(outp,'-')end;

                  '1': begin inc(b); write(outp,'-')end;

                  '2': begin inc(chr); write(outp,'2')end;

                  '3': begin inc(z); write(outp,'-')end;

               end;

            end;

         writeln(outp);

         readln(inp);

      end;

   writeln(outp);

   if (ch=0)or(b=0)or(z=0)or(chr=0)then

      begin

         rewrite(outp);

         writeln(outp,'BAD INPUT LIST');

      end

   else writeln(outp,ch,' ',b,' ',chr,' ',z);

   close(inp);

   close(outp);

end.

Задача D. Цвяхи (100 балів)

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

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

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

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

Вхідні дані

У першому рядку вхідного файлу записано число N – кількість цвяхів (2 ≤ N ≤ 100). У наступному рядку записано N чисел -

координати всіх цвяхів (невід'ємні цілі числа, не перевищують 10000).

Вихідні дані

У вихідний файл потрібно вивести єдине число мінімальну сумарну довжину всіх ниточок.

Приклад

іnput.txt

output.txt

5

4 10 0 12 2

6

#include <cstdlib>

#include "fstream"

#include "string"

using namespace std;

int main()

{ifstream cin("input.txt");

ofstream cout("output.txt");

string a[100000];

long long int k=0;

long long int k0,k1,k2,k3,i;

k0=0;k1=0;k2=0;k3=0;

while (! cin.eof())

{k++;

cin>>a[k];

for (i=0;i<a[k].length();i++)

{if (a[k][i]=='0') k0++;

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

if (a[k][i]=='2') k2++;

if (a[k][i]=='3') k3++;

if (a[k][i]!='2') a[k][i]='-';

}

}

if (k0==0 || k1==0 || k2==0 || k3==0) cout<<"BAD INPUT LIST"<<endl;

else

{

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

                               cout<<a[i]<<endl;

                cout<<endl;

                cout<<k0<<" "<<k1<<" "<<k2<<" "<<k3<<endl;

}

                return 0;

}

function min(a,b:integer):integer;

begin

  if a<b then min := a

  else min := b;

end;

procedure Swap(var a,b:integer);

var

  q:integer;

begin

  q := a;

  a := b;

  b := q;

end;

var

  n,i,j:integer;

  a,b:array[-1..100] of integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  Read(n);

  for i := 1 to n do Read(a[i]);

  for i := 1 to n do

    for j := i+1 to n do

      if a[i]>a[j] then Swap(a[i],a[j]);

  a[0] := Maxint;

  a[-1] := 0;

  for i := 1 to n do

    b[i] := min(b[i-1],b[i-2])+abs(a[i]-a[i-1]);

  WriteLn(b[n]);

  close(input); close(output);

end.

Задача E. Міста (100 балів)

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

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

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

У файлі мститься N назв міст (по одній назві в кожному рядку). Утворіть з даного набору слів замкнений ланцюжок, в якому кожне наступне слово починається з літери, якою закінчувалось попереднє, використавши найбільшу кількість слів. Всі слова у файлі різні і у ланцюжку їх можна використовувати не більше одного разу. Програма повинна на екран та у перший рядок файлу вивести кількість використаних слів,.У випадку, коли ланцюжок утворити неможливо, у файлі міститься лише  одне число 0.

Вхідні дані

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

Вихідні дані

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

Приклади

іnput.txt

output.txt

10

KYEV

DONETSK

LUTSK

KOVEL

VINNICA

DNIPROPETROVSK

KIROVOGRAD

LUGANSK

IVANO-FRANKOVSK

VINNICA

4

#include <fstream>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream cin("input.txt");
ofstream cout("output.txt");
struct ch
{
        char f;
        char l;
};
int m[52][52];
int used[52], maxStep;

void p(int step, int n, int v, int fv)
{
        used[v] = 1;
        int i;

        for (i = 0; i < n; i++)
        {
                if (m[v][i] == 1)
                {
                        if (i == fv)
                        {
                                maxStep = max(maxStep, step);
                        }
                        else
                        {
                                if (used[i] != 1)
                                {
                                        p(step + 1, n, i, fv);
                                }
                        }
                }
        }


        used[v] = 0;
}

int main()
{
        int n,i,j;
        ch mm[50];
        char a[100];
        cin >> n;
        for (i = 0; i < n; i++)
        {
                cin >> a;
                mm[i].f = a[0];
                mm[i].l = a[strlen(a) - 1];
        }

        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        if (mm[i].l == mm[j].f)
                        {
                                m[i][j] = 1;
                        }
                }
        }

        for (i = 0; i < n; i++)
        {
                p(1, n, i, i);
        }

        cout << maxStep << "\n";

        return 0;
}

program state;

const MaxState = 50;

var  name : array [1..MaxState] of string[25]; { назви міст }

fl : array [1..MaxState] of boolean;

kol, maxkol : array [1..Maxstate] of byte;

n, max, j, k, i : byte;

f  : text;

flag : boolean;

{ перевірка можливості додати наступне слово }

function next (st1, st2: string) : boolean;

begin

if st1[length(st1)] = st2[1] then next := true

else next := false;

end;

begin

  { введення даних з файлу }

assign(f,'input.txt'); reset(f);

readln(f,n);

n := 0;

repeat

inc(n); readln(f, Name[n]);

until eof(f);

close(f);

  { головний алгоритм, який шукає тільки один найдовший ланцюжок }

flag := false;

for i:=1 to n do fl[i] := true;

j := 0; k := 0; max := 0;

repeat

while (k < n) do

begin

inc(k);

if (j = 0) or (next(Name[kol[j]], Name[k]) and fl[k]) then

begin

inc(j); kol[j] := k;

fl[k] := false;

k := 0;

end;

end;

if (j > max) and next(Name[kol[j]], Name[kol[1]]) then

begin

max := j;

maxkol := kol;

end;

if j>0 then

begin

k := kol[j]; dec(j);

fl[k] := true;

end

else flag := true;

untilflag;

  { виведення результатів роботи одночасно на екран і у файл }

assign(f, 'output.txtl'); rewrite(f);

if max = 0 then writeln(f,'0') else

begin

writeln(f, max);

end;

close(f);

end.

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

Готуємось до олімпіади з інформатики – 2016 – 3

Завдання

Програма

1

Задачі -5

Система – Ejudge

Робота з файлами – input.txt, output.txt

#include "fstream"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

2

Обчислювальні алгоритми

$1-          Цілі числа та операції – int, longlong, /, %

$1-          Дійсні числа – float, double,  sqrt, pow (math.h)

Задача 1. Час в секундах подати гг хх сс

#include <iostream>

using namespace std;

int main()

{ long long t,g,h,s;

cin >>t;

s=t%60;

t=t/60;

h=t%60;

t=t/60;

g=t%60;

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

    return 0;

}

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

#include <iostream>

#include <math.h>

using namespace std;

int main()

{ double x1,y1,x2,y2,p,s,r,a,b;

cin >>x1>>y1>>x2>>y2;

a=fabs(x1-x2);

b=fabs(y1-y2);

s=a*b;

p=2*(a+b);

r=sqrt(pow(a,2)+pow(b,2))/2;

cout.precision(3);

cout <<fixed;

cout <<s<<endl;

cout <<p<<endl;

cout <<r<<endl;

    return 0;

}

3

Структура розгалуження і цикулу

Задача 3. Кількість нулів

За даним числу n визначте, якою кількістю нулів закінчується десяткова запис числа n! .

#include "iostream"
using namespace std;
int main()
{

long long n,f;
cin>>n;
if (n<5){cout<<0;}
if (n>=5 && n<10) cout<<1;
if (n>=10 && n<15)cout<<2;
if (n>=15 && n<20)cout<<3;
if (n>=20 && n<25)cout<<4;
if (n>=25 && n<30)cout<<6;
if (n>=30 && n<35)cout<<7;
if (n>=35 && n<40)cout<<8;
if (n>=40 && n<45)cout<<9;
if (n>=45 && n<50)cout<<10;
if (n>=50 && n<55)cout<<12;

}

 

#include "iostream"
using namespace std;
int main()
{
long long n,f,i,d,s;
cin>>n;
 d=1;s=0;
for(i=1;i<=100;i++)
{
        d=d*5;
        s=s+n/d;
}
}       

4

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

Задача 4. Кількість максимальних елементів в масиві

#include <iostream>

#include <math.h>

using namespace std;

int a[10000],n;

int main()

{ int max,nmax,k;

cin >>n;

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

max=a[0];nmax=0;

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

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

k=0;

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

if(a[i]==max)k++;

cout <<k<<endl;

    return 0;

}

#include <iostream>

#include <math.h>

using namespace std;

int a[10000],n;

int main()

{ int max,nmax,k,j;

cin >>n;

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

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

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

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

j=n-1;k=1;

while (a[j]==a[j-1] && j>0){k++;j--;}

cout <<k<<endl;

    return 0;

}


 

Задача 5. Домашня робота з математики (100 балів)

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

2 секунди

Максимальний об’єм пам’яті:

256 Мб

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

input.txt

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

output.txt

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

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

Тепер Сашку слід вибрати, яке завдання не виконувати. Допоможіть Сашку вибрати завдання, яке можна не виконувати, щоб інші завдання виконати якомога швидше.

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

Перший рядок вхідного файлу містить цілі числа n и m — кількість завдань і кількість залежностей між завданнями (1 n 100, 0 m 1000). Другий рядок містить n цілих чисел: t1, t2, . . . , tn. Число ti  означає кількість хвилин, необхідних Сашку для виконання i-го завдання (1 ti 1000). Далі іде m рядків, кожен з яких містить два цілих числа. Числа a и b означають, що

завдання a слід виконати раніше аніж завдання b. Гарантується, що всі завдання можна виконати.

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

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

Наприклад

Вхідні дані

Вихідні дані

5 5

1 2 3 4 5

1 2

5 3

1 3

3 4

2 4

11

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

#include "fstream"

using namespace std;

int a[1000],b[1001],c[1001];

ifstream cin("input.txt");

ofstream cout("output.txt");

int main()

{

         long long  n,m,max,nmax,s=0,f2;

         cin>>n>>m;

for (int i=1; i<=n;i++) {cin>>a[i];s=s+a[i];}

for (int i=1; i<=m;i++) cin>>b[i]>>c[i];

int f=1;

while (f)

{max=0;nmax=0;

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

f2=0;

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

if(b[i]==nmax)f2=1;

if(f2)a[nmax]=0;  else f=0;

}

cout<<s-max<<endl;

}

5

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

Задача 6. На квадратному аркуші паперу в клітинку розміром 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;

}

Задача 7.  "Прямокутники" На квадратному аркуші паперу в клітинку розміром 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;

}

6

Рядки

Задача 8. Підрахувати кількість цифри 0  в рядку

#include <iostream>

#include <string.h>

using namespace std;

 char a[10000];

int main()

{

cin>>a;

int n=strlen(a);

int k=0;

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

    if(a[i]=='0')k++;

     cout<<k<<endl;

        return 0;

}

Задача 9. В тесті залишити всі голосні букви інші замінити “_” та порахувати їх кількість

#include <fstream>

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

    char a[1000];

int main()

{

int ka=0, ke=0,ki=0, ko=0, ku=0, ky=0;

while (!cin.eof())

{cin>>a;

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

   {if(a[i]=='a')ka++; else

   if(a[i]=='e')ke++; else

   if(a[i]=='i')ki++;else

   if(a[i]=='o')ko++; else

   if(a[i]=='u')ku++;else

   if(a[i]=='y')ky++;else

   a[i]='_';

   }

   cout<<a<<endl;

}

   cout<<ka<<" "<<ke<<" "<<ki<<" "<<ko<<" "<<ku<<" "<<ky<<endl;

        return 0;

}

 

#include "fstream"

#include "string.h"

#include "string"

using namespace std;

ifstream cin("input.txt");

ofstream cout("output.txt");

string a[1000];

int main()

{int n=0;

int ka=0, ke=0,ki=0, ko=0, ku=0, ky=0;

while (!cin.eof())

{getline(cin,a[n]);

   for(int i=0;i<a[n].length();i++)

   {if(a[n][i]=='a')ka++; else

   if(a[n][i]=='e')ke++; else

   if(a[n][i]=='i')ki++;else

   if(a[n][i]=='o')ko++; else

   if(a[n][i]=='u')ku++;else

   if(a[n][i]=='y')ky++;else

   a[n][i]='_';

   }

   n++;

   }

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

    cout<<a[i]<<endl;

   cout<<ka<<" "<<ke<<" "<<ki<<" "<<ko<<" "<<ku<<" "<<ky<<endl;

        return 0;

}

7

Динамічне програмування

Задача 10. Квиток

Задача 4. «Квитки» (30 балів)

Ім’я файлу програми: BILET.*

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

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

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

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

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

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

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

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

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

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

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

Приклади файлів

input.txt

output.txt

input.txt

output.txt

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]));

#include<iostream>

using namespace std;

int main()

{

int n,i,a[5000],b[5000],c[5000],d[5000];

cin>>n;

for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];

d[0]= 0; d[1]= a[1]; d[2]= min(a[1]+a[2],b[1]);

for(i=3;i<=n;i++) d[i]=min(d[i-1]+a[i],min(d[i-2]+b[i-1],d[i-3]+c[i-2]));

cout<<d[n]<<endl;

}

8

Еврестичні методи

cin>>n;              . . .         cout<<n;

cin>>n;              . . .         cout<<”yes”;

 

9

   

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)

Последнее обновление 29.11.16 09:46
 
Заняття 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

 


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

Статистика

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

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

Нет