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

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

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

Задача Wagon. Водій-далекобійник їде  своєю фурою по довгій прямій дорозі з багатьма світлофорами. Для кожного світлофора він знає, як довго буде горіти червоне і зелене світло (цикл повторюється нескінченно).

Коли водій починає свою поїздку, всі світлофори горять червоним і тільки що розпочали свій цикл. Фура рухається рівномірно зі швидкістю в  одну одиницю шляху в секунду, зупиняється і стартує миттєво, а жовте світло у даного типу світлофорів відсутнє. Коли світлофор червоний, фура миттєво зупиняється і чекає, поки не ввімкнеться  зелене світло, після чого миттєво розпочинає свій рівномірний рух. Напишіть програму  яка визначає, скільки часу потрібно водієві, щоб досягти кінця дороги. Початок дороги має координату 0, кінець має координату  L.

Технічні умови Програма  Wagon читає з пристрою стандартного введення два цілі числа N та L (1 ≤ N ≤ 10⁴, 1 ≤ L ≤ 10⁶), кількість світлофорів на дорозі та довжину дороги.

Кожен з наступних N рядків містить три цілі числа D, R і G, що описують один світлофор (1 ≤ D <L, 1 ≤ R ≤ 10⁶, 1 ≤ G ≤ 10⁶). D – координата світлофора,. R і G позначають тривалість відповідно червоного та зеленого сигналів. Світлофори  впорядковані у порядку зростання D. Жодні 2 світлофори не мають однакової координати.  Програма виводить  на пристрій стандартного виведення час (у секундах),  що потрібен водієві для подолання дороги.

   Приклади

Введення 2 10 3 5 5 5 2 2   Виведення 12

Введення 4 30 7 13 5 14 4 4 15 3 10 25 1 1  Виведення 36

 

 

 

 

 

 

 

 

 

 

Задача Track. Група, що складається з 3-х автомобілів великої вантажопідйомності (фур) завантажується на складі компаніїї «Вантажтранс». Спочатку завантажили в фури a, b, та c контейнерів відповідно. Але водії почали вимагати, аби фури були навантажені однаково. На складі було 2 крани, кожен з яких міг за 1 хвилину завантажити один контейнер. Крани почали працювати синхронно, зрозуміло, що на одну фуру 2 контейнера одночасно вантажити не можна.   Допоможіть водіям розрахувати, через яку мінімальну кількість хвилин вони зможуть відправитися в рейс. Технічні умови. Програма Track читає з пристрою стандартного введення три числа a, b, c через пропуски (1 ≤ a,b,c ≤ 5·10⁸). Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади

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

1 2 3               3        

2 2 2               0

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

 

 Задача Channel.  Пропускна спроможність каналів зв’язку компанії  «FreeNet» вимірюється цілим додатнім числом і зараз складає a одиниць. З метою покращення інтернету в школах області менеджмент компанії вирішив збільшити спроможність до значення b. Потрібні нові канали зв’язку. Технічно  можливо прокладати канали зв’язку двох типів: L та LL. Канал типу L збільшує пропускну спроможність на 1, а канал типу LL – на 2. Звичайно, є бажання прокласти найменшу кількість  каналів. Канали  потрібно вводити в дію по одному, одразу після облаштування. Але, якщо поточна пропускна спроможність стає кратною цілому числу c, все обладнання «зависає», школи взагалі лишаються без Інтернету. Потрібно написати програму, яка по заданим значенням a,b,c порахує, яку мінімальну кількість каналів  потрібно збудувати.

Технічні умови. Програма Channel читає з пристрою стандартного введення 3 числа  a b  c через пропуск. (1 ⩽ a < b ⩽ 10⁹, 2 ⩽ c ⩽ 10⁹, a не кратне c, b не кратне c). Програма виводить на пристрій стандартного виведення єдине число -  шукану величину.

Приклади

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

2 7 3             3

4 10 3           4

Коментар до прикладів. В першому прикладі можливо діяти так: будувати лінії  LL, L, LL. Пропускна спроможність  міняється так: 2 → 4 → 5 → 7. В другому прикладі можна діяти так: будувати канали L, LL, L, LL. Пропускна спроможність  каналів міняється таким чином: 4 → 5 → 7 → 8 → 10.

Задача Division2020. Водій-далекобійник  розпочав їздити міжнародними маршрутами  своєю вантажівкою. Його найбільша проблема - кордон з Польщею. Кордон є пунктом в'їзду до Європейського Союзу, тому кожна вантажівка ретельно оглядається. Через це (і не тільки через це…) водій мусить  там чекати кілька годин, а інколи і кілька діб. Щоб вбити час, він придумує різні логічні та математичні ігри. В одній такій грі він спочатку зчитує номери з N номерних знаків і записує їх на аркуші паперу. Тоді  намагається знайти ціле число M, більше за 1, так що всі цілі числа, записані ним на папері, давали однаковий залишок при діленні на М. Звичайно, він  намагається знайти якомога більше таких цілих чисел M.

Технічні умови. Програма Division2020 читає з пристрою стандартного введення ціле число N (2 ≤ N ≤ 100), кількість цілих чисел на папері. Далі в тому ж рядку через пропуски N цілих чисел  від 1 до 1 000 000 000 (один мільярд). Усі ці цілі числа будуть різними. Вхідні дані гарантують, що принаймні одне ціле число M завжди буде існувати.

Програма виводить на пристрій стандартного виведення усі числа М через пропуски в одному рядку.

 Введення

3  6  34 38

 Виведення

2 4

Введення

 5 5 17 23 14 83

 Виведення

 3

Задача Vus.  Козак Вус потрапив у дивовижний світ. Як вiн з’ясував, цей світ існуватиме рівно n календарних років. Причому кожен рік складається з n місяців, а місяць пiд номером i триває рiвно a_i дiб. Козак одразу зрозумiв, що в цьому свiтi використовують один iз наступних шести форматiв календарних дат: Д.М.Р, Д.Р.М, М.Д.Р, М.Р.Д, Р.М.Д та Р.Д.М (замiсть букви Р пишуть номер року, замiсть М—номер мiсяця, а замiсть Д—день мiсяця).

Вуса зацiкавила кiлькiсть впорядкованих тройок (1 ≤x,y,z ≤ n) таких, що для будь-якого формату, календарна дата x.y.z є коректною (ця дата описує реально існуючу добу). Наприклад, при n = 3, a₁ = 2, a₂ = 3 i a₃ = 1, дата 2.3.1 є коректною для формату Р.М.Д, але не є коректною для формату Д.М.Р (третiй мiсяць триває всього одну добу). У свою чергу, дата 1.1.1 є коректною для всiх форматiв.

Технічні умови.  Програма  Vus   читає з пристрою стандартного введення цiле число n (1 ≤ n ≤ 5·10³)—кiлькiсть мiсяцiв у календарному роцi, далі в тому ж рядку через пропуски  n цiлих чисел a₁,a₂,...,a_n (1≤a_i ≤ n)—кiлькiсть дiб в i-му мiсяцi. Програма виводить на пристрій стандартного виведення одне число—кiлькiсть трiйок.

Приклади

Введення	Виведення	Пояснення до першого прикладу
3 2 1 2 5 4 3 4 2 1	4 30	Розглянемо всi  трiйки: (1, 1, 1)—підходить під всi формати (1, 1, 2)—підходить пiд всi формати (1, 2, 1)—пiдходить пiд всi формати (1, 2, 2)—не пiдходить пiд формати Р.Д.М та Р.М.Д (2, 1, 1)—пiдходить пiд всi формати (2, 1, 2)—не пiдходить пiд формати Д.Р.М та М.Р.Д (2, 2, 1)—не пiдходить пiд формати М.Д.Р та Д.М.Р (2, 2, 2)—не пiдходить пiд формати Д.Р.М, М.Д.Р, М.Р.Д, Р.Д.М, Р.М.Д та Д.М.Р Трiйки (1, 1, 3), (1, 2, 3), (1, 3, 1), (1, 3, 2), (1, 3, 3), (2, 1, 3), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3), (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2) та (3, 3, 3) не пiдходять, бо кiлькiсть днiв в кожному мiсяцi менша за 3 (серед форматів Д.Р.М, Р.Д.М та Р.М.Д буде хоча б один, пiд який трiйка не буде пiдходити).