Задачи олимпиады "Школьная олимпиада по Красноярскому краю, 9-11 классы"
Задача A. Перестановка - 2
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Рассмотрим Z + = {0, 1, 2, 3, ...} – множество неотрицательных целых чисел. Пусть последовательность an, n ∈ Z + определяется формулой an = n + (−1)n. Таким образом, последовательность an выглядит следующим образом: 1, 0, 3, 2, 5, 4, ... .
Эта последовательность интересна тем, что в ней встречаются все числа из Z +, причем каждое ровно один раз, то есть она является перестановкой чисел из Z +.
Ваша задача – найти такое i, что ai = x.
Входные данные
Входной файл INPUT.TXT содержит целое неотрицательное число x (x ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
0
1
2
1
0
Задача B. Расширение Вселенных
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Астрономы и астрофизики Флатландии ведут активное исследование расширения Вселенной. Недавно они выяснили, что можно считать, что Вселенная представляет собой круг некоторого радиуса, причем этот радиус увеличивается с постоянной скоростью.
Кроме этого, из результатов последних исследований стало ясно, что существует как минимум две Вселенных. Так как они обе расширяются, то рано или поздно у них будет хотя бы одна общая точка.
В модели Флатландских ученых первая Вселенная представляет собой круг с центром в точке (x1,y1), радиус которого возрастает со временем как r1+v1•t, а вторая Вселенная – круг с центром в точке (x2,y2), радиус которого возрастает со временем как r2+v2•t.
Ваша задача состоит в том, чтобы написать программу, которая по описаниям Вселенных найдет ближайший к начальному момент времени, в который у двух Вселенных будет общая точка.
Входные данные
Первая строка входного файла INPUT.TXT содержит описание первой Вселенной. Оно содержит 4 целых числа: x1, y1, r1, v1 соответственно координаты ее центра, ее радиус в начальный момент времени и скорость расширения. Вторая строка входного файла содержит описание второй Вселенной в аналогичном формате: x2, y2, r2, v2.
Все числа во входном файле не превышают 104 по абсолютному значению, скорости расширения и начальные радиусы строго положительны.
В начальный момент времени Вселенные не пересекаются и не касаются друг друга.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу с точностью 10-6.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
0 0 1 1 2 2 1 1
0.41421356237309515
2
324 3429 33 389 -134 3498 123 39
0.7176832614131544
Задача C. Оптимизация сепарабельной функции
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Функцию n переменных f(x1, x2, ... , xn) назовем сепарабельной, если она представима как сумма следующего вида: f(x1, x2, ... , xn) = f1(x1) + f2(x2) + ... + fn(xn), где каждая fi зависит только от xi. В рассматриваемой задаче каждая из функций fi является многочленом второй степени от xi.
Задача минимизации заданной функции на гиперпараллелепипеде формулируется следующим образом: «Задана функция f(x1, x2, ... , xn) и множество ограничений a1 ≤ x1 ≤ b1, a2 ≤ x2 ≤ b2, ... , an ≤ xn ≤ bn. Необходимо найти точку (x1*, x2*, ... , xn*) такую, что она удовлетворяет всем ограничениям, и значение функции в ней минимальное среди всех возможных».
Ваша задача состоит в том, чтобы решить задачу минимизации на гиперпараллелепипеде для заданной сепарабельной функции, состоящей из многочленов второй степени.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 1000). Каждая из последующих n строк содержит по пять целых чисел: ai, bi, pi, qi, ri – они соответствуют ограничению ai ≤ xi ≤ bi и функции fi(xi) = pi•xi2 + qi•xi + ri (−1000 ≤ ai ≤ bi ≤ 1000, −10 ≤ pi, qi, ri ≤ 10, pi ≠ 0).
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите минимальное возможное значение f (x1*, x2*, ... , xn*). Во второй строке выведите x1*, x2*, ... , xn*, на которых достигается указанное минимальное значение. Ответ будет считаться правильным, если найденное минимальное значение отличается от правильного не более, чем на 10−3.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
1 2 3 4 5
-1 1 1 2 3
14.0
1.0 -1.0
2
1
-1 1 1 0 0
0.0 -0.0
Пояснение
В первом примере задана функция f(x1, x2) = (3x12+4x1+5) + (x22+2x2+3), где x1 принадлежит отрезку [1, 2] и x2 принадлежит отрезку [-1, 1]. Минимум данной функции достигается при x1=1 и x2=-1, а ее значение равно 14.
Задача D. Лабиринт с тигром
(Время: 2 сек. Память: 32 Мб Баллы: 100)
В средние века в замках Европы был популярен следующий вид казни: в лабиринт, в котором находился тигр, заводили раба. Рабу была известна карта лабиринта и его первоначальное расположение. Тигр обладал очень тонким обонянием, то есть он знал, где находится раб в любой момент времени и мог в кратчайшее время настигнуть раба и съесть, если мог.
Дана схема лабиринта в виде таблицы N×M. Вход в лабиринт находится в левой верхней клетке. В этом же месте находится раб в начальный момент времени. Выход из лабиринта находится в правой нижней клетке. Гарантируется, что от входа до выхода существует путь и что тигр находится в свободной клетке лабиринта. Также известно, что лабиринт ограничен сплошной стеной по периметру.
Необходимо определить длину кратчайшего пути раба до выхода, и сможет ли раб гарантированно выбраться из лабиринта живым, если за единицу времени как раб, так и тигр, могут переместиться в соседнюю по стороне клетку в произвольном свободном направлении (то есть туда, где нет стены).
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа: N и M – длина и ширина лабиринта (4 ≤ N, M ≤ 1000). Далее следует N строк по M символов – описание лабиринта. Символ «#» означает стену, а символ «.» - свободное пространство, «T» - положение тигра в начальный момент времени.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число – длину кратчайшего пути раба, во второй строке выведите «Yes», если раб гарантированно сможет добраться до выхода, и «No» в противном случае.
