fork(1) download 
  1. #include <iostream>
  2. #include <limits>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <memory>
  8.  
  9. using namespace std;
  10.  
  11. const int max_hour = std::numeric_limits<int>::max() / 2;
  12.  
  13. int solve(const string& s,
  14.     char height = 0,
  15.     double a = 0,
  16.     double b = 0,
  17.     double a_base = 1000.0,
  18.     double b_base = 1.0,
  19.     shared_ptr< map<double, int> > searched = make_shared< map<double, int> >());
  20.  
  21. int solve_sub(const string& s, char height,
  22.     double a, double b,
  23.     double a_base, double b_base,
  24.     shared_ptr< map<double, int> > searched) {
  25.  
  26.     if (height == ':')
  27.         return 0;
  28.  
  29.     int hour = max_hour;
  30.     int l = s.length() - 1;
  31.  
  32.     if (a + b > l)
  33.         return max_hour;
  34.  
  35.     int fwd_a = floor(a + 1.0);
  36.     int back_a = ceil(a - 1.0);
  37.  
  38.  
  39.     vector<int> a_pos = { fwd_a, back_a };
  40.  
  41.     // move A to left and right peak or bottom
  42.     for (int a : a_pos) {
  43.         if (a < 0 || a > l)
  44.             continue;
  45.  
  46.         char h = s[a];
  47.         int took_hour = abs(height - h);
  48.  
  49.         int fwd_b = floor(b + 1.0);
  50.         if (fwd_b < l) {
  51.             // can B move to left peak/bottom?
  52.             if (s[l - fwd_b] == h) {
  53.                 // move B to left peak/bottom
  54.                 if (h == ':')
  55.                     return took_hour;
  56.                 hour = min(hour, took_hour + solve(s, h, a, fwd_b, a_base, b_base, searched));
  57.             }
  58.             // can B move to left slope?
  59.             char high = max(s[l - fwd_b], s[l - (fwd_b - 1)]);
  60.             char low = min(s[l - fwd_b], s[l - (fwd_b - 1)]);
  61.             if (low < h && h < high) {
  62.                 // move A to right, B to left slope
  63.                 hour = min(hour, took_hour + solve(s, h, a, fwd_b - 0.5, a_base, b_base, searched));
  64.             }
  65.         }
  66.  
  67.         // can B move to right peak/bottom?
  68.         int back_b = ceil(b - 1.0);
  69.         if (back_b >= 0) {
  70.             // can B move to right peak/bottom?
  71.             if (s[l - back_b] == h) {
  72.                 // move B to left peak/bottom
  73.                 if (h == ':')
  74.                     return took_hour;
  75.                 hour = min(hour, took_hour + solve(s, h, a, back_b, a_base, b_base, searched));
  76.             }
  77.             // can B move to right slope?
  78.             char high = max(s[l - back_b], s[l - (back_b + 1)]);
  79.             char low = min(s[l - back_b], s[l - (back_b + 1)]);
  80.             if (low < h && h < high) {
  81.                 // move A to right, B to left slope
  82.                 hour = min(hour, took_hour + solve(s, h, a, back_b + 0.5, a_base, b_base, searched));
  83.             }
  84.         }
  85.     }
  86.  
  87.     return hour;
  88. }
  89.  
  90. int solve(const string& s, char height,
  91.     double a, double b,
  92.     double a_base, double b_base,
  93.     shared_ptr< map<double, int> > searched) {
  94.  
  95.     double key = a*a_base + b*b_base;
  96.     auto p = searched->insert(make_pair(key, max_hour));
  97.     if (!p.second) {
  98.         // have result or loop
  99.         return p.first->second;
  100.     }
  101.  
  102.     if (!height)
  103.         height = s[0];
  104.  
  105.     string rev(s.rbegin(), s.rend());
  106.     int hour = solve_sub(s, height, a, b, a_base, b_base, searched);
  107.     int hour_rev = solve_sub(rev, height, b, a, b_base, a_base, searched);
  108.     int result = min(hour, hour_rev);
  109.     (*searched)[key] = result;
  110.     return result;
  111. }
  112.  
  113. int main() {
  114. 	string s;
  115. 	while (cin >> s) {
  116. 		cout << "\"" << s << "\" => " << solve(s) << endl;
  117. 	}
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin 
073:0
07362:450
06464:36470
0827171:28480
0737491:28180
05374734372747484:184618186912120
stdout 
"073:0" => 18
"07362:450" => 36
"06464:36470" => 42
"0827171:28480" => 66
"0737491:28180" => 146
"05374734372747484:184618186912120" => 400
https://ideone.com/ECmxkW
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!