Завдання на олімпіаду 2015 з програмування.

ІІ етап Всеукраїнської учнівської олімпіади з інформатики

2015 рік

1.    Перестановка(послідовності)

Задано послідовність, що складається з n натуральних чисел. Визначити, чи є вона перестановкою перших n натуральних чисел.

Вхідні дані

В єдиному рядку задано спочатку число n(n≤10000), а потім n натуральних чисел, розділених пропуском. Відомо, що кожне з натуральних чисел менше за 2000000.

Вихідні дані

Вивести 0, якщо послідовність є перестановкою. Інакше слід вивести мінімальне число, що не входить в цю послідовність.

Вхідні дані	Вихідні дані
3 1 4 2	3

2.    Перебудова

У деякій країні було рівно n міст та m доріг між ними. При цьому у цій країні система доріг була влаштована наступним чином:

·  між довільними двома містами не більше однієї дороги;

·  ніяка дорога не з'єднує місто саме з собою.

Після зміни влади новий уряд вирішив провести ряд реформ, серед яких є реформа, яка стосується дорожньої системи країни. Ця реформа складається з двох пунктів:

·  зруйнувати одну з існуючих доріг;

·  побудувати нову дорогу, якої раніше не було, яка не веде з міста у нього ж.

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

Тепер уряд задумався над тим, скільки існує способів провести реформу. Допоможіть йому.

Вхідні дані

Перший рядок містить два цілих числа n і m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000). Наступні m рядків містять по два числа a_i та b_i (1 ≤ a_i, b_i ≤n, a_i ≠ b_i) – номери міст, які з'єднує i-та дорога.

Вихідні дані

Виведіть одне ціле число – кількість способів провести реформу.

Вхідні дані	Вихідні дані
4 4 1 2 2 3 1 3 3 4	8

3.     Примхливий ліфтер

На першому поверсі N-поверхового будинку зібралися К школярів, яким потрібно піднятися вверх, кожному на свій поверх. Ліфтер погоджується зробити тільки один рейс на будь-який поверх, а далі нехай школярі ідуть пішки. У ліфті можуть поміститися всі школярі. Відомо, що всі школярі спускаються пішки вниз на один поверх з однаковим незадоволенням, що дорівнює 1, й піднімаються пішки вверх на один поверх з однаковим незадоволенням, що дорівнює 2. Який поверх повинен вибрати ліфтер, щоб загальне незадоволенням всіх школярів було мінімальним.

Вхідні дані: У першому рядку вхідного файлу INPUT.TXT задаються два числа N (2 ≤ N ≤ 100000) та K (1 ≤ K ≤ 100). N – кількість поверхів у будинку, K – кількість школярів. Числа у рядку розділені пробілами.

У другому рядку записані через пробіл K чисел – номери поверхів, на які хочуть піднятися школярі. Перше число – номер поверху першого школяра. Друге число – номер поверху другого школяра, і т.д. Номер поверху для кожного школяра знаходиться в діапазоні від 1 до N включно.

Вихідні дані: У вихідний файл OUTPUT.TXT потрібно вивести одне число – мінімально можливе значення загального незадоволення школярів Приклади:

Вхідний файл input.txt	Вихідний файл output.txt
5 4 2 3 4 5	5

4.    Голова професора Інтеграл

З Монте-Карло Олег і Тарас полетіли на літаку до Лондона, де їх вже чекав Іван. Поруч з нашими героями летів професор інтеграли, який був запрошений на міжнародний симпозіум. Професор вирішив продемонструвати свою здатність швидко і безпомилково виконувати складні математичні обчислення.

"Припустимо, – сказав професор, – що у нас є N – деяке натуральне число. Спочатку обчислимо факторіал цього числа, тобто N!, а після цього обчислимо суму всіх цифр числа N!. Якщо сума виявиться більше, ніж 9, треба знову обчислити суму вже для отриманого числа і цю процедуру повторяти до тих пір, поки не отримаємо число в діапазоні від 1 до 9. Зрозуміло? ".

"Так" – відповів Олег.

Ну а далі сталося диво. Яке б початкове число не називали Олег і Тарас, професор не моргнувши оком, тут же називав правильну відповідь – число від 1 до 9. Спробуйте написати програму, яка б моделювала інтелектуальні здібності професора Інтеграла.

Вхідні дані:

Перший рядок вхідного файлу містить єдине число, N(1≤N≤10⁹).

Вихідні дані:

У вихідний потік введіть одне єдине число яке повідомив професор Інтеграл нашим героям.

Вхідний файл input.txt	Вихідний файл output.txt
2	2