POJ 2590 - Steps

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

概要

整数 x から y まで移動するのに必要な最小のステップ数を答える．

各ステップにおいて，1つ前のステップで長さ l だけ飛んだとすると，

• 長さ l+1 だけ飛ぶ
• 長さ l だけ飛ぶ
• 長さ l-1 だけ飛ぶ

のいずれかの行動をとれる．ただし l は非負． また，最初と最後のステップでは長さ 1 だけ飛ぶ．

制約

• 0 <= x <= y <= 2^31

解法

答えは x と y の差 d := y - x で決まる．

最初と最後のステップでは 1 しか飛べないため，飛ぶ長さは 1, 2, ..., l-1, l, l, ..., l, l-1, ..., 2, 1 と対称的にするのが最適．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   cin >> N;
 8   while (N-- > 0) {
 9     int x, y;
10     cin >> x >> y;
11 
12     const int d = y-x;
13     int i = 0;
14     for (; ; i++) {
15       if (i % 2 == 0) {
16         const long long k = i/2;
17         if (d <= k*k + k) {
18           break;
19         }
20       } else {
21         const long long k = (i+1)/2;
22         if (d <= k*k) {
23           break;
24         }
25       }
26     }
27     cout << i << endl;
28   }
29   return 0;
30 }