Задача Soldier. У деякій (здогадайтесь самі, у якій) войовничій країнi солдати-призовники роблять дві справи: - фарбують травичку та ходять строєм. I якщо з фарбуванням все легко, то стройова підготовка потребує багато часу та сил, особливо за умов, коли ось-ось черговий військовий парад...

Плац, по якому крокуватимуть солдати нашого героїчного взводу, являє собою прямокутник N×M(2≤N,M≤700) (якщо прийняти розмір «коробки» взводу солдат за квадрат з одиничною стороною), деякі клітинки якого зайняті іншими підрозділами, тож взводу ходити через цi клітинки забороняється. Відомі також початковий та кінцевий пункти руху взводу. Сержант Pupkin добре знає - солдати відмінно ходять по прямій, а ось команди «наліво», «направо» i «кругом» виконують іноді з помилками, тож він хоче, щоб на святковому проходженні взвод зробив якомога менше поворотів. Допоможіть сержанту знайти маршрут з найменшою кількістю поворотів.

Технічні умови. Програма Soldier читає з пристрою стандартного введення у першому рядку N - кількість рядків у схема плацу. У другому рядку M - кількість стовпчиків. Далі N рядків по M символів у кожному. Символ «.» означає вільну клітинку, символ «X» зайняту. Також існує рівно один символ «S» та один символ «F», що позначають відповідно початкову та кінцеву точки проходу взводу. Хоча б один маршрут між S та F завжди існує.

Програма виводить на пристрій стандартного виведення єдине число - мінімальну кількість поворотів взводу на маршруті. Перед початком маршу сержант може вишикувати взвод обличчям у будь-яку сторону – як йому це зручно.

Задача Binfriend.  Для натурального числа N назвемо бінарним другом число вигляду 2^t+1 (t - натуральне), що ділиться націло на N. Вам необхідно знайти найменше число з бінарних друзів чи констатувати відсутність таких для кожного з чисел заданого набору.

Технічні умови. Програма Binfriend читає з пристрою стандартного введення число M(1≤M≤100) - кількість чисел у наборі, і в тому ж  рядку рівно M натуральних чисел, кожне з яких не перевищує 10¹⁵. Програма виводить на пристрій стандартного виведення в одному рядку через пропуски  M чисел - мінімальне ціле невід’ємне t таке, що N_i ділить 2^t +1 націло. Якщо такого немає, слід вивести -1.

Пояснення до прикладу:

Для 1, очевидно, мінімальним t буде 0. Оскільки жодне число вигляду 2^t +1 за t>1 не може бути парним, то жодне не зможе i ділитися на 4. Для 11 за t = 5 маємо друга 2⁵ +1 = 33. 

Задача Maxtriangle. Цензура в геометричному світі! Багатокутники з кількістю сторін, що більша за 3, під забороною. У зв’язку з цим усі багатокутники намагаються перетворитись на трикутники (іноді вироджені). Роблять це вони у такий спосіб: поки кількість сторін не дорівнює 3, обираються дві суміжні сторони, що об’єднуються в одну, довжина якої дорівнює сумі довжин об’єднаних. Кожному багатокутнику цікаво, якою буде його максимально можлива площа після «трикутизацiї». Допоможіть їм у цьому!

Технічні умови. Програма  Maxtriangle  читає з пристрою стандартного введення число  N(3≤N≤7000) - кількість сторін опуклого багатокутника. В  цьому ж рядку слідує N натуральних чисел, кожне з яких не перевищує 10⁵ - розміри сторін (сторони задаються у тій послідовності, у якій вони були в багатокутнику). Гарантується, що периметр багатокутника не перевищує 70000.  Програма виводить на пристрій стандартного виведення єдине дійсне число - максимальну площу багатокутника після «трикутизацiї». Відповідь буде зарахована, якщо відносна чи абсолютна похибка не перевищує 10⁻⁵ від відповіді журі.

Задача Trees2018. Робот-провідник моделі TouristVasya призначений для організації туристичних походів лісами Поділля. Нещодавно у ньому знайшли проблему - у деяких ситуаціях робот може заблукати в чотирьох соснах. Працівники туристичної компанії, яка купила робота,  вже зрозуміли алгоритм, за яким робот обходить перешкоди: натикаючись на дерево, робот повертає на 90 градусів праворуч, після чого йде прямолінійно до наступної зустрічі з деревом (або поки не вийде з лісу).  На жаль, виправлення помилок програмного забезпечення - справа довготривала i дорога, тож туристична компанія вирішила знайти усі проблемні маршрути i видати відповідні брошури з рекомендаціями туристам. Проблемним маршрутом назвемо замкнену послідовність обходу роботом чотирьох дерев, при цьому робот жодним чином (рухаючись за алгоритмом) вийти з цього маршруту не може.  Вам доручається розробити програму, яка б за мапою дерев визначила б кількість проблемних маршрутів. Маршрути вважаються різними, якщо відрізняється четвірка дерев, що входить у цей маршрут. До прикладу, четвірки (1,2,3,4) та (3,2,1,4) однакові, у той час як (1,2,3,5) та (1,5,4,3) - різні.

Технічні умови. Програма Trees2018 читає з пристрою стандартного введення  в першому рядку ціле число N(1≤N≤1000) - кількість дерев на мапі. В наступних N рядках координати дерев у форматі x_iy_i. При цьому кожна з координат не перевищує 10⁹ за абсолютною величиною. Жодних два дерева не розміщені в одній точці. Жодних три дерева не розміщені на одній прямий. Програма виводить на пристрій стандартного виведення єдине число - кількість проблемних маршрутів.

Приклади

Пояснення до прикладів:

Проблемні маршрути такі:

• 3 → 2 → 1 → 4 → 3,
• 5 → 6 → 8 → 7 → 5,

Проблемні маршрути такі:

• 3 → 1 → 5 → 7 → 3,
• 3 → 2 → 5 → 8 → 3,

Задача Islands.  Є n островів, які пронумеровані від 0 до n-1. На нульовому острові знаходиться відомий мореплавець Гама-да-Васко. Йому відомо, що з кожного острова можна потрапити напряму лише на один інший, тобто з острова і можна потрапити лише на острів a_i. Тому, щоб потрапити на якийсь острів, потрібно відвідати деякі інші, а на якісь острови взагалі потрапити неможливо. Мореплавець хоче відвідати якомога більше островів. Для цього він може змінити значення будь-якого a_i. Скільки різних островів Гама-да-Васко зможе відвідати, якщо він може змінити шлях з будь-якого острова?

Технічні умови. Програма Islands читає з пристрою стандартного введення число n(1≤n≤2·10⁵) - кількість островів, а далі n чисел a_i(-1≤a_i<n) - острів, на який веде шлях з острова i, якщо a_i=-1, то з цього острова немає шляху. Програма виводить на пристрій стандартного виведення єдине число - максимальну кількість різних островів, які можна відвідати.

Приклади

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