Школа олімпійського резерву з інформатики

Заняття 7 (19.10.2016)

Добавил(а) 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 10 15

2 10 15

5 5 5

20 20 1

20 1 1

3 4 5

1 1 1

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]+A_i, D[i-2]+ B_i-1, D[i-3]+ C_i-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 клітин намальовано кілька прямокутників. Кожен прямокутник складається з цілих клітинок, різні прямокутники не накладаються один на одного і не дотикаються.

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

Вхідні дані

Вихідні дані

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

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

Вихідні дані

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

Приклад

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

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

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

Добавил(а) 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 клітин намальовано кілька прямокутників. Кожен прямокутник складається з цілих клітинок, різні прямокутники не накладаються один на одного і не дотикаються.

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

Вхідні дані

Вихідні дані

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

input.txt

output.txt

0 1 0

0 0 0

1 1 0

0 0 0

$11 0 1

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

}

Додаткова

(http://codeforces.com/)

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

Заняття 5 (05.10.2016)

Добавил(а) Administrator
11.10.16 10:00
Заняття 5 (05.10.2016) Базові структури алгоритмів (структура циклу) 1. Прості числа http://www.e-olymp.com/uk/problems/830 Вивести всі прості числа від M до N включно. Вхідні дані У першому рядку знаходяться відокремлені пропуском M і N (2 ≤ M ≤ N ≤ 300 000). Вихідні дані Вивести числа у порядку зростання, по одному у рядку. Якщо між M і N включно немає простих - вивести "Absent" (без лапок). Вхідні дані Sample 1 2 5 Sample 2 4 4 Вихідні дані Sample 1 2 3 5 Sample 2 Absent 2. Решето Ератосфена http://www.e-olymp.com/en/problems/4739 За введеним числам A і B вивести всі прості числа в інтервалі від A до B включно. Вхідні дані У єдиному рядку вводяться два числа 1 ≤ A≤ B≤ 100000. Вихідні дані Вивести в один рядок всі прості числа в інтервалі від A до B включно. Input example Sample 1 2 2 Sample 2 1 100 Output example Sample 1 2 Sample 2 $12 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 3.Codeforces (http://codeforces.com/) http://codeforces.com/problemset/problem/550/A Два підрядки Дано рядок s. Потрібно визначити, чи існують в цьому рядку s два непересічні підрядка "AB" і "BA" (ланцюжки можуть йти в будь-якому порядку). Вхідні дані На вхід подається рядок s довжиною від 1 до 10⁵ символів, що складається з великих літер латинського алфавіту. Вихідні дані Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше. приклади тестів вхідні дані ABA вихідні дані NO вхідні дані BACFAB вихідні дані YES вхідні дані AXBYBXA вихідні дані NO Примітка У першому прикладі вхідних даних, незважаючи на те, що є підрядка "AB" і "BA", їх входження перетинаються, тому відповідь - "NO". У другому прикладі вхідних даних є наступні входження подстрок: BACFAB. У третьому прикладі немає ні підрядка "AB", ні підрядка "BA".
Читать полностью

Заняття 4 (28.09.2016)

Добавил(а) Administrator
11.10.16 09:58
Заняття 4 (28.09.2016) Структура циклу Група 1 (рівень 1). Розгалуження https://www.e-olymp.com/uk/problems/905 (Трикутник) https://www.e-olymp.com/uk/problems/918 (Координатна чверть) https://www.e-olymp.com/uk/problems/911 (Квадратне рівняння) Структура циклу https://www.e-olymp.com/uk/problems/910 (Середнє арифметичне додатних) https://www.e-olymp.com/uk/problems/908 (Ті що діляться на 6) https://www.e-olymp.com/uk/problems/906 (Добуток цифр) https://www.e-olymp.com/uk/problems/7338 (Постійна сума) Група 2 (рівень 2). Задачі Сортування часу - http://www.e-olymp.com/uk/problems/972 Велике сортування - http://www.e-olymp.com/uk/problems/973 Хитре сортування - http://www.e-olymp.com/uk/problems/1462 Багатокутники - http://www.e-olymp.com/uk/problems/2987 Два массива - http://www.e-olymp.com/uk/problems/2099 Результати олімпіади - http://www.e-olymp.com/uk/problems/1962 Теорія Методи сортування: $11) Бульбашка $12) Вибір максимального (мінімального) $13) Швидке $14) Вектором Група 3 https://www.e-olymp.com/uk/problems/1906/ (Лампочки) http://ejudge.itolymp.com/cgi-bin/new-client?contest_id=000092
Последнее обновление 11.10.16 09:59

Заняття 3 (21.09.2016)

Добавил(а) Administrator
11.10.16 09:53
Заняття 3 (21.09.2016) Завдання 1 Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в даній послідовності. Завдання 2 - https://www.e-olymp.com/uk/problems/192 - http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=24 (завдання B ) Логін school2016-1 . . . school2016-10 (пароль - 1) Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з усіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару? Використаємо рекурентну формулу чисел Фібоначі. Кожне число Фібоначі знаходять за формулою: Додаток 1. Волинська учнівська Інтернет-олімпіада з програмування у 2016-2017 н. р. http://93.183.238.10/vippoolimp/. 2. Повідомляємо, що а сайті http://netoi.org.ua (http://www.olymp.vinnica.ua) почалася реєстрація учасників відкритої Всеукраїнської Інтернет-олімпіади з інформатики NetOI-2016 http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=1679 Ви можете самі взяти в ній участь і порекомендувати це зробити тим, кого, на вашу думку, це може зацікавити.Якщо Ви школяр, обов'язково повідомте про олімпіаду своїм учителям інформатики. 3. Школа з програмування (м. Київ) Природничо-науковий ліцей №145 оголошує про початок роботи Київської школи олімпійського резерву з програмування. Мета школи – підготовка учнів міста Києва до олімпіад з інформатики (програмування) різних рівнів. Перше (організаційне) заняття відбудеться 24 вересня. Заняття цілком безкоштовні! https://itolymp.com/ 4. Інтелектуальні змагання школярів в мережі Інтернет. Сервіс підтримки Інтернет-олімпіади з інформаційних технологій ІОІТ-2016 http://ejudge.itolymp.com/ 5. ІОІТ 2017 Відповідно до Положення про Всеукраїнські учнівські Інтернет-олімпіади, затвердженого наказом Міністерства освіти і науки, молоді та спорту України від 11 червня 2012 року № 671, зареєстрованого в Міністерстві юстиції України 27 червня 2012 року за № 1074/21386, наказу Міністерства освіти і науки України від 07.06.2016 №626 «Про проведення Всеукраїнських учнівських Інтернет-олімпіад з математики, фізики, хімії, біології, географії, економіки, інформатики, інформаційних технологій у 2016/2017 навчальному році» Міністерством освіти і науки України, Київським національним університетом імені Тараса Шевченка спільно зУкраїнським фізико-математичним ліцеєм КНУ імені Тараса Шевченка розпочато проведення Всеукраїнської учнівської Інтернет-олімпіади з інформаційних технологій у 2016/2017 навчальному році. Всеукраїнська учнівська Інтернет-олімпіада проводиться у два етапи в наступні терміни: І ( заочний) етап:30 червня – грудень 2016 року; ІІ (очний) етап:січень – лютий 2017 року. Реєстрація для участі в олімпіаді відбувається за цимпосиланням. Ознайомитися із умовами реєстрації та етапами проведення олімпіади можна за посиланням http://upml.knu.ua/internet-olimpiada-it-2017/
Читать полностью

Заннятя 2 (14.09.2016)

Добавил(а) Administrator

14.09.16 00:00

Заннятя 2 (14.09.2016)

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

Розв’язати і протестувати задачі в системі (http://134.249.159.199/cgi-bin/new-client?contest_id=23)

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

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

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

Задача DEMO_A
         На площині задано координати двох відрізків AB і CD. Знайти спільну частину проекцій цих відрізків на вісь абсцис.

Вхідні дані
         Ви вводите з клавіатури 8 цілих чисел - координати точок A, B, C, D. Кожне число не перевищує за абсолютною величиною 1000.

Вихідні дані
         Ви виводите на екран одне число - спільну частину проекцій. Якщо спільна частина - порожня множина, вивести -1, якщо це одна точка - вивести 0.

Приклад вхідних та вихідних даних
Вхід: 2 2 7 5 3 4 8 1
Вихід: 4

Задача DEMO_B

         Скільки натуральних чисел виду 2^a3^b5^ca,b,c - невід'ємні цілі числа) належать відрізку [M;N]?

Вхідні дані
         Ви вводите з клавіатури 2 цілих числа M та N. Кожне з чисел не перевищує за абсолютною величиною 10000.

Вихідні дані
         Ви виводите на екран одне число - шукану кількість чисел.

Приклад вхідних та вихідних даних
Вхід: 10 20
Вихід: 6

Задача DEMO_C

         Дана послідовність N цілих чисел. Знайти найменший додатній елемент цієї послідовності.

Вхідні дані
         Ви вводите з клавіатури кількість чисел N та N цілих чисел - елементів цієї послідовності. Число N не перевищує 10000, кожний елемент послідовності не перевищує за абсолютною величиною 1000.

Вихідні дані
         Ви виводите на екран одне число - шуканий елемент послідовності. Якщо у послідовності немає додатніх елементів - вивести 0.

Приклад вхідних та вихідних даних
Вхід: 7 -4 4 -7 3 0 8 2
Вихід: 2

Задача DEMO_D

         Задано натуральне число N. Знайти найменше та найбільше число, яке складається з тих самих цифр та у такій самій кількості, що і N.

Вхідні дані
         Ви вводите з клавіатури число N (1£ N £2000000000).

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

Приклад вхідних та вихідних даних
Вхід: 7051
Вихід: 1057 7510

Задача DEMO_E

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

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

Вихідні дані
         Ви виводите на екран шуканий рядок.

Приклад вхідних та вихідних даних
Вхід: Ф11р88н
Вихід: 1188

Задача DEMO_F

         Дано K клітин шахової дошки. З'ясувати, чи всі вони одного кольору.

Вхідні дані
         Ви вводите з клавіатури кількість контрольних прикладів, потім число К - кількість клітин шахової дошки,а у наступних К рядках - координати клітин (натуральні числа, не більші 8).

Вихідні дані
         Ви виводите на екран для кожного приклада 1, якщо всі клітини одного кольору і 0, якщо це не так.

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

Вхід:

3
1	2
8	1
8	5
2
1	1
1	2
2
1	1
2	2

Вихід: 101

Увага! Це не заліковий тур!

Парне+парне, непарне-непарне –чорна

Парне+непарне, непарне-парне –біла

$13. Дистанційне навчання *(http://dystosvita.mdl2.com/ )

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

Основи програмування (Python)

Заннятя 1 (07.09.2016)

Добавил(а) Administrator

07.09.16 00:00

Заннятя 1 (07.09.2016)

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

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

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

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

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

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

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

Введення	Виведення
12 1 5
125 5 10
325 5 1

Завдання 2

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

Поворот

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

Вхідні дані

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

Вихідні дані

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

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

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

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

3 4

1 2 3 4

5 6 7 8

9 10 11 12

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

4 3

9 5 1

10 6 2

11 7 3

12 8 4

Завдання 3

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

Фібоначчієва система числення

Як відомо, послідовність Фібоначчі починається з двох чисел 0 та 1 і кожен наступний член послідовності отримується як сума двох попередніх. Наприклад, третій член послідовності це 1 (1=1+0), четвертий - 2 (2=1+1), п'ятий - 3 (3=2+1) і т.д.

i	0	1	2	3	4	5	6	7	8	9
Fib(i)	0	1	1	2	3	5	8	13	21	34

Рисунок 1 - Перші числа послідовності Фібоначчі

Ця послідовність проявляється дуже часто і у нашому житті і у природі та має велике значення. А чи знаєте Ви, що всі додатні цілі числа можна подати як суму чисел з послідовності Фібоначчі? Більше того, всі натуральні числа можна подати за допомогою послідовності Фібоначчі, причому без повторень. Наприклад: 13 може бути подано за допомогою вказаної множини як {13}, {5,8} або {2,3,8} а 17 подано як {1,3,13} або {1,3,5,8}. Так як всі числа мають цю властивість (може у Вас є бажання довести це?), то цей набір є гарним способом для його використання у якості "бази" (основи системи числення) для подання чисел. Але, як ми бачили вище, деякі числа можуть бути подані більш ніж одним способом сумою чисел з послідовності Фібоначчі. Як нам вийти з цієї ситуації? Дуже просто! Для цього достатньо накласти обмеження, що при поданні числа не можна використовувати два сусідніх елементи з послідовності Фібоначчі! Це обмеження поясюється тим, що сума двох сусідніх членів послідовності Фібоначчі сама є членом послідовності Фібоначчі.

Тепер, коли нам відомо все сказане вище, ми можемо запропонувати гарний спосіб подавння довільного цілого додатнього числа. Для цього ми будемо використовувати двійкову послідовність (лише нулів та одиниць). Наприклад, 17 = 1 + 3 + 13 (ми повинні пам'ятати, що не можна використовувати два послідовних числа Фібоначчі). Будемо використовувати нуль у запису, якщо чергове число з послідовностіи Фібоначчі не використовується, і одиницю для тих, що використовуються. Тоді, 17 = 100101 (ведучі нулі повинні бути відсутні). На рисунку 2детально показано, як отримано цей запис і що означають нулі та одиниці у наведенному вище запису. Для кращого розуміння цієї схеми звернемо увагу на той факт, що не використання двох сусідніх чисел Фібоначчі означає, що двійкова послідовність не буде мати двох одиниць, що йдуть підряд. Використовуючи наведене подання числа, ми будемо говорити, що ми використовуємо Фібоначчієву систему числення і записувати його як 17 = 100101 (fib).

17=	1	0	0	1	0	1
13+3+1=	13	8	5	3	2	1

Рисунок 2 - Пояснення подання числа 17 у Фібоначчієвій системі числення

Ваша задача полягає у запису задного десяткового числаув Фібоначчієвій системі числення.

Вхідні дані

У першому рядку вхідних даних задано єдине натуральне число N, яке вказує на кількість прикладів у тесті (1 ≤ N ≤ 500).

Наступні N рядків містять по одному додатньому цілому числу, яке не перевищує 100 000 000. Числа можуть бути подані у довільному порядку.

Вихідні дані

Ви повинні вивести по одному рядку для кожного з N чисел, отриманих у вхідних даних, у наступному форматі: "DEC_BASE = FIB_BASE (fib)". DEC_BASE це задане оригінальне число у десятковій системі числення, а FIB_BASE відповідно - його подання у Фібоначчієвій системі числення. Зразок виведення наведено у прикладі вихідних даних.

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

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

Вхідні дані

Вихідні дані

1 = 1 (fib)

2 = 10 (fib)

3 = 100 (fib)

4 = 101 (fib)

5 = 1000 (fib)

6 = 1001 (fib)

7 = 1010 (fib)

8 = 10000 (fib)

9 = 10001 (fib)

10 = 10010 (fib)

Архів матеріалів

Добавил(а) Administrator
27.04.16 08:11
Архів матеріалів Матеріали школи обдарованих дітей 2016-2017 Матеріали школи обдарованих дітей 2015-2016 Матеріали школи обдарованих дітей 2014-2015 Матеріали школи обдарованих дітей 2013-2014 Матеріали школи обдарованих дітей 2012-2013 Матеріали школи обдарованих дітей 2011-2012 Матеріали школи обдарованих дітей 2010-2011 Матеріали школи обдарованих дітей 2009-2010 Матеріали школи обдарованих дітей 2008-2009 Матеріали школи обдарованих дітей 2007-2008 Матеріали школи обдарованих дітей 2006-2007 Матеріали школи обдарованих дітей 2005-2006
Последнее обновление 20.09.16 13:14

Другие статьи...

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

Главное меню

Статистика

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

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

Нет

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

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

Задачі

5. ІОІТ 2017

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

Поворот

Вхідні дані

Вихідні дані

Главное меню

Статистика

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