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

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

Школа олімпійського резерву з інформатики
Заняття (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

 
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

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

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

 


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

Статистика

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

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

Нет