e-olymp
Соревнования

Azerbaijan Student Finals

Отладка

Ваш модный отладчик не поможет вам в этом вопросе. Существует много способов, с помощью которых код может производить различное поведение между сборками отладки и выпуска, и когда это случается, возможно, придется прибегнуть к более примитивным формам отладки.

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

Однако для добавления каждой инструкции printf в код требуется некоторое время, да и программа может иметь много строк. Поэтому, возможно, лучший план будет заключаться в том, чтобы поместить инструкцию printf в середину программы. Затем запустить программу и увидеть, произошел ли сбой перед добавленной командой printf, после чего продолжить поиск в первой или второй половине кода.

Но опять же, запуск программы может занять много времени, поэтому наиболее эффективная стратегия времени может быть чем-то средним. Напишите программу, которая вычислит минимальное время наихудшего случая, чтобы найти строку со сбоем (независимо от того, где она находится), предполагая, что Вы выбираете оптимальную стратегию для размещения своих операторов printf.

Мы выпускаем новую версию через пять часов, поэтому задача обостряется и должна быть решена как можно скорее.

Входные данные

Состоит из одной строки с тремя целыми числами:

  • n (1n106) - количество строк кода;

  • r (1r109) - количество времени, которое уходит на компиляцию и работу программы до точки сбоя;

  • p (1p109) - время, которое требуется на добавление одной строки printf.

Вы уже запустили программу один раз и поэтому уже знаете, что она где-то сбоит.

Выходные данные

Выведите наихудшее время, за которое можно найти строку, которая сбоит при использовании оптимальной стратегии.

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
1 100 20
Выходные данные #1
0
Входные данные #2
10 10 1
Выходные данные #2
19
Входные данные #3
16 1 10
Выходные данные #3
44
Источник 2015 ACM North Western European Regional Contest (NWERC), Ноябрь 30, Задача D