Codeforces Round 382 (Div. 2) |
---|
Закончено |
Бразильский город Рио-де-Жанейро принимает крупный теннисный турнир, и Остап Бендер не намерен пропускать это событие. В турнире примут участие n теннисистов, причём с первого же матча будет идти игра на выбывание — проигравший сразу покидает турнир.
Организаторы ещё не составили сетку чемпионата, но известно, что два игрока могут играть друг с другом, если и только если количество игр, уже проведённых одним из них, отличается от количества игр, проведённых другим, не более чем на одну игру (в любую сторону). Разумеется, оба игрока должны были выиграть все свои встречи, чтобы всё ещё участвовать в турнире.
Пока турнир не начался и зрители ищут, чем занять себя в ожидании, Остап решил вычислить, в каком максимальном количестве партий может принять участие победитель турнира. Скорее всего, без вашей помощи ему не справиться.
В единственной строке входных данных записано целое число n (2 ≤ n ≤ 1018) — количество участников турнира.
Выведите одно целое число — максимальное количество партий, в которых может принять участие победитель турнира.
2
1
3
2
4
2
10
4
Во всех примерах будем считать, что турнир выигрывает участник с номером 1.
В первом примере будет всего одна игра, поэтому ответ очевидно 1.
Во втором примере первый игрок может последовательно обыграть игрока 2, а затем игрока 3.
В третьем примере первый игрок не может последовательно обыграть всех остальных, так как если он сыграет с игроками 2 и 3, то у него будет уже две партии, а игрока номер 4 — ноль партий. Тогда они не смогут сыграть и турнир не завершится. Таким образом, ответ 2 и он достигается на сетке турнира, в которой сначала играют пары (1, 2) и (3, 4), а затем победители этих пар играют друг с другом.
Название |
---|