1. Задания олимпиады

Завдання ІІІ (обласного) етапу Всеукраїнської олімпіади з інформатики 2018-2019 н.р.

2 лютого 2019 р.                                                                         https://new.netoi.org.ua

 

Задача Amount. Представити задане число у вигляді суми чотирьох різних натуральних чисел, причому щонайменше 3 з них мають бути простими.

Технічні умови. Програма Amount читає з пристрою стандартного введення задане натуральне число  N  (4≤N≤10⁹)  Програма виводить на пристрій стандартного виведення 4 натуральних числа через пропуск (три перших з них обов’язково прості) таким чином, щоб їх сума була рівна N. Якщо зробити це неможливо, виведіть чотири нулі через пропуски.

Приклади

Введення

20

Виведення

2 3 5 10

Введення

4

Виведення

0 0 0 0

Задача Skiers. Один з кращих способів провести вільний час взимку - катання на лижах. N дітей збиралися зробити це під час зимових свят. На жаль, не у всіх є свої лижі, тому діти погодилися принести все, що можна було знайти в своїх підвалах. Загалом  вдалося зібрати рівно 2*N лиж, але вони були різної довжини. Кожна дитина отримає дві лижі довжиною a та b і буде незадоволена на величину |a-b|

Діти хотіли б обмінятися своїми лижами так, щоб сумарне незадоволення дітей було якомога меншим, тобто S=|a1-b1|+|a2-b2|+…|aN-bN| мінімальне. Допоможіть їм.

Технічні умови.  Програма Skiers читає з пристрою стандартного введення натуральне число N, не більше 100000, далі через пропуск 2*N натуральних чисел, не більших 1000-довжини лиж. Програма виводить на пристрій стандартного виведення єдине число – мінімальне сумарне незадоволення дітей.

Приклади

Введення                 Виведення

3 1 2 3 1 2 3             0

Введення                Виведення

3 1 2 3 4 5 6             3

Задача Coffee.   Програміст  Анатолій Васильович дуже полюбляє пити каву. Він знає, якщо коли вип’є чашку кави перед виконанням певного завдання, то  витратить на нього на 20%  менше часу в порівнянні з роботою  без кави. Але на заварювання кави теж необхідно витратити певний час! Вам необхідно визначити, за яку мiнiмальну кiлькiсть робочих днiв Анатолій Васильович зможе справитися з усіма своїми завданнями, якщо у нього є запас кави на K чашок. Керівник проекту вже наперед визначив необхідну кількість часу для кожного завдання. Завдання необхідно виконувати послідовно. Щодня по законодавству працювати (та заварювати каву!)  можна  упродовж не більше ніж 480 хвилин (8 годин). Якщо залишок робочого часу не дозволяє виконати наступне завдання, то програміст почне його виконувати наступного дня. Звернiть увагу, що магiчна дiя чашки кави впливає лише на одне завдання, i що не можна випивати перед виконанням завдання бiльше однiєї чашки кави. Напишіть програму Coffee, яка б знаходила мінімальну кількість днів, яку необхідно витратити на виконання всіх завдань. Вимоги випити всю каву не ставиться. Вчорашня кава магічної сили не має.

Технічні умови. Програма Coffee читає з пристрою стандартного введення перший рядок вхiдних даних, що  мiстить три цiлих числа N, K, L через пропуск — кiлькiсть завдань, кiлькiсть чашок кави та тривалiсть заварювання однiєї чашки кави (1≤N≤1000, 0≤K≤1000, 1≤L≤100). З цього ж  рядка програма читає  N цiлих чисел, роздiлених пропусками — необхiдний обсяг часу для виконання кожного завдання (час задано у хвилинах, кожне число не менше за 1 i не бiльше за 480). Програма має вивести на пристрій стандартного виведення  єдине цiле число — мiнiмальну кiлькiсть днiв, якi необхiдно потратити на виконання всiх завдань.

Приклади

Введення  5 1 10  10 10 10 100 360

Виведення 1

 

 

 

 

 

Задача  Perstr.

Означення 1. Рядок є періодичним, якщо його можна розбити на К однакових підрядків (K > 1). Приклади періодичних рядків:  abcabcabc, hellohello

Означення 2.

Рядок є особливим, якщо обмінюючи його символи місцям, можна отримати періодичний рядок. Наприклад, рядок aabcbc є особливим, так як abcabc є періодичним.

Задача:

Дано рядок S. Треба змінити в ньому мінімальну кількість символів, так, щоб він став особливим.

Технічні умови. Програма Perstr читає з пристрою стандартного введення рядок символів S  (не більше 50000 маленьких латинських літер).  Програма виводить на пристрій стандартного виведення мінімально можливу кількість символів, яку треба замінити, аби рядок став особливим. Вивести тільки число, самі символи виводити не потрібно.

Приклад:

Введення:

qadcscqa

Виведення

1

 

Задача Gcdarray. Дано масив з n чисел. За один хід можна одне з чисел збільшити на 1. Вам необхідно з’ясувати, за яку мінімальну кількість операцій можливо отримати масив, який буде задовільняти  умови:

• a_i ⩽ a_i+1                 для всiх i вiд 1 до n – 1
• найбільший спільний дільник усіх чисел більший за 1.

Найбільший спільний дільник множини додатних чисел — це найбільше додатне число, що одночасно є дільником усіх чисел з множини.

Технічні умови. Програма Gcdarray  читає з пристрою стандартного введення в першому рядку  одне цiле число t  (1 ⩽ t ⩽ 5) — кількість тестів.  Далi читає  t рядків, кожен з яких є описом відповідного  тесту  і мiстить  цiле число n (1 ⩽ n ⩽ 10⁴) — розмiр масиву а далі n цiлих чисел a₁,a₂,...,a_n (1 ⩽ a_i ⩽ 10⁴) — числа масиву. Всі числа розділено пропусками. Програма виводить на пристрій стандартного виведення рядок з t числами через пропуск, кожне з яких - мінімальна кількість операцій, яку необхідно виконати для того, щоб масив задовольняв даним умовам.

 

Приклади

Введення	Виведення
1 3 9 1 16	10
2 4 5 7 3 6 5 4 2 8 16 10	7 8

Примiтка

У першому прикладi можна перше та друге число збiльшити до 10,  тодi найбiльший спiльний дiльник чисел з масиву буде становитиме 2

У першому тестi другого прикладу можна усi числа зробити рiвними  7.

У другому тестi другого прикладу масив можна змiнити до масиву [4,4,8,16,16].