Напишіть програму, яка за натуральними числами A, B та k різними простими числами знаходитиме кількість чисел у діапазоні від A (включно) до B (включно), які не діляться на жодне з перелічених простих чисел.

Технічні умови. Програма  Division має прочитати з клавіатури в одному рядку спочатку числа A, B (1 ≤ A < B ≤ 10¹⁸), потім кількість простих чисел k (1 ≤ k ≤ 100), потім k штук різних простих чисел, кожне з яких  не більше 10¹⁸.

Програма має вивести на екран єдине ціле невід’ємне число — кількість чисел у діапазоні від A  до B включно, які не діляться на жодне з перелічених простих чисел.

Приклад

Введення

17 42 3 2 3 5

Виведення

7

Пояснення до прикладу. Числами в діапазоні від 17 до 42, які не діляться ні на 2, ні на 3, ні на 5, є числа 17, 19, 23, 29, 31, 37 та 41. Їх 7 штук.

Задача Prize

Для розігрування грошових призів використали ігровий апарат, конструкція якого складається з вертикально розміщеної плоскої основи та прикріплених перпендикулярно до неї N стержнів (N – квадрат деякого натурального числа), пронумерованих від 1 до  N (розміщення та нумерація стержнів показана на малюнку). Корпус ігрового апарата обмежує рух кульки так, що її шлях обов‘язково починається з першого стержня, та закінчується на останньому. 

В розіграші беруть участь рівно N учасників, кожен з яких отримує свій оригінальний номер (від 1 до  N) та перед початком розіграшу робить ставку, прикріплюючи картку зі своїм номером до одного з стержнів, кожен до свого. Розіграш проводять, впускаючи кульку зверху в ігровий апарат. Стержні, на які кулька під час свого руху падає вертикально вниз, вважаються виграшними, тобто, виграшними є номери учасників, що зробили ставку на ці стержні, а сума виграшу дорівнює сумі виграшних номерів учасників розіграшу (див. малюнок).

Під час одного з розіграшів сума виграшу була найбільшою з усіх можливих для даних ставок. Знайдіть цю суму та номери учасників, що отримали виграш.

Технічні умови. Програма Prize читає  число N (4≤N≤10000), а в наступному рядку  N чисел  k₁,  k₂, … , k_N,  де k_i – номер учасника розіграшу, що зробив ставку на  i-й стержень. Всі числа розділено пропусками.

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

Приклад.

Введення:    

9

2  8  5  3  6  1  9  7  4

Виведення:   

29

2  4  6  8  9

 В спортивному залі учні вишикувалися в колону, один за одним. Учитель фізкультури дав команду перешикуватися таким чином, щоб всі дівчатка опинилися попереду хлопчиків. Яку мінімальну кількість переходів в інше місце колони повинні виконати учні? (Перехід означає, що учень чи учениця займає місце між двома іншими або стає в будь-який кінець колони).

Технічні  умови. Програма Column читає з клавіатури число N (1£N£32765) – кількість учнів в колоні, а далі N чисел (0  або 1). Всі числа розділено пропусками.(0 - умовне позначення дівчинки, 1 - хлопчика). Програма вивдить на екран єдине число - шукану величину.

Приклади

Введення

2 1 0
Виведення
1

Введення

5 0 0 1 1 1

Виведення

0

Напишіть програму, яка допоможе пану Диваку прийняти рішення. Програма повинна, прочитавши таблицю відстаней між містами, знайти довжину маршруту, якщо просто відвідати усі міста по порядку, та мінімальну можливу сумарну довжину пари маршрутів, що задовольняє вимогам компромісного варіанту (обидва починаються в першому за словниковим порядком місті, закінчуються в останньому, всередині кожного маршруту всі міста відсортовані, через кожне місто проходить хоча б один з двох маршрутів).

Технічні умови.  Програма Towns має прочитати з клавіатури спочатку задане число N (3 ≤ N ≤ 555), потім N∙(N–1) / 2 чисел, що задають відстані (від 1‑го міста до 2‑го, 3‑го, …, N‑го, потім від 2‑го до 3‑го, …, N‑го, і т. д.). Відстані є натуральними (цілими строго додатними) числами, не більшими 10⁶. Всі числа записані в одному рядку, розділені пропусками. Для відстаней гарантовано виконується нерівність d(i,j)+d(j,k) ≥d(i,k).

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

Приклад

Введення:

5 1 8 6 3 7 5 2 11 7 5

Виведення

24 26

Задача Іnstigator

Маленький хлопчик вирізав  з  паперу в клітинку багатокутник, причому всі розрізи йшли по сторонах кліток. Йому цікаво, за який час згорить багатокутник, якщо підпалити його в певній вершині. Папір горить рівномірно в  усіх напрямках, і швидкість розповсюдження вогню рівна 1 стороні клітинки в секунду. Напишіть програму, яка визначає, який час пройде, перш ніж багатокутник згорить повністю.

Технічні умови.

Програма Іnstigator   читає з клавіатури кількість вершин багатокутника N (4<=N<=500), а далі -  N пар чисел – координати  вершини в порядку обходу периметра багатокутника.  Координати кожної вершини -  два цілі числа, таких, що не перевищують по абсолютній величині 10000. Багатокутник підпалюється в першій вершині. Опис коректний – сторони багатокутника не мають спільних точок (крім сусідніх), і кожна вершина сполучає дві взаємно перпендикулярні сторони.

Програма виводить  одне дійсне число – кількість секунд, які пройдуть до повного згорання багатокутника. Допустима помилка, що не перевищує 0,001% від правильної відповіді.
Приклади

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