Задача Soldier. В некотором (догадайтесь сами, в каком)  воинственном государстве солдаты-призывники делают два дела: красят травку и ходят строем. И если с покраской все легко, то строевая подготовка требует много времени и сил, особенно при условии, когда вот-вот очередной военный парад... Плац, по которому будут шагать солдаты нашего героического взвода, представляет собой прямоугольник N×M(2≤N,M≤700) (если принять размер "коробки" взвода солдат за квадрат с единичной стороной),  некоторые клеточки которого заняты другими подразделениями, поэтому взводу ходить через эти клеточки запрещается. Известны также начальный и конечный пункты движения взвода. Сержант Pupkin хорошо знает - солдаты отлично ходят по прямой, а вот команды "налево", "направо" и "кругом" выполняют иногда с ошибками, поэтому он хочет, чтобы на праздничном прохождении взвод сделал как можно меньше поворотов. Помогите сержанту найти маршрут с наименьшим количеством поворотов.

Технические условия. Программа 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 не может быть четным, то ни одно не может и делиться на 4. Для 11 при t = 5 имеем друга 2⁵ +1 = 33.

Задача Maxtriangle. Цензура в геометрическом мире! Многоугольники с количеством сторон, большим 3, под запретом. В связи с этим все многоугольники пытаются превратиться в треугольники (иногда вырожденные). Делают это они таким способом: пока количество сторон не равно 3, выбираются две смежных стороны, которые объединяются в одну, длина которой равняется сумме длин объединенных. Каждому многоугольнику интересно, какой будет его максимально возможная площадь после "треугольнизации". Помогите им в этом!  

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

Задача Trees2018. Робот-проводник модели TouristVasya предназначен для организации туристических походов лесами Подолья. Недавно в нем нашли проблему - в некоторых ситуациях робот может заблудиться в четырех соснах. Работники туристической компании, которая купила робота,  уже поняли алгоритм, по которому робот обходит препятствия: натыкаясь на дерево, робот поворачивает на 90 градусов направо, после чего идет прямолинейно к следующей встрече с деревом (или пока не выйдет из леса).  К сожалению, исправление ошибок программного обеспечения - дело долговременное и дорогое, поэтому туристическая компания решила найти все проблемные маршруты и выдать соответствующие брошюры с рекомендациями туристам. Проблемным маршрутом назовем замкнутую последовательность обхода роботом четырех деревьев, при этом робот никоим образом (двигаясь по алгоритму) выйти из этого маршрута не может.  Вам поручается разработать программу, которая бы по карте деревьев определила бы количество проблемных маршрутов. Маршруты считаются разными, если отличается четверка деревьев, входящих в этот маршрут. Например, четверки (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, то с этого острова нет пути. Программа выводит на устройство стандартного вывода единственное число - максимальное количество разных островов, которые можно посетить.

Примеры

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