1. Задания личной олимпиады

Задача Fourpoints.

В этом году после успешного окончания Турнира Чемпионов инициативная группа решила провести квест. Всего было решено оборудовать четыре станции и теперь надо определить, где необходимо расположить координационный центр квеста. Единственным требованием для его размещения является соблюдение такого условия: суммарное расстояние от координационного центра до каждой станции должно быть минимальным.

Технические условия

Программа Fourpoints сначала читает с клавиатуры (стандартного устройства ввода) единственное натуральное число N (1≤N≤50000) – количество тестируемых наборов. Дальше следуют N строк, каждая из которых содержит координаты четырех попарно различных точек, в которых размещены станции. Все координаты – целые числа, не превышающие по абсолютной величине 10000.

Программа Fourpoints выводит на экран (стандартное устройство вывода) N строк, которые содержат минимальное суммарное расстояние от координационного центра до указанных четырех станций. Ответ будет засчитан, если будет отличаться от правильного не больше чем на 10^-5.

Пример

Ввод	Вывод
2 0 0 0 1 0 2 0 3 0 0 1 1 0 1 1 0	4.0000000 2.8284271

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

 

Задача Regexp

Вам дан некоторый текст S - последовательность строчных букв латинского алфавита. Вам необходимо найти в этом тексте количество подстрок, которые соответствуют паттерну, т.е. шаблону.

Паттерны у нас бывают только вида “A*B” (где вместо А и B могут быть заданы строчные буквы латинского алфавита). Этот паттерн значит следующее:

• строчка начинается с символа А и заканчивается символом B
• длина подстроки, соответствующей паттерну, не считая А и В, делится нацело на K.

К примеру, если у нас есть паттерн “e*s” и k=2, то строчки “es”, “eggs”, “errors”, “ends” подходят под этот паттерн, а вот строчки “elixirs”, “posix” или “regexp” – не подходят.

Технические условия

Программа Regexp читает с устройства стандартного ввода (клавиатуры) строку S - заданный текст длиной не более чем 100 000, который состоит только из строчных букв латинского алфавита. Со следующей строки программа должна считать паттерн - ровно три символа. Последняя строка содержит единственное натуральное число К, которое не превышает 100 000.

Программа выводит на стандартное устройство вывода  (экран) единственное число – искомую величину.

Примеры

Ввод	Вывод
abacaba a*a 1	6
ofoofooof o*f 3	4

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Glassroom.

На уроке физического практикума Василию необходимо построить конструкцию в виде прямоугольника, где все стенки являются зеркалами. Во всех четырех углах конструкции находятся маленькие отверстия, через которые может проходить свет. Необходимо построить прямоугольник такого размера, чтобы когда в его левый нижний угол посветить лазером под углом 45 градусов, луч лазера вышел из правого нижнего угла конструкции (смотри рисунок).

Василию дано N комплектов зеркальных стенок. Каждый комплект состоит из двух зеркал одинаковой длины. Для построения  прямоугольника необходимо использовать ровно два комплекта. Какое максимальное количество прямоугольников можно построить из заданных комплектов одновременно, чтобы выполнялись условия лабораторной.

Технические условия

Программа Glassroom вводит со стандартного устройства ввода (клавиатуры) четное число N (2≤ N ≤10⁷). Затем считывает N натуральных чисел x_i (1≤ x_i ≤10⁹ ) – длины зеркал соответствующего комплекта. Все числа разделены пробелами.

Программа выводит на стандартное устройство вывода (экран) единственное целое число – максимальное количество прямоугольников, которые удовлетворяют условиям задачи.

Пример

Ввод	Вывод
6 2 2 3 4 6 10	2

 

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Puzzle2019. Игровое поле представляет собой прямоугольник из ячеек (5 строк, 4 колонки), на котором размещены плитки. Возможны размеры плиток - 1 * 1, 2 * 2, 1 * 2 и 2 * 1. Известно, что плитка 2 * 2 единственная. Ровно две ячейки свободны, плитки не могут накладываться друг на друга и выходить за пределы поля. За один ход можно переместить одну плитку на одну ячейку по горизонтали или вертикали. За какую наименьшее количество ходов можно получить позицию, в которой клетки (1,2) и (1,3) будут покрываться плиткой 2 * 2?

Технические условия. Программа читает из стандартного устройства ввода 5 строк по 4 целых разделенных пробелом числа в каждой строке - начальную позицию. 0 - пустая ячейка, 1 - плитка 1 * 1, 2 - принадлежит плитке 1 * 2, 3 - принадлежит плитке 2 * 1, 4 - принадлежит плитке 2 * 2. Программа выводит на устройство стандартного вывода минимальное количество ходов. Гарантировано, что плитка 2 * 2 не покрывает одновременно клетки (1,2) и (1,3). Если переместить плитку 2 * 2 Условия предоставления невозможно, программа выводит -1.

Пример

ввод

1 1 0 1

1 4 4 1

1 4 4 1

1 1 1 3

2 2 0 3

вывод

7

Комментарий. Пример соответствует позиции на рисунке.