Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Школьная олимпиада по Красноярскому краю, 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.TXTOUTPUT.TXT
101
210

Задача 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.TXTOUTPUT.TXT
10 0 1 1
2 2 1 1
0.41421356237309515
2324 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.TXTOUTPUT.TXT
12
1 2 3 4 5
-1 1 1 2 3
14.0
1.0 -1.0
21
-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», если раб будет съеден тигром.

Примеры

INPUT.TXTOUTPUT.TXT
18 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#...###..#
#....T#..#
##########
12
No
2 8 10
##########
#.#...##.#
#.#..###.#
#.#.##...#
#.......##
#..####..#
#....T#..#
##########
12
Yes


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



Источник: http://www.amurutro.ru/