精度周りのツメが甘くて本番落とした問題。
http://codeforces.com/contest/325/problem/B
問題
Aチームで大会を開催するとき、試合回数は以下の手順で決まる。
- Aが偶数の場合、2チームずつペアにして敗者が脱落する。すなわちA/2試合してA/2チームが脱落する。これをAが偶数の間繰り返す。
- Aが奇数になったら、総当たり戦、すなわちA*(A-1)/2試合して勝者を決める。
ここで、総試合数Nが与えられたとき、試合数がNになるチーム数Aを列挙せよ。
解法
最初i回チーム数を半減して奇数になったとする。
この時、チーム数は奇数Xを用いてX*2^iチームである。
また、試合数はX*(X-1)/2 + X*(2^i-1)=Nなので、整理するとX^2 + (2^(i+1) - 3) + 2N=0となる。
各iについて上記方程式を解き、Xが奇数な整数となるものを選べばよい。
誤差が怖かったので、念のため得られた整数値で再度試合数をチェックしている。
ll N; int okok(ll M) { ll res=0; while(M%2==0) { res+=M/2; M/=2; } res += M*(M-1)/2; return res==N; } void solve() { int f,r,i,j,k,l, x,y; vector<ll> res; cin>>N; FOR(i,61) { ll B=(1LL<<(1+i)) - 3; ll C=2*N; if(B>C) break; double D = sqrt(B*(double)B+8*(double)N+1e-9); if(D-(ll)D <= 1e-9) { ll B2 = (ll)D-B; if(B2%2==0 && B2%4!=0 && okok((B2/2)<<i)) res.push_back((B2/2)<<i); } } sort(res.begin(),res.end()); res.erase(unique(res.begin(),res.end()),res.end()); if(res.empty()) _P("-1\n"); else FOR(i,res.size()) cout << res[i] << endl; }
まとめ
誤差回りで失点するのはもったいないなぁ…。