Google Code Jam Japan 2011 予選 C
方針
具体例で考えよう。例えば、N=10とする。仮に、a=10, b=0という組み合わせを考える。この時2進数表記でa=1010, b=0である。ここで
- aの2の位に1が立っている
- a,bの1の位が空いている
事に着目すると、aの2の位の1を0に変えて、その代わりにa,bの1の位を1に変更すると、a+bを一定に保ったまま、f(a)+f(b)の値を増やせることが分かる。で、この考えを小さい位から順番に適用すれば良い。
実装
#!/usr/bin/env python import sys ifs = open(sys.argv[1]) num = int(ifs.readline().strip()) class Solve: def solve(self, n): self.ans = 0 self.rec(n) return self.ans def rec(self, n): if n <= 2: if n == 2: self.ans += 2 elif n == 1: self.ans += 1 return else: if n % 2 == 0: self.ans += 2 n -= 2 else: self.ans += 1 n -= 1 self.rec(n / 2) n = 1 obj = Solve() for l in ifs: print 'Case #%(n)d: %(ans)d' % {'n':n, 'ans':obj.solve(int(l))} n += 1
