1. ЗАДАЧИ КОМАНДНОЙ ОЛИМПИАДЫ

Задача Душа жаждет полета… (tourist3D).

Устала баба Яга делать пакости людям и решила отдохнуть. Как известно, лучший отдых – это туризм, а поэтому решила она отправиться в дальние края: себя показать и на других посмотреть. Летать на ступе ей смертельно надоело и решила она отправиться в путешествие на новом транспортном средстве – душа жаждет полета... Кроме того, путешествовать одной мало интересно, а поэтому пригласила с собой в путь баба Яга Колывана.

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

В начальный момент времени 0 их абсолютно упругие тела впервые оторвались от плоской поверхности в точках (x₁, y₁, 0) и (x₂, y₂, 0) со скоростями (v_x1, v_y1, v_z1) и (v_x2, v_y2, v_z2). Ускорение свободного падения g в выбранной бабой Ягой местности равняется в точности 10. Необходимо найти минимальное (за все время полета в однородном гравитационном поле над плоской поверхностью) расстояние между оседланными бабой Ягой и Колываном абсолютно упругими телами.

Формат ввода/вывода.

Программа tourist3D считывает с клавиатуры (стандартного устройства ввода) числа через пробел x₁, y₁, 0,v_x1, v_y1, v_z1x₂, y₂, 0,v_x2, v_y2, v_z2 (координаты z гарантированно равняются нулю, но все равно задаются во входных данных). Все значения координат и скоростей являются целыми числами, не превышающими по модулю 1000. Кроме того, точки старта (x₁, y₁, 0) и (x₂, y₂, 0) не равны между собой и v_z1>0, v_z2>0.

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

Пример входных и выходных данных.

Задача Квадратное уравнение (ax2pbxpc).

После приятного отдыха в обществе бабы Яги Колыван решил поразмять мозги математическими вычислениями,чтобы не ошибаться в подсчете игровых долгов. Самым любимым его занятием на досуге является решение квадратных уравнений. Однако при решении большого их количества и ошибку легко допустить! Вот и просит Колыван вас написать программу, решающую квадратные уравнения вида ax²+bx+c=0, если известно, что ни один из коэффициентов a, b, c не равен 0 в точности, но некоторые из них могут быть весьма близки к нулю.

Формат ввода/вывода.

Программа ax2pbxpc считывает с клавиатуры (стандартного устройства ввода) три действительных числа a, b и c, причём модуль каждого из них — в диапазоне от 10^–12 до 10⁺¹². Гарантированно будут вводиться только такие тройки a, b, c, при которых уравнение имеет два различных корня, ни один из которых не равен нулю в точности.

Программа ax2pbxpc выводит на экран (стандартное устройство вывода) два найденных корня через пробел (сначала меньший, потом больший). Ответ будет засчитан, если значения обоих корней найдены с относительной погрешностью не хуже 1%.

Пример входных и выходных данных.

Задача И снова пузырек (bubblesort).

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

для k от 1 до N-1

для j от 1 до N-k

если A[j] < A[j+1]

переставить A[j] и A[j+1]

Начав выполнять перестановки по описанному алгоритму, Колыван понял, что работа выполняется очень медленно, и хочет оценить необходимое время для ее выполнения. Помогите Колывану оценить время работы сортировки, подсчитав для каждого элемента таблицы количество операций перестановки, проведенных над ним.

Формат ввода/вывода.

Программа bubblesort считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100000) – количество сортируемых чисел; а затем N целых чисел – элементы сортируемой таблицы (1<=A[i]<=10⁹,все элементы различны), разделенные пробелами.

Программа bubblesort выводит на экран (стандартное устройство вывода) N чисел, каждое из которых является количеством операций перестановки, проведенных над числом, которое стояло на этом месте в исходной таблице.

Пример входных и выходных данных.

Задача Распил (SLICE)

После многочисленных попыток сэкономить и внесения изменений в проект строительства Колыван, наконец-таки, получил бассейн кубической формы с ребром 1 м. Но даже после такого существенного уменьшения затрат все равно он не может успокоиться и хочет заработать на эксплуатации бассейна. Случайно он узнал, что богатыри собираются проводить соревнования скейтбордистов и им нужен полигон. Полигоном может служить плоскость, проходящая через три точки, которые находятся на поверхности воображаемого куба, создаваемого бассейном. Чтобы не запутаться, Колыван связал один из углов куба с системою декартовых координат. Затем, используя все свои связи, узнал координаты точек на поверхности этого воображаемого куба. Теперь его цель вычислить площадь полигона, который является частью плоскости, проходящей через заданные три точки и ограниченный гранями воображаемого куба, чтобы определить оплату за использование этого полигона.

Формат ввода/вывода.

Программа SLICE читает с клавиатуры (стандартного устройства ввода) три тройки действительных чисел – координаты трех точек (числа в диапазоне [0; 1]), разделенные пробелами. Гарантируется, что точки не лежат на одной прямой и не принадлежат все одновременно одной грани куба.

Программа SLICE выводит на экран (стандартное устройство вывода) одно действительное число – искомую площадь. Ответ необходимо получить с максимально возможной точностью.

Пример входных и выходных данных