Ограничение памяти: 64 М байт

Задача 1. «Погода» (VIP-турнир 2008. E)

Входной файл: weather.in

Выходной файл: weather.out

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

«Погоды стоят совсем никудышные, никогда таких не было» - молвил Мартовский Заяц – «март на исходе, а снег ещё не сошел. Каждый день то дождь идёт, то вообще град. Так, глядишь, и Безумное Чаепитие провести не сможем.» «Не скажи» - ответствовал Белый Кролик – «вот, помнится, в одна тыща девятьсот…ммм…семьдесят пятом погоды ещё хуже были.» «В каком-каком?» - окрысился Мартовский – «как ты можешь это помнить?» «А вот могу! У меня количество осадков за все годы от сотворения мира записано, так что нынешний год самый плохой после одна тыща девятьсот семьдесят пятого» - гордо заявил Кролик.

Ваша задача – по заданной информации о количестве осадков, выпавших в течение различных лет, оценить справедливость утверждения «год X был самым сырым после года Y». Конечно, Белый Кролик несколько прихвастнул, и его записи могут содержать пробелы, поэтому такое утверждение может быть или верным, или правдоподобным или неверным.

Будем говорить, что утверждение верно, если:

- количество осадков, выпавших в год X, в год Y и во все годы между ними, известно;

- количество осадков в год X не больше, чем в год Y;

- для любого года Z, такого, что Y < Z < X, количество осадков строго меньше, чем в год X.

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

Вход

Входной файл состоит из двух частей. Первая часть начинается числом 1 ≤ n ≤ 50000, определяющим количество записей в дневниках Белого Кролика. Затем следуют n пар целых чисел -10⁹ ≤ y_i ≤ 10⁹ и 1 ≤ r_i≤ 10⁹ , свидетельствующих, что r_i миллиметров осадков выпало в году y_i. Вы можете быть уверены, что y_i < y_i+1 для всех 1 ≤ i < n. Вторая часть файла начинается количеством запросов 1 ≤ m ≤ 10000. Затем следуют m пар целых чисел -10⁹ ≤ Y < X ≤ 10⁹.

Выход

Для каждого запроса выведите в отдельной строке слово “true”, если утверждение «год X был самым сырым после года Y» верно, слово “maybe”, если оно правдоподобно, и слово “false”, если оно неверно.

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

weather.in	weather.out
	false
2002 4920	true
2003 5901
2004 2832
2005 3890
2002 2005
2003 2005
	maybe
1985 5782	maybe
1995 3048
2005 4890
1985 2005
2005 2015

Задача 2. “Jewel Trading” (Весенний Турнир имени Мартовского Зайца 2008. C)

Input file: trade.in

Output file: trade.out

Time limit: 1 second

Memory limit: 64M byte

 

You want to sell a diamond to a merchant for a good price. You know so much about how merchant likes the diamond that you have even built a mathematical model for it: He will definitely accept the price p if it's not greater than a certain threshold a, but for a price p higher than it, he must have a think. The higher the price, the lower probability he will accept. Precisely, the probability that he accept price p > a is 1 / (1 + (p - a)^b), where b>1 is a positive constant in your model.

The exact trading process is as follows: you first propose a price (a non-negative integer), then the merchant decides whether to accept. If he accepts, the trade is over and you have no chance to regret. If he does not accept, you propose another price, and so on. You know that the merchant would get angry if you always propose unacceptable high prices, so you promised that the n-th proposal (if there is) is always not greater than a (which he can accept for sure).

Write a program to find an optimal way to propose prices to maximize your expected earning (i.e. the final price).

 

Input

The input consists of two positive integers n, a, and a real number b (1 ≤ n ≤ 100, 1 ≤ a ≤ 1000, 1 < b < 10), b is given to up to three decimal places.

 

Output

Print the expected earning, to two decimal places. It is guaranteed that the maximal earning exists.

Sample Input and Output

trade.in	trade.out
1 10 2	10.00
10 33 3.14	34.41

 

Задача 3. “Тарифы” (Турнир «Экспонента» 2010. H)

Входной файл: payment.in

Выходной файл: payment.out

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

 

С нового года компания Тьмутараканьэнерго установила для населения новые тарифы на электричество. Теперь тарифы прогрессивные, то есть зависят от количества потреблённой энергии (введены для стимулирования экономии электроэнергии):

Количество потреблённой энергии (дж)	Стоимость единицы энергии (тугрики)
1-100
101-10000
10001-1000000
>1000000

Так, если в месяц вы потребили 10123 дж электроэнергии, то вы должны заплатить компании 100 ∙ 2 + 9900 ∙ 3 + 123 ∙ 5 = 30515 тугриков (конечно, не считая штрафов и пеней за несвоевременную оплату и не восторженный образ мыслей). Кроме того, для экономии бумаги Тьмутараканьэнерго теперь присылает одну квитанцию на две квартиры. В этой общей квитанции указываются два числа: стоимость суммарной электроэнергии, потреблённой в двух квартирах, и абсолютная величина разности стоимостей. Если P(Е) – стоимость энергии Е, рассчитанная по новым тарифам, и два домовладения в месяц использовали энергию Е₁ и Е₂, то в квитанции будет указано P(E₁+E₂) и |P(E₁)-P(E₂)|. Если получатели квитанции не могут самостоятельно подсчитать, кому сколько платить, то компания за 100 тугриков предоставляет дополнительную услугу, выдавая отдельную квитанцию старого образца. Но вы, как люди не чуждые математике, конечно, не собираетесь выбрасывать на ветер по 100 тугриков ежемесячно и сами можете извлечь нужную информацию. Для этого у Вас есть P(E₁+E₂), |P(E₁)-P(E₂)| и вы точно знаете, что потребляете электричества не больше, чем соседняя квартира. Однако после недолгого размышления вы поняли, что решением системы двух линейных уравнений тут не обойдёшься, и вообще, лучше это не на бумаге считать, а написать специальную программу.

 

Вход

Входной файл может содержать один или несколько тестов. Каждый тест состоит из двух положительных целых чисел P(E₁+E₂) и |P(E₁)-P(E₂)|, числа не превосходят 10⁹. Тест, состоящий из двух нулей, означает конец данных, обрабатывать его не нужно.

 

Выход

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