Завдання 1 туру Всеукраїнської олімпіади школярів з інформатики NetOI-2019
(термін прийому розв'язків - до 0 годин 16.11.19)
Задача Coins2019. Як вам відомо, в Україні вилучено з обігу монети 1, 2 та 5 копійок. Ці монети приймаються до обміну. Вам необхідно визначити кількість способів подати на обмін суму в N копійок цими монетами.
Технічні умови. Програма Coins2019 читає з пристрою стандартного введення натуральне число N, не більше 105 і виводить на пристрій стандартного виведення шукану кількість способів.
Приклад
Введення 5
Виведення 4
Задача Jogging. Один з учасників NetOI займається спортивним орієнтуванням та періодично бере участь у змаганнях. Цього разу правила змагання трохи незвичні. Існує N контрольних пунктів, усі розміщено на прямій. Пункти мають свої координати. Спортсмен розпочинає маршрут у точці з координатою Q i має вiдвiдати K пунктів. Яку мiнiмальну відстань він має подолати?
Технiчнi умови Програма Jogging читає два натуральних числа - N та K (обидва не бiльшi за 105). Далі програма читає рівно N цілих чисел, кожне з яких за модулем не перевищує 105 - координати контрольних пунктів, далі одне ціле число, що за модулем не перевищує 105 - координата, з якої починає спортсмен. Програма має вивести єдине число - мiнiмальну відстань, яку треба подолати, аби досягти мети i вiдвiдати K контрольних пунктів.
Приклади
|
|
||||||||
|
|
|
||||||||
|
|
|
Задача Minandmax. Тарас, молодший брат Михася, дуже хоче погратися одним з його масивів. Михась, аби не гаяти можливість навчити малюка чомусь новому, поставив йому таку умову: “Ось тобі масив цілих чисел. Знайди у ньому «найслабший» фрагмент з елементів, що йдуть підряд, довжиною не менш ніж 2, тоді можеш погратися з цим масивом”. При цьому він додав, що «силою» фрагмента масиву є різниця максимального та мінімального значень в даному фрагменті. Допоможіть Тарасу.
Технічні умови. Програма читає зі стандартного пристрою введення два рядки. Перший рядок містить число N (2 ≤ N ≤ 10000) – довжину масиву. Другий рядок містить елементи масиву (цілі числа, за абсолютною величиною не перевищують 109). Програма виводить на пристрій стандартного виведення єдине число – силу «найслабшого» фрагмента.
|
Введення |
Виведення |
|
2 1 3 |
2 |
|
3 1 1 1 |
0 |
|
5 1 2 1 2 1 |
1 |
Задача Toys2019. У класі НУШ встановили автомат, який продає іграшки (реформа освіти!). Учні, звичайно ж, вишикувались у чергу, але з’ясувалося, що:
- Вартість іграшки – 1 гривня;
- Кожен учень може придбати лише одну іграшку;
- Автомат приймає лише купюри 1, 2 та 5 гривень і видає за потребою решту;
- У кожного учня є лише одна купюра;
- Якщо автомат не має чим видати решту, він зупиняється;
- На початку роботи в автоматі немає жодної купюри;
- Учні категорично не хочуть мінятися місцями в черзі і пропускати інших учнів.
Скільки учнів зможуть придбати іграшки?
Технічні умови. Програма Toys2019 читає з пристрою стандартного введення в першому рядку кількість учнів N – натуральне число, не більше 105, в другому – N розділених пропуском чисел 1, 2 або 5 – номінали купюр учнів в черзі, починаючи від автомата. Програма виводить на пристрій стандартного виведення єдине число – максимальну кількість учнів, що придбають іграшки.
Приклад
Введення
7
1 2 1 2 5 5 1
Виведення
5
Задача Buffet. У буфеті фізико-математичної школи (не дивуйтеся, вони поки існують!) всі ціни – нескоротні звичайні дроби з додатними чисельниками і знаменниками. Вчора до буфету привезли A булочок і B пиріжків загальною вартістю S1, а сьогодні – C булочок і D пиріжків загальною вартістю S2. Допоможіть буфетниці визначити вартість одної булочки і одного пиріжка.
Технічні умови. Програма Buffet читає з пристрою стандартного введення у єдиному рядку три натуральні числа A, B, S1, а далі три числа C,D, S2. Всі числа не перевищують 105 та розділені пропусками. Програма виводить на пристрій стандартного виведення вартість одної булочки - розділені пропуском чисельник і знаменник, а далі вартість одного пиріжка у тому ж форматі. Якщо однозначно визначити вартості булочки і пиріжка неможливо, треба вивести 0 0 для кожного з виробів.
Приклади
Введення Виведення
1 3 5 2 6 10 0 0 0 0
Введення Виведення
4 3 5 2 3 4 1 2 1 1
Завдання підготували Г.Непомнящий, М.Стречень, Ю.Пасіхов