Задача Chart. Крім олімпіад з інформатики, в нашій країні з деякого часу стали проводити олімпіади з ІКТ. Мабуть, і вам доводилось брати в них участь. Автор задачі не дуже розуміє, в чому там змагаються, але пропонує знавцям офісних пакетів таку задачу. Синоптик у Excel створив  гістограму з N стовпчиків. Кожен стовпчик має висоту, яка дорівнює температурі в конкретний день. Ширина стовпчиків дорівнює одиниці їх висоти. Якщо вважати, що максимально можлива температура (висота стовпчика) M, то вся гістограма являє собою поле N×M клітинок, частина яких зафарбована, починаючи з нижньої клітинки кожного стовпчика. Гістограму надрукували, а потім розрізали на смужки шириною в одну клітинку. Перша смужка – це найнижчий рядок клітинок. До її кінця приклали початок другої смужки (другий рядок клітинок) і так далі. Допоможіть знайти кількість зафарбованих фрагментів смужки, адже знавці офісних пакетів цього зробити не змогли.

Технічні умови. Програма Chart читає з пристрою стандартного введення ціле число N(1 ≤ N ≤ 10⁵). В наступному рядку N цілих  чисел - a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) – температури протягом кожного з N днів. Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади

Коментар до прикладу 1.  Синоптик побудував таку гістограму:

Після всіх операцій – 6 зафарбованих фрагментів.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Fibgame. Вам необхідно зіграти з журі в таку гру. Журі загадає число n, що не перевищує 10⁹, а програма повинна його відгадати. За 1 хід ваша програма може запитати у журі (тобто в системи перевірки) остачу від ділення k-того числа Фібоначчі на n (тобто програма виводить запит - число k ( k≤10⁹ ) і може прочитати гарантовано правильну відповідь перевіряючої системи). У розпорядженні програми є 7 спроб. Якщо відповідь готова, програма її виводить (або замість чергового запиту, або після того, коли всі запити використано). Єдина пересторога: якщо ваша програма виводить  запит (тобто чергове k), то, щоб перевіряюча система  змогла відрізнити його від відповіді (тобто задуманого числа n), потрібно  виводити –k  (наприклад, програма бажає дізнатися остачу від ділення 12-го числа  Фібоначчі на задумане журі число, вона виводить  запит -12). А ось відповідь треба вивести без знака «мінус».

Технічні умови. Програма Fibgame все введення-виведення робить на стандартних пристроях (клавіатура та екран) з нового рядка.

Приклад  У двох тестах, доступних для перевірки онлайн, журі задумало числа 5 та 34.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача library2016. Головний бібліотекар найбільшої бібліотеки світу вийшов на роботу після відпустки й з жахом побачив, що всі томи окраси бібліотеки – Збірка Всіх Творів Усіх Часів Та Народів – розставлені у довільному порядку. Він одразу заходився наводити порядок. Оскільки головний бібліотекар – літня людина, він не може переносити великий вантаж. Та, намагаючись якнайшвидше завершити справу, він кожного разу бере два сусідніх томи та переставляє обидва на інше місце, не змінюючи порядку слідування томів й не вставляючи між ними інших томів.

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

Технічні умови. Програма library2016 читає з пристрою стандартного введення натуральне число n (2<n≤10) – кількість томів збірки всіх творів усіх часів та народів, а далі через пропуски n натуральних чисел – номери томів у тому порядку, в якому їх побачив бібліотекар. Гарантується, що всі томи від 1-го до n-го присутні в єдиному примірнику. Програма виводить на пристрій стандартного виведення мінімально можливу кількість перестановок пар сусідніх томів. Якщо такі перестановки не дозволяють впорядкувати всі томи збірки в порядку зростання їхніх номерів, вивести на стандартний пристрій виведення -1.

Приклади

Введення  3 1 2 3
Виведення 0
Введення  3 1 3 2
Виведення -1
Введення  5 5 4 3 2 1
Виведення 3

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Shift. Дано рядок S та рядок А. Необхідно знайти циклічний зсув рядка S з максимальною кількістю входжень в нього рядка А  і вивести не сам циклічний зсув, а саме максимальну кількість входжень серед усіх зсувів. Наприклад, якщо в рядку ABCDA шукати входження рядка АА, то максимальна кількість входжень дорівнює 1 (в зсувах  AABCD чи BCDAA). У рядках гарантовано відсутні пропуски ("пробіли").

Технічні умови. Програма Shift читає з пристрою стандартного введення рядок символів S, а в другому – підрядок А. Довжина кожного рядка не перевищує 10⁶. Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача ACCESS. Готуючись до олімпіади з ІКТ знавці  баз даних (а знавці є, адже всі вивчають ACCESS!) зіткнулися з такою задачею: є база, яка задає орієнтований граф у вигляді таблиці вершин, між якими є ребро. Потрібно зробити запити 2-х видів:

- додати нове ребро до графа;

- повідомити кількість ребер у найкоротшому шляху від  першої вершини до заданої.

Чи ACCESS  «не дуже СУБД» для роботи з базами, чи «знавці не знавці», але не вийшло… Знавці ІКТ просять вас, програмістів, написати програму,  яка буде виконувати вказані запити по мірі їх надходження: повідомляти найкоротшу відстань від першої вершини до заданої та додавати нові ребра. Зрозуміло, що перед початком роботи програми база порожня. А ось відповіді на запити чомусь користувачеві треба отримувати у зворотному порядку.

Технічні умови. Програма ACCESS читає з пристрою стандартного введення у першому рядку два числа N, М (1 ≤ N ≤ 1000, 1 ≤  M ≤  30 000) - кількість вершин та кількість запитів.

У кожному з наступних M рядків міститься інформація про запит до бази:

1. "+ x y"- додати ребро до графа, яке йде з вершини x до  вершини y (1 ≤ x, y ≤ N);
2. "? k" - визначити найкоротший шлях від першої вершини (тобто з номером 1) до вершини з номером  k (тобто  мінімальну  кількість ребер, що входять до такого шляху).

Програма виводить через пропуски в один рядок на пристрій стандартного виведення відповідь на запити про довжину найкоротшого шляху в порядку, зворотному до їх надходження. Якщо шляху від першої вершини до вказаної не існує, виведіть -1.

Приклад

Введення  

2  4
? 2
+ 1 2
? 1
? 2

Виведення     

1 0 -1

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача TouristVasya

Передмова журi

Ми пропонуємо вам розв’язати відому задачу. Можливо, хтось із вас мав нагоду вже отримати за неї повний бал. (https://www.e-olymp.com/uk/problems/122)

Журі це не лякає, а навпаки, саме цей факт був вирішальним при підготовці завдань. Навіть більше, у вас є можливість перевіряти свої розв’язки  перед відправкою на офіційну перевірку необмежену кількість разів на розширеному (правда, не до 100%) наборі тестів, що їх підготувало журі. Ми щиро бажаємо вам успіхів!

Гірський туристичний комплекс складається з n турбаз, з’єднаних між cобою m гірськими переходами (інші маршрути в горах небезпечні). Кожен перехід між двома базами займає 1 день. Туристична група знаходиться на базі a і збирається потрапити на базу b не більш ніж за d днів. Скільки існує різних таких маршрутів (без циклів) від a до b?

Технічні умови. Програма TouristVasya читає з пристрою стандартного введення в одному рядку через пропуски п’ять натуральних чисел n, m, a, b, d (2≤n≤23, 1≤m≤n², 1≤a≤n, 1≤b≤n, a≠b, 1≤d≤min(8,n–1)), а далі в тому ж рядку m пар чисел u, v (1≤u≤n, 1≤v≤n), де кожна пара описує, що існує одноденний перехід, який починається в u і закінчується у v. Усі пари u, v гарантовано різні. Програма виводить на пристрій стандартного виведення одне число — кількість маршрутів (без циклів, тобто без повторень турбаз), які починаються в a, закінчуються в b і мають не більш ніж d переходів.

Приклад

Трьома маршрутами, які відповідають усім вимогам, є:
(1) 2→1→5; (2) 2→1→3→5; (3) 2→4→1→5.

Завдання підготували В. Бездушний, А. Зуєв, Г. Непомнящий, Ю. Пасіхов, І. Порубльов