Оригинал задачи: http://codeforces.com/problemset/problem/569/A
Мальчик Лёша любит слушать музыку со своего смартфона. Но памяти у смартфона не очень много, поэтому Лёша слушает любимые композиции в известной социальной сети НаСвязи.
К сожалению, интернет в Екатеринозаводске не очень быстрый, и песня загружается очень медленно. Но Лёша весьма нетерпелив. Песня длится ровно T секунд. Лёша прогружает первые S секунд композиции и включает песню. Когда воспроизведение доходит до момента, который ещё не прогрузился, Лёша моментально включает песню заново (при этом загруженная часть песни остаётся в памяти телефона, и процесс скачивания продолжается с того же места), и так происходит до тех пор, когда песня скачается полностью и Лёша дослушает до конца. За q секунд реального времени интернет позволяет скачать q - 1 секунду трека.
Подскажите Лёше, сколько раз он запустит песню, включая самый первый запуск.
В единственной строчке записаны три целых числа T, S, q (2 ≤ q ≤ 104, 1 ≤ S < T ≤ 105).
Выведите одно целое число — количество запусков композиции.
Разбор (оригинал):
Пусть перед очередным запуском прогружено S секунд песни, найдем, сколько будет прогружено перед следующим запуском. . Отсюда x = qS.
Тогда решение: будем умножать S на q пока S < T. Количество таких умножений — это ответ.
Сложность —
Моё решение:
1 2 3 4 5 6 7 8 9 10 11 12 |
<span class="kwd">var</span><span class="pln"> data </span><span class="pun">=</span><span class="pln"> readline</span><span class="pun">().</span><span class="pln">split</span><span class="pun">(</span><span class="str">' '</span><span class="pun">);</span> <span class="kwd">var</span><span class="pln"> T </span><span class="pun">=</span><span class="pln"> parseInt</span><span class="pun">(</span><span class="pln">data</span><span class="pun">[</span><span class="lit">0</span><span class="pun">]);</span><span class="com">//длина песни</span> <span class="kwd">var</span><span class="pln"> S </span><span class="pun">=</span><span class="pln"> parseInt</span><span class="pun">(</span><span class="pln">data</span><span class="pun">[</span><span class="lit">1</span><span class="pun">]);</span><span class="com">//прогружено песни перед запуском воспроизведения (от длины песни)</span> <span class="kwd">var</span><span class="pln"> q </span><span class="pun">=</span><span class="pln"> parseInt</span><span class="pun">(</span><span class="pln">data</span><span class="pun">[</span><span class="lit">2</span><span class="pun">]);</span><span class="com">//секунд реального времени</span> <span class="kwd">var</span><span class="pln"> result</span><span class="pun">=</span><span class="lit">0</span><span class="pun">;</span> <span class="kwd">while</span> <span class="pun">(</span><span class="pln"> S </span><span class="pun"><</span><span class="pln"> T</span><span class="pun">)</span> <span class="pun">{</span><span class="pln"> S </span><span class="pun">=</span><span class="pln"> S </span><span class="pun">+</span><span class="pln"> S</span><span class="pun">*(</span><span class="pln">q</span><span class="pun">-</span><span class="lit">1</span><span class="pun">);</span><span class="pln"> result</span><span class="pun">++;</span> <span class="pun">}</span><span class="pln"> write</span><span class="pun">(</span><span class="pln">result</span><span class="pun">);</span> |