POJ 2619 - Delta-wave

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

概要

図のように数字が並べられているとき，数字 N から M へ行くのに必要な最小のステップ数を答える．

各ステップでは，辺を共有しているマスに進むことができる．

制約

• 1 <= N, M <= 10^9

解法

ある数 x が何段目にあるかどうかは sqrt(x) で求めることができる．

高さは最大でも sqrt(10^9) なので，あとは近づくように1段ずつ進めていけば解ける．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 long long height(long long x)
 6 {
 7   for (long long i = 1; ; i++) {
 8     if (x <= i*i) {
 9       return i;
10     }
11   }
12 }
13 
14 int main()
15 {
16   long long M, N;
17   scanf("%lld %lld", &M, &N);
18   if (M > N) {
19     swap(M, N);
20   }
21   // M <= N
22   long long h1 = height(M);
23   long long x1 = M - (h1-1)*(h1-1);
24   const long long h2 = height(N);
25   const long long x2 = N - (h2-1)*(h2-1);
26   int c = 0;
27   while (h1 < h2) {
28     if (h1 % 2 == M % 2) {
29       // lower
30       M += 2*h1;
31       h1++;
32       x1++;
33       c++;
34     } else {
35       // upper
36       if (x1 < x2) {
37         // go down right
38         M += 2*h1 + 1;
39         x1 += 2;
40       } else {
41         // go down left
42         M += 2*h1 - 1;
43       }
44       ++h1;
45       c += 2;
46     }
47   }
48   if (N < M) {
49     swap(N, M);
50   }
51   printf("%lld\n", c + N - M);
52   return 0;
53 }