この問題を解く上で重要な命題を紹介します.

  • 正整数xx22倍して繰り上がりが発生したとき,繰り上がる桁は11桁だけでありその最高位は11である

まずこれを桁数に関する数学的帰納法で示します.

11桁の時,繰り上がりが起こるのは55から99のみであるので, 実際に計算すると5×2=10,6×2=12,7×2=14,8×2=16,9×2=185 \times 2 = 10, 6 \times 2 = 12, 7 \times 2 = 14, 8 \times 2 = 16, 9 \times 2 = 18より成立.

nn桁の時に成立すると仮定する. xx(n+1){(n+1)}桁の正整数とする. また,ddxxの最高位の数字とする. ddを用いると,x=d×10n+(xd×10n)x=d \times 10^{n} + (x - d \times 10^{n})と表すことができる.
よって2×x=2d×10n+2×(xd×10n)2\times x = 2d \times 10^{n} + 2\times (x - d \times 10^{n})である.
xxddの定義の仕方によりxd×10nx-d \times 10^{n}nn桁の整数であるので, 2×(xd×10n)<2×10n2\times (x - d \times 10^{n}) < 2 \times 10^{n}が成立. また,11桁の時の結果より,2d182d \leq 18であるので, 2d×10n18×10n2d \times 10^{n} \leq 18\times 10^{n}が成立.
これらの不等式を辺々足すと 2d×10n+2×(xd×10n)=2x<20×10n=2×10n+12d\times 10^n + 2\times (x - d \times 10^n) = 2x < 20 \times 10^{n}=2 \times 10^{n+1}を得る. よって成立.

この命題を用いると,「a0a_0からaXa_Xのうち最高位が11であるものの個数」は 「aXa_Xの桁数」と一致することが言えます.

よって,aXa_Xの桁数を求めてそれを出力すればよいです. 桁数は[log102X]+1=[X×log102]+1[ \log_{10}{2^X} ]+1 = [X \times \log_{10}{2}]+1によって求めることができます([a][a]aa以下の最大の整数を表す).