CODE FESTIVAL 2016 Relay: F - 3分割ゲーム / Trichotomy

これぐらいなら十分にgolfしてもいいと思うんだけど、それならanagol行くしなあという気がして手が出ない。

solution

まず$f(N)$について。$N = 1 + \lfloor \frac{1}{N} \rfloor + \lceil \frac{1}{N} \rceil$と分割するのが最良で$f(N) = 1 + f(\lfloor \frac{1}{N} \rfloor)$となる。これを二分探索すればよい。あるいは逆っぽい関数を書けば$O(X)$で済む。

implementation

#!/usr/bin/env python3
def g(x):
    if x == 0:
        return 1
    else:
        return 1 + g(x-1) * 2
x = int(input())
print(g(x+1)-1)