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

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

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

Всеукраїнськiй олімпіадi з інформатики NetOI-2015 (http://www.olymp.vinnica.ua/)

Читать полностью
 
Заняття 2 (13.09.2017) PDF Печать E-mail
Добавил(а) Administrator   
15.09.17 09:11

7226 День календаря

Як відомо день програміста припадає на 256 день року, у невисокосний рік це - 13 вересня, а у високосний — 12. Не забудьте привітати своїх колег і наставників.

Аналогічно пропонується розпізнати число та номер місяця, що припадає на день за номером n у невисокосному2014 році.

Вхідні дані

Натуральне число n (1 ≤ n ≤365).

Вихідні дані

Число (від 1 до 31) та номер місяця (від 1 до 12), що відповідає дню з номером n.

Вхідні дані

256

Вихідні дані

13 9

#include <iostream>

using namespace std;

int main()

{

int n;

cin>>n;

int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int m=0;

while (n>a[m]){n=n-a[m];m++;}

cout<<n<<" "<<m<<endl;

}

 
 


 

193 Сума цифр

Знайти найменше і найбільше N-значні натуральні числа, які мають суму цифр M.

У вхідному файлі числа N і M (1≤N≤100, 1≤M≤9*N). До вихідного файлу потрібно записати два N-значних числа в неспадаючому порядку.

Вхідні дані

3 4

Вихідні дані

103 400

#include <iostream>

using namespace std;

int main()

{int n,m;

cin>>n>>m;

long long x=1;

for(int i=1;i<n;i++) x=x*10;

int s=0;

while (s!=m)

{

    int t=x;

    s=0;

    while(t>0)

    {

        s=s+t%10;

        t=t/10;

    }

    x++;

}

x--;

cout<< x << " ";

x=9;

for(int i=1;i<n;i++) x=x*10+9;

s=0;

while (s!=m)

{

    int t=x;

    s=0;

    while(t>0)

    {

        s=s+t%10;

        t=t/10;

    }

    x--;

}

x++;

cout<< x << endl;

    return 0;

}

#include <iostream>

using namespace std;

int a[100],b[100];

int main()

{int n,m;

cin>>n>>m;

int s=1;

int i=n-1;

a[0]=1;

int temp=m-1;

while (temp>0 and i>0)

{

if(temp<=9) a[i]=temp; else a[i]=9;

temp=temp-a[i];

i--;

}

a[0]=a[0]+temp;

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

cout<<" ";

s=0;

i=0;

temp=m;

while (temp>0)

{

if(temp<=9) b[i]=temp; else b[i]=9;

temp=temp-b[i];

i++;

}

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

cout<<endl;

return 0;

}

 


 

1356 SMS голосування

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

Вхідні дані

У першому рядку записано два числа N і M (3 ≤ ≤ 100≤ ≤ 1000000).

У наступному рядку M чисел, кожне з яких не перевищує N.

Вихідні дані

Три числа - номери переможців записані в один рядок, через пропуск.

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

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

Вхідні дані

5 10 1 2 3 4 5 2 1 2 4 2

Вихідні дані

2 1 4

Зчитати масив

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

Знайти три максимальні

Сортування

#include <iostream>

int a[1001],b[4];

using namespace std;

int main()

{int n,m,k,maxx,nmaxx;

cin>>m>>n;

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

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

{

maxx=a[1];nmaxx=1;

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

if(a[i]>maxx){maxx=a[i];nmaxx=i;}

a[nmaxx]=-1;

b[j]=nmaxx;

}

cout<<b[1]<<" "<<b[2]<<" "<<b[3]<<endl;

return 0;

}

 

 

 

 

 

Последнее обновление 22.09.17 08:01
 
Заняття 1 (06.09.2017) PDF Печать E-mail
Добавил(а) Гісь І.В.   
15.09.17 09:09

7226 День календаря

Як відомо день програміста припадає на 256 день року, у невисокосний рік це - 13 вересня, а у високосний — 12. Не забудьте привітати своїх колег і наставників.

Аналогічно пропонується розпізнати число та номер місяця, що припадає на день за номером nу невисокосному2014 році.

Вхідні дані

Натуральне число n(1 n ≤365).

Вихідні дані

Число (від 1 до 31) та номер місяця (від 1 до 12), що відповідає дню з номером n.

Вхідні дані

256

Вихідні дані

13 9

193 Сума цифр

Знайти найменше і найбільше N-значні натуральні числа, які мають суму цифр M.

У вхідному файлі числа N і M (1≤N≤100, 1≤M≤9*N). До вихідного файлу потрібно записати два N-значних числа в неспадаючому порядку.

Вхідні дані

3 4

Вихідні дані

103 400

1356 SMS голосування

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

Вхідні дані

У першому рядку записано два числа Nі M(3 100,1 1000000).

У наступному рядку Mчисел, кожне з яких не перевищує N.

Вихідні дані

Три числа - номери переможців записані в один рядок, через пропуск.

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

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

Вхідні дані

5 10 1 2 3 4 5 2 1 2 4 2

Вихідні дані

2 1 4

Последнее обновление 22.09.17 08:01
 
Літня школа з програмування PDF Печать E-mail
Добавил(а) Administrator   
31.05.17 09:09

Літня школа з програмування

та інформаційних технологій 2017

 

Комп’ютерна Школа «ОЛІМП»


Працюйте влітку. Розв'язуйте задачі самостійно на сайтах:

1. https://www.e-olymp.com

2. http://codeforces.com/


 

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

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

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

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

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

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

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

Логінschool1-school10 (пароль - 1)

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

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

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

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

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

Задача A. Сходинки

https://www.e-olymp.com/ru/problems/7669

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

На яку сходинку стрибне Петрик, якщо він стоїть на сходинці з номером M, а усього сходи мають N сходинок?

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

У єдиному рядку вхідного файлу записані через пробіл такі дані: число N(1 ≤ N ≤ 1000) – кількість сходинок на сходах, число M(0 MN)– номер сходинки на якій стоїть Петрик та символ, який  означає силу з якою Петрик відштовхується: S (strongly) – сильно або  W (weakly) –слабо.

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

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

Приклад:

Стандартне введення

Стандартне виведення

10  3W

4


Задача B Степан і похід в магазиy

 

https://www.e-olymp.com/ru/problems/7670

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

Від будинку до першого магазину веде доріжка довжини d1 метрів, а до другого магазину веде доріжка довжини d2 метри. Також існує доріжка, яка безпосередньо сполучає два магазини один з одним, довжиною d3 метри

 
   


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

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

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

8

 

У першому рядку вхідних даних знаходяться 3 цілих числа d1, d2, d3 (1 ≤ d1, d2, d3 ≤ 10 ) ­ довжини доріжок.

d1­довжинадоріжки,щоз'єднуєбудинокСтепанаіпершиймагазин;d2 ­ довжина доріжки, що з'єднує будинок Степана і другий магазин;d3 ­ довжина доріжки, що з'єднує двамагазина.

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

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

Приклад

Стандартне введення

Стандартне виведення

10 20 30

60


Задача C. Підготовка до шахової олімпіади

https://www.e-olymp.com/ru/problems/7671

В університеті, де вчився Степан, вирішили провести шахову олімпіаду. Щоб добре до неї підготовитись, Степан вирішив спочатку пограти зі своїм сусідом Робертом, якого усі мешканці дома називали жартома Фішером. Роберт досить пристойно грав у шахи і залюбки погодився допомогти Степану.

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

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

Вхідний файл містить одне число – N  (кількість партій,  0 ≤ N ≤1018).

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

Одне число – кількість поразок Степана у зустрічах з Робертом у перших N партіях.

Приклад:

Стандартне введення

Стандартне виведення

5

3

Задача D Кратне трьом

https://www.e-olymp.com/ru/problems/7672

Дано число. Степан хоче замінити в ньому одну цифру таким чином, шоб нове число ділилось на 3 і було максимально можливим. В заданому числі потрібно обов'язково замінити одну цифру, навіть якщо задане число ділилось на 3.

Оскільки Степан тільки почав відвідувати факультатив з програмування, то він просить допомоги у вас. Формат вхідних даних

Дано одне натуральне число. Довжина числа може досягати 100 цифр. Формат вихідних даних

Виведіть інше натуральне число, що задовольняє умовам:

$11.    Нове число повинно відрізнятись від даного рівно однієюцифрою.

$12.    Нове число повинно ділитись на3.

$13.    Нове число повинно бути максимально можливим з усіх такихчисел.

Стандартне введення

Стандартне виведення

123

723


Задача Е  З трьох прости чисел

 

https://www.e-olymp.com/ru/problems/7673

Знайти кількість натуральних чисел з проміжку [B] в розкладі на прості множники яких є рівно 3 простих множника.

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

В одному рядку два числа через пробіл: A і B, 1 ≤ AB ≤ 10000000

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

В одному рядку одне число – кількість чисел з проміжку які складаються рівно з 3­х простих множників.

Стандартне введення

Стандартне виведення

10 20

8 20

3

4

Задача F Старовинна задача

https://www.e-olymp.com/ru/problems/7674

Готуючись до чергової олімпіади з програмування, Степан натрапив на одну старовинну задачу, яка його зразу ж зацікавила. У задачі йшлося про те, що у країні, яка називалась Триманія, номінали усіх паперових грошей (триманських фунтів) дорівнювали ступеням трійки, тобто 1, 3, 9, 27 і так далі. Необхідно було визначити, яку мінімальну кількість купюр і яких саме потрібно мати покупцю та продавцю, щоб купити товар вартістю Nтриманських фунтів та отримати здачу, причому номінали купюр, якими розплачуються та отримують здачу, не повинні повторюватися.

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

Вхідний файл містить одне число – N  (вартість товару у фунтах,  0 ≤ N ≤1018).

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

Один рядок містить номінали купюр у зростаючому порядку через пробіл, які потрібні для купівлі товару покупцю та продавцю,  або  –1, якщо купити товар за означених умов неможливо.

Приклад:

Стандартне введення

Стандартне виведення

11

1 3 9


Задача G Багатокутники

На площині задана така множина з N багатокутників, що виконуються наступні умови:

$11)    ніякі два багатокутника не мають спільнихточок;

$12)      для кожного i–го багатокутника існує Pi багатокутників, всередині яких він знаходиться, і N­1­Piбагатокутників, котрі знаходяться всередині нього,0≤PiN­1.

Завдання:    напишіть    програму    POLYGON,   яка    для    кожного    багатокутника   видає    кількість багатокутників, всередині яких вінзнаходиться.

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

перший рядок вхідного файлу містить ціле число N — кількість багатокутників, 3≤N≤10000. Наступні N рядків файлу описують N багатокутників. (i+1)–ий рядок файлу описує i–ий багатокутник. Перше ціле число Ci­ кількість вершин багатокутника, 3≤Ci≤20. Наступні Ciпар чисел — координати вершин багатокутника у порядку його обходу. Координати вершин — цілі числа, що належать діапазону від ­2 000 000 000 до 2 000 000 000.

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

єдиний рядок вихідного файлу повинен містити N чисел: i–те число рядка повинно бути Pi— кількість багатокутників, всередині яких знаходиться i–ий багатокутник.

Приклад

Стандартне введення

Стандартне виведення

3

0 2 1

3 ­2 1 8 9 12 1

 

3 7 5 6 3 7 4

 

4 4 3 7 7 9 3 1 2

 


Задача H Вираз

https://www.e-olymp.com/ru/problems/7675

Для запису числових виразів жителі країни Олімпія використовують наступний формат:

$11.                    Вираз складається з операндів та знаків операцій, розділенихпропусками.

$12.                    Операнди: додатні цілічисла.

$13.                    Операції: додавання (позначається знаком +) та множення (позначається знаком*).

$14.                    Вираз розглядається зліва направо. Якщо у виразі зустрічається знак операції, виконується відповідна операція над двома останніми операндами перед ним, результат операції замінює у виразі послідовність її операндів і знаку операції, посля чого обчислення продовжується за цим жеправилом.

$15.                    Результатом виразу є результат останньоїоперації. Обчислимо, наприклад, вираз 3 4 2 *+

Перша операція у виразі ­ множення (*), вона буде виконана над останніми перед нею числами (4 та 2), отримаємо число 8, що замінить послідовність 4 2 *, таким чином отримаємо вираз 3 8 +.

У отриманому виразі перша операція, що зустрілась ­ додавання (+), вона буде виконана над останніми перед нею числами (3 та 8), отримаємо число 11, що замінить послідовність 3 8 +.

Оскільки операцій у виразі більше не залишилось, обчислення виразу завершилось. Результатом виразу є число 11.

Відомо, що значення будь­якого виразу знаходиться у межах від 0 до 2000000000.

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

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

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

Вихідний текстовий файл містить єдине число ­ результат обчислення виразу. Приклад

Стандартне введення

Стандартне виведення

3 4 2 * +

11

58 2 + 10 + 2 *

140


Задача I. Кубики

https://www.e-olymp.com/ru/problems/7676

На День народження свого племінника Петрика Степан подарував йому набір кубиків. Петрик тутже став будувати з кубиків паркан, однак стовпчики у Петрика виходили різної висоти. Степана зацікавило питання: "Яку найменшу кількість перекладань можна зробити, щоб висота будь­яких двох стовпчиків відрізнялась не більше ніж на один кубик. Крім того за один раз можна перекладати тільки один кубик з довільного стовпчика на поручрозташований.

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

У першому рядку вхідного файлу записано число N(1 ≤ N ≤ 1000) – кількість стовпчиків з кубиками у Петрика. Другий рядок містить Nцілих чисел – висоту кожного стовпчика (у кубиках). Усі числа не перевищують 106.

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

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

Приклад:

Стандартне введення

Стандартне виведення

5

3 4 8 2 5

4

Пояснення до прикладу. Зробити два перекладання зі стовпчика №3 у стовпчик №4. Результат – 3 4 645.Потімперекластикубикзістовпчика№2устовпчик№1.Результат–43645.Інаостанок

перекласти кубик зі стовпчика №3 у стовпчик №2. Результат – 4 4 5 4 5.

Задача J П'ятірки

https://www.e-olymp.com/ru/problems/7677

Задані два цілих числа NiK. Знайдіть найменше число, більше, чим N, в десятковому записі якого міститься не менше чим K п'ятірок.

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

У першому рядку вхідного файлу міститься два числа NiK (1 ≤N ≤10^15 , 1 ≤ K ≤ 15).

Формат вихідних даних виведіть одне знайдене число.

Приклад

Стандартне введення

Стандартне виведення

99 1

105

595 2

655


15187565 3

15187575

15187565 2

15187566

Задача K Безпечний шлях

Межа відомого Вам мінного поля представляє собою многокутник без самоперетинів і самодотиків. Поза мінним полем (але, можливо, на його межі) задані дві точки А і В.

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

Формат вхідних даних: у першому рядку вхідного файлу міститься чотири цілих числа:

XA, YA, XBiYB­ координати заданих точок. Другий рядок містить ціле число N(3 ≤ N ≤ 100) ­ кількість вершин граничного многокутника. Кожен із наступних N рядків містить координати XiY однієї вершини многокутника. Опис вершин задано в порядку їх обходу проти годинникової стрілки. Усі координати ­ цілі числа в проміжку від ­100 000 до 100 000.

Формат вихідних даних: виведіть одне число ­ довжину найкоротшого шляху, з точністю до 0.0001.

Стандартне введення

Стандартне виведення

0 0 5 5

7.2361

4

 

1 0

 

3 0

 

3 2

 

1 2

 


Задача L Дороги

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

Формат вхідних даних: Вхідний файл описує граф доріг одного і більше міст. Перший рядок вхідногофайлуміститьдвацілихчисла:N­числовершин,E­числоребер(1≤N≤20000,0≤E≤20000). Далі йдуть E рядків ­ опис ребер, що містять E пар цілих чисел ­ номери вершин з'єднаних ребром, вершини нумеруються від 1 до N. Всі числа розділеніпробілами.

Формат вихідних даних: Вихідний файл повинен повторювати дані вхідного файлу точно в томуж порядку з додатковими елементами: опис ребра крім двох чисел, що є лівою і правою вершиною ребра, містить праворуч символ > якщо дорога орієнтована від лівої вершини до правої, символ < якщо дорога орієнтована від правої вершини до лівої або символ = якщо дорога залишається неорієнтованою. Не забувайте розділяти елементи пробілами і виведіть будь­який вподобаний вами варіант орієнтації графа доріг.

Приклад

Стандартне введення

Стандартне виведення

2 2

2 2

1 2

1 2 >

1 2

1 2 <

2 1

2 1

1 2

1 2 =


Задача М Найбільший прямокутник

Вам заданий прямокутник розміром N*M, який складається тільки з одиниць і нулів. Вам дозволяється переставляти стовпці в ньому. Яку максимальну площу підпрямокутника, який складається тільки з 1 можна отримати за допомогою таких операцій. Підпрямокутником прямокутника назвемо четвірку чисел (x1, y1, x2, y2), x1 ≤ x2, y1 ≤ y2. Точки з яких він складається мають координати (i, j), x1 ≤ ix2, y1 ≤ jy2.

Формат вхідних даних: перший рядок вхідного файлу містить два числа N і М (1 ≤ N ≤ 15 000, 1 ≤ M ≤ 1500). В наступних N рядках задано матрицю, кожен рядок якої не містить пропусків і складається рівно з М символів.

Пояснення: В даному тесті можна поміняти місцями 2­й і 5­й стовпець. Після такої операції отримаємо прямокутник в якому міститься максимальний підпрямокутник.

Стандартне введення

Стандартне виведення

10 6

21

001010

 

111110

 

011110

 

111110

 

011110

 

111111

 

110111

 

110111

 

000101

 

010101

 
 

Формат вихідних даних: єдиний рядок вихідного файлу має містити одне число ­ максимальну площу. Приклад


Задача N Прогулянка по парку

Руслан полюбляє вечорами та ночами гуляти парком. Іноді ці прогулянки тривають всього півгодини, іноді 2, а іноді Руслан губиться у складній системі доріжок парку і блукає там годинами, доки не знайде виходу.

Кожна доріжка являє собою замкнене коло, таким чином з однієї доріжки можна перейти на іншу, тільки там, де обидві мають спільну точку. Будемо вважати що доріжка ­ контур деякого круга з центром в точці (X, Y).

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

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

Вхідні дані:

Перший рядок містить кількість доріжок (1 ≤ N ≤ 200). Далі йде N рядків, кожен з яких містить трійку цілих чисел X, Y, R ­ координати центру та радіус кола відповідно. В останніх двох містяться координати Руслана та гуртожитку (координати початку та кінця ­ дробові числа з 11 знаками після коми). Всі координати по абсолютній величині не перевищують 105

Кожна з позицій буде гарантовано розташована на якомусь з кіл. Ніякі два кола не співпадають (трійка  X, Y, R ­унікальна).

Вихідні дані:

Єдиний рядок має містити довжину найкоротшого шляху з точністю не гірше ніж 10­5. У випадку, якщо такого маршруту не існує виведіть ­1.

Стандартне введення

Стандартне виведення

2

9.4247780

0 0 3

 

5 0 3

 

­3.0 0.0

 

2.0 0.0

 

2

­1

0 0 2

 

5 0 2

 

­2 0

 

3 0

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

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

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

Задача 4 «Зернинки»

Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.

 

1

2

3

4

5

6

7

8

9

   

1

2

3

4

5

6

7

8

9

1

2

1

0

8

4

1

4

9

6

 

1

2

3

3

12

16

17

20

30

36

2

6

2

5

7

3

2

10

1

3

 

2

8

10

15

22

25

27

37

37

40

3

2

8

6

6

6

6

8

5

8

 

3

10

17

24

30

35

41

49

55

62

4

5

9

5

9

6

6

4

6

9

 

4

15

26

31

41

47

53

57

63

72

5

7

4

6

7

3

5

8

4

1

 

5

21

30

38

48

51

58

66

71

73

6

2

5

4

9

4

5

5

4

10

 

6

24

35

41

56

60

66

72

75

85

7

4

3

8

1

0

6

6

9

4

 

7

28

39

49

58

61

71

77

87

91

8

4

3

7

8

8

9

5

9

1

 

8

32

42

57

65

74

83

89

98

99

9

2

5

2

2

2

1

6

7

6

 

9

34

47

59

68

76

84

95

105

110

10

10

1

6

2

10

7

4

5

3

 

10

44

48

65

69

86

93

99

110

113

=МАКС(C3+M3;C3+N2)


Задачі 6. Купування квитків

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

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

Bilet.*

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

Bilet.dat

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

Bilet.dat

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

5 секунд

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

100 балів

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

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

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

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

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

У вхідному файлі записано спочатку число N - кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел AiBiCi. Кожне з цих чисел не перевищує 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]= min(а[1]+a[2], b[1]);

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

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

Прості числа

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

https://www.e-olymp.com/az/problems/5212

https://www.e-olymp.com/ru/problems/22

Решето Ератосфена

http://e-maxx.ru/algo/eratosthenes_sieve

Варіант 1

Варіант2

for i:=2 to n do

begin

p:=0;

for j:=2 to round(sqrt(i)) do

if i mod j =0 then p:=1;

if p=0 then write(i,' ');

end;

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

a[1]:=0;

i:=1;

while i<=n div 2 do begin

while a[i]=0 do i:=i+1;

//writeln(i);readln;

j:=i+a[i];

while j<=n do begin

a[j]:=0;

j:=j+a[i];

end;

i:=i+1;

//for k:=1 to n do write(a[k],' ');readln;

end;

for k:=1 to n do

if a[k]<>0 then ///write(a[k],' ');

writeln;

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

http://nvk26.lutsk.ua/cgi-bin/new-client?contest_id=22 (zboru2017-1, zboru2017-2, zboru2017-3, zboru2017-4, zboru2017-5, пароль 1)

Еволюція

Під час досліджень, присвячених появі життя на планеті Олімпія, вченими було зроблено декілька сенсаційних відкриттів:

$11.     Усі живі організми планети походять від однієї бактерії BitozoriaProgramulis.

$12.     Еволюція проходила крок за кроком (за припущенням вчених – під час змін клімату на планеті).

$13.     На кожному кроці еволюції з кожного виду утворювалися рівно два підвиди, а попередній вид зникав.

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

Щоб не вигадувати назви під час досліджень, вчені пронумерували всі види організмів, що будь-коли існували на планеті. Для цього вони намалювали дерево еволюції із коренем BitozoriaProgramulis, яка отримала номер 1. Далі нумерували види кожного кроку еволюції зліва направо. Таким чином безпосередні підвиди BitozoriaProgramulis отримали номери 2 та 3. Наступними були занумеровані види третього кроку еволюції – підвиди виду 2 отримали номери 4 та 5, а виду 3 – номери 6 та 7, і т.д.

Завдання

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

Вхідні дані

Перший рядок вхідного файлу EVO.DAT містить ціле число N (1N≤100) – кількість етапів еволюції, що відбулися на планеті Олімпія до теперішнього часу. Другий та третій рядки файлу містять по одному натуральному числу, що представляють номери видів, для яких потрібно знайти номер їх найближчого спільного предка.

Вихідні дані

Єдиний рядок вихідного файлу EVO.SOL має містити натуральне число – номер найближчого предка для двох видів.

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

EVO.DAT

EVO.SOL

4

15

12

3

18

233016

233008

14563


Працівники (100 балів)

На заводі кожна з N деталей може бути обробленою на одному з двох верстатів: Aабо B. Кожна деталь має порядковий номер від 1 до N.До обробки деталі поступають послідовно, у відповідності зі своїми номерами. Кількість деталей завжди парна.

Існують правила, за якими визначається чи можна обробляти деталь на певному верстаті.

$11)     Якщо на поточний момент на верстаті Bбула оброблена така ж кількість деталей, як і на верстаті A, то наступна деталь повинна бути оброблена на верстаті A.

$12)     У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки і думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Завдання

Напишіть програму STAFF, що за інформацією про кількість деталей N визначає максимальну можливу кількість працівників заводу.

Вхідні дані

Єдиний рядок вхідного файлу STAFF.DAT містить парне число N (2N≤28) – кількість деталей яку необхідно обробити.

Вихідні дані

Єдиний рядок вихідного файлу STAFF.SOL має містити ціле число – максимальну можливу кількість працівників заводу.

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

STAFF.DAT

STAFF.SOL

4

2

Перший працівник вважає що на верстаті Aнеобхідно обробити деталі 1 та 2, а на верстаті B, відповідно, 3 та 4. Другий  має думку, що на верстаті A потрібно обробити деталі 1 та 3, а на станке B – детали 2 та 4. Інших варіантів послідовності обробки немає.

Розв’язок задачі «Працівники»

Автор: Шаміль Ягіяєв

Розв’язок 1 (Пошук з поверненням)

Найпростіший розв’язок задачі — це перебір усіх можливих варіантів обробки деталей на верстатах. У такому випадку кожного разу, коли буде оброблятися певна деталь, буде розглянуто обидва варіанти верстатів (при цьому буде перевірено, чи задовольняє це наведеним правилом). При такому підході алгоритм буде мати складність порядку O(2N).

Розв’язок 2 (Динамічне програмування)

Твердження. Задача еквівалентна задачі обчислення кількості вірних варіантів розташування n=N/2 пар круглих дужок у арифметичному виразі.

Дійсно, обробка i-ої деталі на верстаті A може означати що i-та дужка у виразу буде відкриваючою „(”, а обробка на верстаті B, що закриваючою „)”. Неважко переконатися у тому що таке формулювання є адекватним початковому, проаналізувавши правила обробки деталей.

Будемо продовжувати розв’язувати задачу, використовуючи таке більш зручне формулювання.

Відомо, що коли кількість пар дужок n=1 кількість різних розташувань дужок дорівнює 1. Нехай K(s)— це розв’язок задачі для будь-якого s<n (K(0)=1). Тоді число K(n) можна отримати наступним чином.

Таким чином, кожне значення від 1 до nнеобхідно обрахувати 1 раз (проміжні результати потрібно зберігати), на що необхідно лінійну кількість операцій. Тобто, загальна складність такого алгоритму, повертаючись до початкового формулювання складатиме O(N).

(2*n)!/(n!*(n+1)!)

(N+2)*(n+3)*

2*3*4*5

S=s+(n+2)/2+ (n+3)/3+….

Розв’язок 3 (Комбінаторні обчислення)

Задача про відшукання кількості розташування дужок у арифметичному виразі є досить поширеною. Послідовність чисел, які утворюються при розв’язанні цієї задачі при n=1,2,… називають послідовністю Каталана. Загальний член цієї послідовності можна обчислити за формулою:

Розв’язок 4 (Масив констант)

Можна помітити, що кількість різних вхідних даних дорівнює 13, тобто усі ці випадки можна перелічити у програмі, заздалегідь обрахував відповіді на них. Звісно, за час туру неможливо вручну перелічити усі випадки, і доведеться робити це з допомогою комп’ютера.


Дільники

За заданим натуральним числом N необхідно обчислити кількість натуральних чисел, які є дільниками N! (факторіалу числа N).

Наприклад, при N=4, N!=4·3·2·1=24. Це число має такі дільники: 1, 2, 3, 4, 6, 8, 12, 24. Таким чином шукана кількість дорівнює 8.

Завдання

Напишіть програму DIVISOR, що за натуральним N, знаходить кількість дільників його факторіалу.

Вхідні дані

Єдиний рядок вхідного файлу DIVISOR.DAT містить одне ціле число N (1N45).

Вихідні дані

Єдиний рядок вихідного файлу DIVISOR.SOL має містити одне ціле число – знайдену кількість дільників числа N!

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

DIVISOR.DAT

DIVISOR.SOL

4

8

 


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

Статистика

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

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

Нет