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

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

Школа олімпійського резерву з інформатики
III етап олімпіади з інформатики PDF Печать E-mail
Добавил(а) Administrator   
08.02.17 09:44

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

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

Результати учасників

Коди учасників для дорозв'язування олімпіади

 
Заняття 18.01.2017 PDF Печать E-mail
Добавил(а) Administrator   
25.01.17 09:32

http://dn.hoippo.km.ua:8889/cgi-bin/register?contest_id=77

 Задачі (скачати)

 
Заняття 17.01.2017 PDF Печать E-mail
Добавил(а) Administrator   
25.01.17 09:30

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

Тури на шаховій дошці - https://www.e-olymp.com/uk/problems/1327

Анаграми - https://www.e-olymp.com/uk/problems/390

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

НСК - https://www.e-olymp.com/uk/problems/135

Відрізок - https://www.e-olymp.com/uk/problems/136

Сортування -https://www.e-olymp.com/uk/problems/2321

Корупція - https://www.e-olymp.com/uk/problems/21 

 
Заняття 14 (07.12.2016) PDF Печать E-mail
Добавил(а) Administrator   
13.12.16 23:32

Олімпіадні задачі

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

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

1  - Неуважність

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

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

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

Вхідні дані розміщені у файліtext.in

Результат роботи знаходиться у файліtext.out

sCHOOL
School
 
Заняття 13 (30.11.2016) PDF Печать E-mail
Добавил(а) Administrator   
06.12.16 16:09

Функції для опрацювання рядків

strlеn(<рядок>) — визначає фактичну кількість символів у  рядку, застосовується у виразах;

strcat(rl, r2) - команда з'єднання рядків г1, г2 в один ря­док, результат присвоює змінній г1;

strncat(r1, г2, n) - до змінної г1 додає перших n символів рядка г2, команда;

strcpy(r1, r2) - копіює символи з рядка г2 в рядок г1, команда;

strncpy(r1, r2, n) — копіює перших n символів рядка г2 в рядок r1, команда;

strchr(r1, <символ>) - визначає перше входження деякого символу у рядок r1 так: повертає рядок, який починається від першого входження заданого символу до кінця рядка r1, застосовується у виразах;

strrchr(r1, <символ>) - визначає останнє входження зада­ного символу у рядок, застосовується у виразах;

strspn(r1, r2) — визначає номер першого символу, який входить у рядок г1, але не входить

у рядок г2, застосовується у виразах

strstr(r1, r2) - визначає в рядку г1 підрядок, що починаєть­ся з першого входження рядка г2 у рядок г1, засто­совується у виразах;

strtok(r1, r2) - визначає частину рядка г1, яка закінчується перед першим однаковим символом рядків г1 та г2;

strnset(r1, <символ>, n) - вставляє n разів заданий символ перед рядком r1, застосовується у виразах;

strupr(rl) - перетворює усі малі літери рядка у великі;

strlwr(rt) - перетворює усі великі літери рядка у малі;

strrev(rl) - записує рядок у зворотному порядку.

strcmp(s1,s2) -            порівнює рядок s1 з рядком s2 і повертає результат типу int: 0 – якщо рядки однакові, >0 – якщо s1<s2,  <0  — якщо s1>s2 з врахуванням регістру.

cin.getline(str,sizeof(str))- Зчитування рядка з пропусками (тип char)

Застосування функцій

Результат

 

Lviv = "НУ Львівська політехніка"

n = strlen(Lviv)

n = 21

strcat(Un, Lviv)

Un = "НУ Львівська політехніка"

strncat(Un, Lviv, 10)

r1 = "НУ Львівська"

strcpy(r1, Lviv)

r1 = "Львівська Політехніка"

strncpy(r1, Lviv, 10)

r1 = "Львівська"

p = strchr(Lviv, 'П')

p = "політехніка"

p = strrchr(Lviv, Ї)

p = "іка"

n = strspn(Lviv, "Львів")

n = 5

p = strstr(Lviv, "теж")

p = "техніка"

p = strtok(Lviv, "кс")

p = "Львів"

p = strnset(Lviv, 'x', 10)

p = "ххххххххххполітехніка"

p = strupr("I Love You")

p = "і love you"

p = strlwr("I Love You")

p = "I LOVE YOU"

p = strrev('тexнiкa")

p = "акінхет"

Практичні завдання

1. Підрахувати кількість цифр в натуральному числі.

#include "string.h"

int main()

{char n;

cin>>n;

cout<<strlen(n);}

2. Вивести число з п’яти (n) цифр введене з клавіатури в зворотному порядку.

3. Підрахувати кількість входження заданого символу в рядок.

4. Знайти і замінити заданий символ на інший в рядку.


 

Олімпіадні задачі

Задача1. ACMWorldFinals

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

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

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

Кожна команда складається з трьох чоловік і має назву. Напишіть програму, яка по короткій назві команди і прізвищах її учасників, формує повну назву команди.

Повна назва команди складається з короткої назви команди і списку прізвищ її учасників. Прізвища учасників у списку мають бути впорядковані за абеткою і відділені одне від іншого комами. Назва команди від прізвищ учасників має бути відділена двокрапкою. Після кожного розділового знаку має бути рівно один пробіл. 

Формат вхідних даних: вхідний файл містить рівно 4 рядки. Перший рядок містить назву команди. Кожен із наступних трьох рядків містить прізвище одного із членів команди. Довжини рядків не перевищують 50 символів.

Формат вихідних даних: єдиний рядок вихідного файлу має містити рівно один рядок з повною назвою команди.

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

acm.in

acm.out

Dream Team

Knuth

Dijkstra

Cormen

Dream Team: Cormen, Dijkstra, Knuth

Задача 3. Дужки.

Перевірити в виразі правильність розставлення дужок. Вивести повідомлення (Yes|No).

Задача 4.Вираз

Обчислити вираз, який містить операції( +,-,*,/), цілі числа (2, -5), дужки.

5  - Неуважність

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

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

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

Вхідні дані розміщені у файліtext.in

Результат роботи знаходиться у файліtext.out

sCHOOL
School

6 - Арифметика

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

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

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

Вхідні дані розміщені у файліcount.in

Результат роботи знаходиться у файліcount.out

1233
3

Домашнє завдання

Повторити операції з масивом.

 
Опорний конспект 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
 


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

Статистика

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

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

Нет