POJ 1781 - In Danger

http://poj.org/problem?id=1781

概要

N 人が 1 .. N の順に円形に並んでいる． 1の人からスタートして，2番目にいる人が次々に抜けていくときに最後に残っている人を答える．

N は "xyez" というフォーマットで与えられ，N = xy * 10^z を表している．

制約

• 0 <= x,y <= 9
• 0 <= z <= 6
• N > 0

解法

N = 1 から 10 くらいまでシミュレーションで解いてみると，答えは 2 * (N - (N を越えない最大の2のべき乗)) + 1 と予想できる．

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   string line;
 8   while (cin >> line && line != "00e0") {
 9     long long n = 10*(line[0]-'0') + (line[1]-'0');
10     for (int i = 0; i < line[3]-'0'; i++) {
11       n *= 10;
12     }
13     long long b = 1LL;
14     for (; b <= n; b *= 2LL);
15     b /= 2LL;
16     n -= b;
17     cout << 2*n+1 << endl;
18   }
19   return 0;
20 }