Задача состоит в следующем:

У игрока изначально есть приз размером 1 очко. Есть также последовательность вопросов n штук.

Для каждого вопроса у игрока есть два действия:

1. Забрать текущий приз и выйти из игры.

2. Попытаться ответить на вопрос. Если он отвечает правильно, то приз удваивается и игра продолжается, иначе игрок не получает ничего.

Если вопросы закончились, то игрок забирает текущий приз и уходит. Нужно выбрать такую стратегию для игрока, чтобы максимизировать математическое ожидание выигрыша. Для каждого вопроса вероятность правильно ответить на него равномерно распределяется между t и 1. Причем, перед тем как решить ответить или нет, мы заранее узнаем эту вероятность.

Примеры:

n = 1, t = 0.5

Ответ: 1.500

n = 1, t = 0.3

Ответ: 1.357

n = 2, t = 0.6

Ответ: 2.560

Объясните пожалуйста, как получаются подобные ответы к задаче.

P.S. Обновил условие, оказывается задача выглядит немного не так.

Закончился очередной этап.
Хотелось бы узнать решения задач A, D, E .

Обсуждаем задачи тут.
Я участвовал в Div.2.
И меня интересует, почему Дейкстра с сетом дает WA#16 в G.
И хэширование + дп + бин.поиск дает WA#2 в J.
Я уже просто запарился искать ошибку.

Всем привет!
Я хочу пролить свет на олимпиады, проводимые в Казахстане. Поэтому расскажу как проходил 1/4 у нас, и в частности у моей команды AUPET 1.

Выступаю я уже в 3-й раз, и сразу хочу сказать, что организация 1/4 стал на порядок лучше. Если раньше мы писали контест на МехМате КазНУ в тесных, неудобных аудиториях, где иногда даже не могли поместится за компьютером 3 участника (как это было у нас :) ).
В этот раз 1/4 проходила в молодежном интернет-центре: большой зал, где расположены где-то 16 рядов компов, по типу компьютерных клубов. Команды рассаживали через компьютер, так что места хватило всем, что несказанно радовало. Председателем технического комитета был небезысвестный Артем Игликов, так что касается технической части - об этом можно было не беспокоится. Из софта стояли Eclipse, Visual Studio 2005, FAR. Кто хотел - мог скачать и поставить Delphi. Ничего лишнего.

Посадили нас рядом с командой KBTU 3, членов которой я часто видел на соревнованиях на TopCoder и здесь. Так что впервые на контесте мы познакомились вживую, обсудив насущные проблемы олимпиад в КЗ :). У них стояла оч. сложная задача попасть в 4-ку своего ВУЗа. Нам же нужно было просто нормально выступить, чтобы поехать в Ташкент, на полу-финал. Выступили мы, на мой взгял очень посредственно, в полу-финал вышли без проблем, но чувства удовлетворения от контеста я не получил никакого.
Кстати, в ночь перед контестом, мне приснился очень неприятный сон, в котором я тоже писал контест, вроде какбы 1/4, писал просто ужасно и проснулся в холодном поту. Как оказалось, сон был почти вещим :)

Задачи, которые писали мы, писали так же на 1/4 в Санкт-Петербурге. Однако как обычно, наверное несколько задач нам дали в облегченном варианте, правда питерских задач я еще не видел.
Итак был дан старт, разорван конверт. Я взял себе несколько первых задач, остальные отдал своим сокомандникам (Боте и Игорю). Читаю A,B,C - халявы пока не нахожу. Через 10 минут, Игорь дает мне задачу D, говорит что вроде простая. Я читаю - и вправду простая. Однако от жуткого волнения, которое преследует меня каждый такой контест, не смог нормально закодить и посадил пару багов. В итоге сдал только с +2. Сразу после нее прочитал задачу E, которую сдавали все в первую очередь. Задача была оч. халявная. Однако я слишком торопился и допустил детский ляп и снова +2. В итоге после 37 минут, 2 задачи, 4 штрафа. Просто ужасное начало. В это время некоторые команды КБТУ уже решили по 3 задачи.

Далее следовали задачи H и K. В H после долго вчитывания, я написал какую-то шаманскую эвристику, которую добил до прохождения сэмпла. Отправил - получил WA #5, и решил забить на нее до лучших времен. Переключился на K. Сама по себе задача была несложной. Основная проблема была найти кратчайшее расстояние от бутылки до границы и от границы до следующей границы, т.е. определенную точку. Решал сначала вместе с Ботой, но она ничего путного не предложила и я решил писать тернарный поиск. Хочу сразу добавить, что тернарный поиск я писал 1 раз в жизни, в итоге посадил пару багов в него, искал их потом минут 20, исправлял. Добился прохождения сэмпла, отправляю - WA #6. Подумал, что проблемы с точностью, исправил - все равно WA #6. Бага опять оказалась дурацкой - забыл обнулять границы поиска l,r. В итоге снова +2 на 150 минуте (О боже...)
На самом деле никакого тернарного поиска там не нужно было писать - просто угол падения=угол отражения. (узнал после контеста)
Снова возвращаюсь к H. Вдумчиво взглянув на сэмпл, я нашел одну закономерность, закодил быстро и получил AC.
Итого к 170 минуте мы имели 4 задачи, ни одну не сдал чисто :(, и место в районе 13-14.
К этому же времени Бота ушла домой, потому что ей надо было готовить жрат для гостей. Мы остались вдвоем...

Теперь стоял важный вопрос что решать дальше. Были задачи A,C из открытых. Я решил делать их. Задача A окончательно вынесла мне мозг. Я попеременно думал то над А, то над С. Но ничего путного не находил. В это же время прочитал G,I.
В G решение вроде бы верное пришло сразу - сделать предподсчет по целым координатам. А между ними искать точки тернарным поиском. Однако писать побоялся,  в виду того, что никто ее не сдал, значит кодить придется оч. долго.
В I все было очевидно, но нужно было аккуратно разбирать таблицу результатов, что могло вылиться в долгие часы. А надо было срочно сдавать "быструю" задачу.
Ближе к концу контеста меня стало постепенно осенять по задаче С. Однако каждая моя эвристика давала WA #6. В итоге последняя, которую я не успел закодить, оказалась таки верной. Но было уже поздно.
На замороженном мониторе мы были 15-мы. Лидировали KBTU 1 с 7 задачами. В итоговой таблице мы оказались 16.
Узнав у КБТУ 3 решение задачи А, которое кстати, оказалось очень красивым, мы в расстроенных чувствах собрали вещи и ушли, не дожидаясь церемонии награждения (а зря, нам вроде бы даже майки подарили).
Другая наша команда AUPET 2, состоящая из необстрелянных 2-курсников таки опередила команду магистрантов AUPET 3 и тоже поедет в Ташкент, на полуфинал.

Первые 3 места:
1. KBTU 1 (Байжикенов, Есенаманов, Канапин) - 8 задач.
2. KBTU 5 (Айтбаев, Алмахан, Сатылханов) - 7 задач.
3. KBTU 2 (Уткелбаев, Ли, Есмуханов) - 6 задач.
У остальных 5 задач и меньше. AC получали по всем задачам, кроме B. В целом, в этом году задачи были посложнее, чем в прошлом, но зато они были более сбалансированы.

Резюмирая, могу сказать, что очень расстроен своим результатом, несмотря на то, что в универе меня похвалили. Рассчитывал я как минимум попасть в 10-ку. Например, на KBTU-Open, который проходил 3 недели назад мы выступили гораздо лучше. Но в оправдание могу сказать, что пишу я фактически один, команды как таковой у меня нет, точнее существенной пользы от сокомандников. На весь контест меня не хватает, т.к. думать над всеми задачами сразу - нереально. Наверное, нужно интенсивнее тренироваться. Один плюс, наконец-то мы поедем в Ташкент. Я ждал этого долго. Там хочется реабилитироваться за промах на 1/4.

Ну что же, спасибо всем, кто дочитал :)