Задача 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

Предисловие жюри

Мы предлагаем вам решить известную задачу. Возможно, кто-то из вас имел возможность уже получить ее полный балл. (https://www.e-olymp.com/uk/problems/122)

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

Горный туристический комплекс состоит из n турбаз, соединенных между собой 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.

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