SRM318 D1E-D2M ReturnToHome

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$(X, Y)$にいて何秒で$(0, 0)$に行けるか．移動方法は$2$通りある．

  • 歩く:$1[s]$当たり$1$マス分進む
  • ジャンプ:$T[s]$当たり$D$マス進む

進む方向は限定されていないので，基本的に$\frac{D}{T} > 1$の場合はジャンプした方が多く進める．基本的にはジャンプで進んでいき，そこから歩いて進んでいった場合と比較する．$1$回以上ジャンプした場合に残りの距離が$D$以下になった場合は，前回のジャンプを$(0, 0)$に向かって真っ直ぐ進むのではなく，適当な点を中継することで残り$1$回のジャンプで行くことができる．初期地点から$D$以下の場合は，必ずどこかの点を中継することで$2$回のジャンプで$(0, 0)$に行くことが出来る．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define EPS 1e-8

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class ReturnToHome {
  public:
  double goHome(int X, int Y, int D, int T) {
      double sum = sqrt(X * X + Y * Y);

      double  ans = INF;
      ans = min(ans, sum);

      if(sum < D) {
          ans = min(ans, 2.0 * T);
      }

      double t = 0;
      while(sum > EPS) {
          sum -= D;
          t += T;

          if(t == T) {
              ans = min(ans, abs(sum) + t);
          } else if(sum <= EPS) {
              ans = min(ans, t);
          } else {
              ans = min(ans, sum + t);
          }
      }

      return ans;
  }
};
Oct 27th, 2016
srm, topcoder