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

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

Школа олімпійського резерву з інформатики
Заняття 5 (05.10.2016) PDF Печать E-mail
Добавил(а) 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 до 105 символів, що складається з великих літер латинського алфавіту.

 

Вихідні дані

 

Виведіть "YES" (без лапок), якщо рядок s містить дві непересічні підрядка "AB" і "BA", і "NO" інакше.

 

приклади тестів

 

вхідні дані

 

ABA

 

вихідні дані

 

NO

 

вхідні дані

 

BACFAB

 

вихідні дані

 

YES

 

вхідні дані

 

AXBYBXA

 

вихідні дані

 

NO

 

Примітка

 

У першому прикладі вхідних даних, незважаючи на те, що є підрядка "AB" і "BA", їх входження перетинаються, тому відповідь - "NO".

 

У другому прикладі вхідних даних є наступні входження подстрок: BACFAB.

 

У третьому прикладі немає ні підрядка "AB", ні підрядка "BA".

Читать полностью
 
Заняття 4 (28.09.2016) PDF Печать E-mail
Добавил(а) 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) PDF Печать E-mail
Добавил(а) 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

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) PDF Печать E-mail
Добавил(а) 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 цілих чисел - координати точок  ABCD. Кожне число не перевищує за абсолютною величиною 1000.

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

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

Задача DEMO_B

         Скільки натуральних чисел виду 2a3b5ca,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

 

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) PDF Печать E-mail
Добавил(а) 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(1n,m50). У наступнихnрядках записано поmневід'ємних чисел, які не перевищують109- сам масив.

Вихідні дані

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

Ліміт часу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

Вхідні дані

10

1

2

3

4

5

6

7

8

9

10

Вихідні дані

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)

 
Архів матеріалів PDF Печать E-mail
Добавил(а) 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
 
ACM­ICPC Ukraine 2016, Перший етап Украї на, 16 кві тня 2016 року PDF Печать E-mail
Добавил(а) Administrator   
27.04.16 08:05

завдання (pdf)

ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року


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

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

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




ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

Сьогодні Степан чекає в гості свого друга Василя. Щоб підготуватися до зустрічі, Степану
необхідно відвідати два магазини, розташованих поряд з його будинком.
Від будинку до першого магазину веде доріжка довжини d​ 1
метрів, а до другого магазину веде
доріжка довжини d​ 2
метри. Також існує доріжка, яка безпосередньо сполучає два магазини один з одним,
довжиною d​
3​
метри

Допоможіть Степану обчислити мінімальну відстань, яку йому буде потрібно пройти, щоб
відвідати обидва магазини і повернутися додому.
Степан завжди стартує зі свого будинку. Він повинен відвідати обидва магазини, переміщаючись
тільки за наявними трьома доріжками, і повернутися назад додому. При цьому його абсолютно не
бентежить, якщо йому доведеться відвідати один і той же магазин або пройти по одній і тій же доріжці
більше одного разу. Єдине його завдання ­ мінімізувати сумарну пройдену відстань.
Формат вхідних даних
У першому рядку вхідних даних знаходяться 3 цілих числа d​ 1​
, d​ 2​
, d​ 3​
(1 ≤ d​ 1​
, d​ 2​
, d​ 3​
≤ 10​
8​
) ­ довжини
доріжок.
d​ 1 ​
­ довжина доріжки, що з'єднує будинок Степана і перший магазин;
d​ 2 ​
­ довжина доріжки, що з'єднує будинок Степана і другий магазин;
d​ 3​
­ довжина доріжки, що з'єднує два магазина.

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

Приклад
Стандартне введення Стандартне виведення
10 20 30 60




ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року





ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

Задача C. Підготовка до шахової олімпіади
В університеті, де вчився Степан, вирішили провести шахову олімпіаду. Щоб добре до неї
підготовитись, Степан вирішив спочатку пограти зі своїм сусідом Робертом, якого усі мешканці дома
називали жартома Фішером. Роберт досить пристойно грав у шахи і залюбки погодився допомогти
Степану.
Перші дві зустрічі Степан програв, потів звів партію у нічию, а наступну виграв. Роберт змінив
дебют і Степан знову програв партію, далі була нічия і виграш Степана. Роберт знову змінив дебют і
ситуація повторилась – Степан знову програв партію, далі була нічия і виграш Степана. Усього Степан з
Робертом зіграли досить багато партій, причому ситуація щоразу повторювалася – спочатку Степан
програвав, потім була нічия, а потім – перемога Степана. Треба визначити скільки поразок було у
Степана у перших N партіях.
Формат вхідних даних
Вхідний файл містить одне число – N (кількість партій, 0 ≤ N ≤10​
18​
).
Формат вихідних даних
Одне число – кількість поразок Степана у зустрічах з Робертом у перших N партіях.
Приклад:
Стандартне введення Стандартне виведення
5 3

Задача D Кратне трьом
Дано число. Степан хоче замінити в ньому одну цифру таким чином, шоб нове число ділилось на
3 і було максимально можливим. В заданому числі потрібно обов'язково замінити одну цифру, навіть
якщо задане число ділилось на 3.
Оскільки Степан тільки почав відвідувати факультатив з програмування, то він просить допомоги у вас.
Формат вхідних даних
Дано одне натуральне число. Довжина числа може досягати 100 цифр.
Формат вихідних даних
Виведіть інше натуральне число, що задовольняє умовам:
1. Нове число повинно відрізнятись від даного рівно однією цифрою.
2. Нове число повинно ділитись на 3.
3. Нове число повинно бути максимально можливим з усіх таких чисел.

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





ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

Задача Е З трьох прости чисел
Знайти кількість натуральних чисел з проміжку [A; B] в розкладі на прості множники яких є рівно
3 простих множника.
Формат вхідних даних
В одному рядку два числа через пробіл: A і B, 1 ≤ A ≤ B ≤ 10000000

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

Стандартне введення Стандартне виведення
10 20
8 20
3
4

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

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

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

Приклад:
Стандартне введення Стандартне виведення
11 1 3 9





ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

На площині задана така множина з N багатокутників, що виконуються наступні умови:
1) ніякі два багатокутника не мають спільних точок;
2) для кожного i–го багатокутника існує Pi багатокутників, всередині яких він знаходиться, і N­1­P​ i

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

Приклад
Стандартне введення Стандартне виведення
3
3 ­2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
0 2 1





ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

Задача H Вираз
Для запису числових виразів жителі країни Олімпія використовують наступний формат:
1. Вираз складається з операндів та знаків операцій, розділених пропусками.
2. Операнди: додатні цілі числа.
3. Операції: додавання (позначається знаком +) та множення (позначається знаком *).
4. Вираз розглядається зліва направо. Якщо у виразі зустрічається знак операції, виконується
відповідна операція над двома останніми операндами перед ним, результат операції замінює у виразі
послідовність її операндів і знаку операції, посля чого обчислення продовжується за цим же правилом.
5. Результатом виразу є результат останньої операції.
Обчислимо, наприклад, вираз 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






ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

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

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

Формат вихідних даних
У вихідний файл необхідно вивести одне єдине число – найменшу кількість перекладань кубиків, в
результаті яких висота будь­яких двох стовпчиків не буде відрізнятися більш ніж на один кубик.
Приклад:
Стандартне введення Стандартне виведення
5
3 4 8 2 5
4

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

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

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

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

Приклад
Стандартне введення Стандартне виведення
99 1 105
595 2 655



ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

15187565 3 15187575
15187565 2 15187566
Задача K Безпечний шлях
Межа відомого Вам мінного поля представляє собою многокутник без самоперетинів і
самодотиків. Поза мінним полем (але, можливо, на його межі) задані дві точки А і В.
Вам необхідно знайти шлях мінімальної довжини між цими точками. Очевидно, що шлях не може
перетинати мінне поле, але може проходити через вершини або по ребрах граничного многокутника.
Формат вхідних даних: у першому рядку вхідного файлу міститься чотири цілих числа:
X​
A​
, Y​
A​
, X​
B
i Y​
B ​
­ координати заданих точок. Другий рядок містить ціле число N(3 ≤ N ≤ ​ 100) ­ кількість


вершин граничного многокутника. Кожен із наступних N рядків містить координати X i Y однієї
вершини многокутника. Опис вершин задано в порядку їх обходу проти годинникової стрілки. Усі
координати ­ цілі числа в проміжку від ­100 000 до 100 000.
Формат вихідних даних: виведіть одне число ­ довжину найкоротшого шляху, з точністю до 0.0001.
Стандартне введення Стандартне виведення
0 0 5 5
4
1 0
3 0
3 2
1 2
7.2361





ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

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






ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

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

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

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

Приклад
Стандартне введення Стандартне виведення
10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101
21






ACM­ICPC Ukraine 2016, Перший етап
Украї на, 16 кві тня 2016 року

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

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

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

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

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

Стандартне введення Стандартне виведення
2
0 0 3
5 0 3
­3.0 0.0
2.0 0.0
9.4247780
2
0 0 2
5 0 2
­2 0
3 0
­1

 
Готуємось до олімпіади – 3 PDF Печать E-mail
Добавил(а) Administrator   
15.01.16 21:09

Готуємось до олімпіади – 3
Опорний конспект по с++

№ Завдання Програмний код
Структура програми

#include "iostream"
#include <math.h>
using namespace std;
int main()
{
int a,b;
double 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");
Заокруглення кількості знаків після коми double a;
a=3.14
cout.precisio(2);
cout<<fixed<<a<<endl;

Обчислити площу трикутника за координатами #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;
}
Зчитати n чисел int n,a[1000];
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
Зчитати рядок з n чисел int n,a[1000];
n=0;
while (! cin.eof())
{cin>>a[n];
n++;
}
Зчитати рядок цифр і вивести його в зворотному порядку char a[1000];
cin>>a;
for(int i=strlen(a)-1; i>=0;i--)cout<<a[i];
Вивести масив з n чисел через пропуск for(int i=0;i<n-1;i++)cout<<a[i]<<” “;

cout<<a[n-1[<<endl;
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;

Підрахувати кількість кожної цифри в числі 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;
Відсортувати масив в порядку зростання 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;
}
Обчислити суму додатних елементів в парних рядках прямокутної таблиці 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;
}
Перевірити чи квадрат є латинським.
Латинським квадратом в математиці називається таблиця розміру n × n заповнена n різними елементами так, що в кожному стовпці і кожному рядку всі елементи зустрічаються по одному разу. Прикладом латинського квадрата може бути: int n,i,j,a[100][100], int b[100];
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>a[i][j];
int f=0;
// перевірка рядків
for(i=0;i<n;i++)
{
for (int k=0;k<n;k++)b[k]=0;
for(j=0;j<n;j++)
if (b[a[i][j]]==0 &&a[i][j]<=n) b[a[i][j]]=1; else f=1;
}
// перевірка стовпців
for(j=0;j<n;j++)
{
for (int k=0;k<n;k++)b[k]=0;
for(i=0;i<n;i++)
if (b[a[i][j]]==0 &&a[i][j]<=n) b[a[i][j]]=1; else f=1;
}
if(f==0) cout<<”yes”<<endl; else cout<<”no”<<endl;
В діапазоні єдиного аркуша файлу дано прямокутне поле nхm, клітинки якого або порожні, або містять значення 1. Вертикальною лінією на цьому прямокутному полі вважатимемо набір з двох і більше клітинок зі значенням 1, суміжних по вертикалі, обмежений вгорі та знизу порожніми клітинками або межами поля. Горизонтальною лінією вважатимемо відповідно набір з двох і більше клітинок зі значенням 1, суміжних по горизонталі, обмежений справа та зліва порожніми клітинками або межами поля. Тобто одна клітинка може належати не більш, ніж одній вертикальній та не більш, ніж одній горизонтальній лініям.
На рисунку нижче вертикальні лінії позначені червоним, горизонтальні – синім кольором.

Виведіть загальну кількість лінії в діапазоні. int a[100][100];
int main()
{int n,m,i; cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>a[i][j];

int s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==1 && a[i-1][j]==1 && a[i][j-1]==1 && a[i+1][j]==0 && a[i][j+1]==0) s=s+1;
else if(a[i][j]==1 && a[i-1][j]==1 && a[i+1][j]==0
|| a[i][j]==1 && a[i][j-1]==1 && a[i][j+1]==0
) s=s+1;
cout<<s<<endl;
}
Рух автомобіля задається координами точок. Підрахувати кількість лівих поворотів.
int x[100],y[100],a[100],b[100],v[100];
int i,n;
//зчитування координат
cin>>n;
for(int i=0;i<n;i++) cin>>x[i]>>y[i];
//обчислення координат векторів
for(int i=0;i<n-1;i++) {a[i]=x[i+1]-x[i];b[i]=y[i+1]-y[i];}
//обчислення векторних добутків
for(int i=0;i<n-2;i++)
v[i]=a[i]*b[i+1]-a[i+1]*b[i];
//підрахунок кількості лівих поворотів векторів
int s=0;
for(int i=0;i<n-2;i++)
if(v[i]>0) s++;
cout<<s++<<endl;

 


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

Статистика

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

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

Нет