fork download
copy 
  1. // Copyright (c) 2015 Elements of Programming Interviews. All rights reserved.
  2.  
  3. #include <algorithm>
  4. #include <cassert>
  5. #include <iostream>
  6. #include <random>
  7. #include <utility>
  8. #include <vector>
  9.  
  10. using std::cout;
  11. using std::default_random_engine;
  12. using std::endl;
  13. using std::random_device;
  14. using std::uniform_int_distribution;
  15. using std::vector;
  16.  
  17. // @include
  18. const int kMPG = 20;
  19.  
  20. // gallons[i] is the amount of gas in city i, and distances[i] is the distance
  21. // city i to the next city.
  22. size_t FindAmpleCity(const vector<int>& gallons,
  23.                      const vector<int>& distances) {
  24.   int remaining_gallons = 0;
  25.   struct CityAndRemainingGas {
  26.     int city = 0, remaining_gallons = 0;
  27.   };
  28.   CityAndRemainingGas city_remaining_gallons_pair;
  29.   const int num_cities = gallons.size();
  30.   for (int i = 1; i < num_cities; ++i) {
  31.     remaining_gallons += gallons[i - 1] - distances[i - 1] / kMPG;
  32.     if (remaining_gallons < city_remaining_gallons_pair.remaining_gallons) {
  33.       city_remaining_gallons_pair = {i, remaining_gallons};
  34.     }
  35.   }
  36.   return city_remaining_gallons_pair.city;
  37. }
  38. // @exclude
  39.  
  40. void CheckAns(const vector<int>& gallons, const vector<int>& distances,
  41.               size_t c) {
  42.   size_t s = c;
  43.   int gas = 0;
  44.   do {
  45.     gas += gallons[s] - distances[s] / kMPG;
  46.     assert(gas >= 0);
  47.     s = (s + 1) % gallons.size();
  48.   } while (s != c);
  49. }
  50.  
  51. void SmallTest() {
  52.   // Example in the book.
  53.   vector<int> gallons = {20, 15, 15, 15, 35, 25, 30, 15, 65, 45, 10, 45, 25};
  54.   vector<int> distances = {15 * kMPG, 20 * kMPG, 50 * kMPG, 15 * kMPG,
  55.                            15 * kMPG, 30 * kMPG, 20 * kMPG, 55 * kMPG,
  56.                            20 * kMPG, 50 * kMPG, 10 * kMPG, 15 * kMPG,
  57.                            15 * kMPG};
  58.   size_t ans = FindAmpleCity(gallons, distances);
  59.   assert(ans == 8);
  60.   CheckAns(gallons, distances, ans);
  61. }
  62.  
  63. int main(int argc, char* argv[]) {
  64.   SmallTest();
  65.   default_random_engine gen((random_device())());
  66.   for (int times = 0; times < 1000; ++times) {
  67.     int n;
  68.     if (argc == 2) {
  69.       n = atoi(argv[1]);
  70.     } else {
  71.       uniform_int_distribution<int> dis(1, 10000);
  72.       n = dis(gen);
  73.     }
  74.     vector<int> gallons, distances;
  75.     int sum = 0;
  76.     for (int i = 0; i < n; ++i) {
  77.       uniform_int_distribution<int> dis(1, 200);
  78.       int x = dis(gen);
  79.       sum += x;
  80.       gallons.emplace_back(x);
  81.     }
  82.     sum -= n;
  83.     for (int i = 0; i < n; ++i) {
  84.       int x = 0;
  85.       if (sum) {
  86.         uniform_int_distribution<int> dis(1, sum);
  87.         x = dis(gen);
  88.       }
  89.       distances.emplace_back(x + 1);
  90.       sum -= x;
  91.     }
  92.     distances.back() += sum;
  93.     size_t c = FindAmpleCity(gallons, distances);
  94.     cout << "start city = " << c << endl;
  95.     CheckAns(gallons, distances, c);
  96.   }
  97.   return 0;
  98. }
Success #stdin #stdout 0.12s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
start city = 6
start city = 5
start city = 7
start city = 7
start city = 8
start city = 8
start city = 9
start city = 4
start city = 4
start city = 4
start city = 2
start city = 3
start city = 7
start city = 5
start city = 5
start city = 7
start city = 5
start city = 7
start city = 8
start city = 3
start city = 5
start city = 7
start city = 6
start city = 5
start city = 3
start city = 7
start city = 5
start city = 8
start city = 9
start city = 6
start city = 8
start city = 9
start city = 1
start city = 4
start city = 8
start city = 3
start city = 5
start city = 7
start city = 5
start city = 5
start city = 4
start city = 4
start city = 7
start city = 8
start city = 5
start city = 11
start city = 6
start city = 2
start city = 6
start city = 7
start city = 7
start city = 2
start city = 3
start city = 9
start city = 9
start city = 3
start city = 4
start city = 2
start city = 12
start city = 5
start city = 7
start city = 5
start city = 4
start city = 4
start city = 5
start city = 4
start city = 8
start city = 6
start city = 5
start city = 7
start city = 5
start city = 6
start city = 9
start city = 6
start city = 9
start city = 5
start city = 12
start city = 5
start city = 4
start city = 6
start city = 3
start city = 7
start city = 6
start city = 11
start city = 8
start city = 6
start city = 5
start city = 3
start city = 6
start city = 7
start city = 4
start city = 8
start city = 4
start city = 9
start city = 6
start city = 7
start city = 3
start city = 9
start city = 7
start city = 3
start city = 9
start city = 2
start city = 6
start city = 6
start city = 4
start city = 2
start city = 2
start city = 1
start city = 7
start city = 9
start city = 5
start city = 8
start city = 5
start city = 7
start city = 3
start city = 4
start city = 5
start city = 1
start city = 3
start city = 5
start city = 1
start city = 5
start city = 3
start city = 3
start city = 5
start city = 7
start city = 7
start city = 4
start city = 6
start city = 4
start city = 6
start city = 2
start city = 4
start city = 5
start city = 8
start city = 6
start city = 9
start city = 7
start city = 4
start city = 5
start city = 7
start city = 5
start city = 10
start city = 7
start city = 1
start city = 4
start city = 6
start city = 5
start city = 3
start city = 6
start city = 3
start city = 2
start city = 3
start city = 7
start city = 5
start city = 11
start city = 7
start city = 3
start city = 3
start city = 5
start city = 8
start city = 5
start city = 8
start city = 2
start city = 6
start city = 3
start city = 5
start city = 3
start city = 3
start city = 6
start city = 6
start city = 7
start city = 5
start city = 9
start city = 6
start city = 7
start city = 6
start city = 8
start city = 7
start city = 1
start city = 5
start city = 6
start city = 5
start city = 5
start city = 5
start city = 4
start city = 6
start city = 1
start city = 4
start city = 5
start city = 6
start city = 4
start city = 6
start city = 4
start city = 9
start city = 6
start city = 6
start city = 5
start city = 4
start city = 8
start city = 8
start city = 6
start city = 4
start city = 4
start city = 9
start city = 2
start city = 6
start city = 3
start city = 4
start city = 6
start city = 4
start city = 7
start city = 3
start city = 3
start city = 7
start city = 6
start city = 6
start city = 3
start city = 4
start city = 6
start city = 6
start city = 5
start city = 3
start city = 6
start city = 3
start city = 4
start city = 5
start city = 7
start city = 5
start city = 6
start city = 4
start city = 4
start city = 2
start city = 7
start city = 6
start city = 2
start city = 7
start city = 5
start city = 8
start city = 5
start city = 5
start city = 2
start city = 5
start city = 4
start city = 3
start city = 8
start city = 8
start city = 5
start city = 4
start city = 5
start city = 5
start city = 7
start city = 2
start city = 7
start city = 2
start city = 3
start city = 6
start city = 6
start city = 8
start city = 2
start city = 9
start city = 1
start city = 10
start city = 7
start city = 4
start city = 3
start city = 3
start city = 4
start city = 5
start city = 6
start city = 7
start city = 7
start city = 8
start city = 5
start city = 9
start city = 5
start city = 1
start city = 5
start city = 5
start city = 5
start city = 4
start city = 5
start city = 1
start city = 5
start city = 7
start city = 9
start city = 3
start city = 6
start city = 8
start city = 8
start city = 8
start city = 7
start city = 5
start city = 7
start city = 4
start city = 12
start city = 3
start city = 7
start city = 0
start city = 5
start city = 9
start city = 9
start city = 4
start city = 6
start city = 8
start city = 6
start city = 9
start city = 3
start city = 4
start city = 8
start city = 10
start city = 4
start city = 1
start city = 4
start city = 10
start city = 7
start city = 5
start city = 9
start city = 4
start city = 7
start city = 2
start city = 6
start city = 6
start city = 8
start city = 4
start city = 5
start city = 8
start city = 3
start city = 7
start city = 6
start city = 3
start city = 4
start city = 2
start city = 5
start city = 8
start city = 3
start city = 5
start city = 4
start city = 3
start city = 6
start city = 4
start city = 4
start city = 7
start city = 3
start city = 8
start city = 11
start city = 6
start city = 4
start city = 6
start city = 4
start city = 10
start city = 2
start city = 6
start city = 3
start city = 5
start city = 2
start city = 5
start city = 5
start city = 3
start city = 1
start city = 1
start city = 7
start city = 2
start city = 2
start city = 6
start city = 7
start city = 3
start city = 4
start city = 11
start city = 6
start city = 6
start city = 1
start city = 6
start city = 6
start city = 9
start city = 9
start city = 2
start city = 7
start city = 7
start city = 3
start city = 6
start city = 5
start city = 6
start city = 4
start city = 13
start city = 9
start city = 6
start city = 11
start city = 4
start city = 1
start city = 4
start city = 3
start city = 4
start city = 7
start city = 4
start city = 3
start city = 4
start city = 8
start city = 2
start city = 7
start city = 10
start city = 5
start city = 7
start city = 6
start city = 5
start city = 5
start city = 6
start city = 5
start city = 2
start city = 10
start city = 3
start city = 6
start city = 8
start city = 8
start city = 3
start city = 8
start city = 4
start city = 4
start city = 6
start city = 17
start city = 8
start city = 3
start city = 9
start city = 7
start city = 4
start city = 9
start city = 5
start city = 3
start city = 5
start city = 4
start city = 8
start city = 5
start city = 9
start city = 7
start city = 8
start city = 2
start city = 8
start city = 4
start city = 8
start city = 3
start city = 9
start city = 5
start city = 5
start city = 7
start city = 8
start city = 0
start city = 9
start city = 6
start city = 3
start city = 7
start city = 7
start city = 7
start city = 4
start city = 6
start city = 11
start city = 1
start city = 12
start city = 6
start city = 8
start city = 2
start city = 9
start city = 5
start city = 5
start city = 2
start city = 4
start city = 4
start city = 6
start city = 7
start city = 3
start city = 10
start city = 5
start city = 8
start city = 5
start city = 12
start city = 7
start city = 4
start city = 2
start city = 5
start city = 6
start city = 6
start city = 2
start city = 4
start city = 5
start city = 7
start city = 7
start city = 5
start city = 5
start city = 3
start city = 3
start city = 2
start city = 4
start city = 4
start city = 6
start city = 8
start city = 8
start city = 7
start city = 6
start city = 4
start city = 6
start city = 8
start city = 8
start city = 10
start city = 3
start city = 5
start city = 3
start city = 6
start city = 10
start city = 10
start city = 7
start city = 2
start city = 6
start city = 5
start city = 4
start city = 6
start city = 5
start city = 5
start city = 2
start city = 6
start city = 1
start city = 6
start city = 5
start city = 5
start city = 4
start city = 6
start city = 9
start city = 2
start city = 5
start city = 6
start city = 2
start city = 9
start city = 4
start city = 11
start city = 6
start city = 2
start city = 5
start city = 6
start city = 11
start city = 7
start city = 4
start city = 9
start city = 5
start city = 4
start city = 3
start city = 6
start city = 3
start city = 5
start city = 8
start city = 8
start city = 6
start city = 6
start city = 8
start city = 9
start city = 7
start city = 3
start city = 7
start city = 4
start city = 7
start city = 2
start city = 3
start city = 11
start city = 10
start city = 2
start city = 3
start city = 4
start city = 8
start city = 2
start city = 5
start city = 4
start city = 1
start city = 6
start city = 7
start city = 8
start city = 5
start city = 5
start city = 1
start city = 3
start city = 4
start city = 3
start city = 6
start city = 5
start city = 4
start city = 7
start city = 4
start city = 6
start city = 4
start city = 2
start city = 6
start city = 5
start city = 2
start city = 8
start city = 6
start city = 7
start city = 6
start city = 5
start city = 3
start city = 7
start city = 4
start city = 4
start city = 4
start city = 3
start city = 8
start city = 1
start city = 5
start city = 8
start city = 5
start city = 11
start city = 8
start city = 9
start city = 4
start city = 6
start city = 1
start city = 6
start city = 4
start city = 5
start city = 3
start city = 3
start city = 6
start city = 3
start city = 8
start city = 7
start city = 6
start city = 10
start city = 4
start city = 4
start city = 6
start city = 9
start city = 10
start city = 6
start city = 5
start city = 8
start city = 8
start city = 7
start city = 5
start city = 10
start city = 5
start city = 4
start city = 2
start city = 3
start city = 6
start city = 4
start city = 6
start city = 5
start city = 9
start city = 10
start city = 9
start city = 10
start city = 5
start city = 7
start city = 5
start city = 8
start city = 6
start city = 6
start city = 3
start city = 6
start city = 4
start city = 5
start city = 5
start city = 4
start city = 2
start city = 6
start city = 5
start city = 7
start city = 3
start city = 5
start city = 7
start city = 5
start city = 7
start city = 3
start city = 7
start city = 11
start city = 5
start city = 2
start city = 7
start city = 7
start city = 6
start city = 6
start city = 8
start city = 8
start city = 5
start city = 7
start city = 8
start city = 9
start city = 8
start city = 4
start city = 8
start city = 6
start city = 4
start city = 6
start city = 7
start city = 8
start city = 5
start city = 5
start city = 5
start city = 7
start city = 4
start city = 4
start city = 8
start city = 6
start city = 6
start city = 8
start city = 5
start city = 3
start city = 5
start city = 8
start city = 7
start city = 3
start city = 5
start city = 1
start city = 4
start city = 5
start city = 6
start city = 2
start city = 10
start city = 6
start city = 4
start city = 6
start city = 5
start city = 6
start city = 4
start city = 5
start city = 2
start city = 6
start city = 7
start city = 4
start city = 3
start city = 4
start city = 11
start city = 2
start city = 9
start city = 5
start city = 2
start city = 12
start city = 9
start city = 7
start city = 1
start city = 6
start city = 3
start city = 7
start city = 5
start city = 7
start city = 4
start city = 2
start city = 13
start city = 5
start city = 3
start city = 5
start city = 3
start city = 3
start city = 3
start city = 6
start city = 7
start city = 5
start city = 7
start city = 4
start city = 5
start city = 6
start city = 2
start city = 6
start city = 4
start city = 5
start city = 4
start city = 1
start city = 6
start city = 4
start city = 6
start city = 4
start city = 8
start city = 4
start city = 5
start city = 2
start city = 3
start city = 6
start city = 8
start city = 3
start city = 8
start city = 6
start city = 3
start city = 13
start city = 3
start city = 2
start city = 8
start city = 6
start city = 5
start city = 8
start city = 3
start city = 5
start city = 4
start city = 9
start city = 6
start city = 6
start city = 6
start city = 7
start city = 8
start city = 2
start city = 3
start city = 5
start city = 11
start city = 2
start city = 6
start city = 4
start city = 4
start city = 3
start city = 2
start city = 6
start city = 5
start city = 8
start city = 3
start city = 4
start city = 6
start city = 6
start city = 3
start city = 6
start city = 4
start city = 5
start city = 2
start city = 2
start city = 7
start city = 4
start city = 1
start city = 7
start city = 6
start city = 4
start city = 4
start city = 4
start city = 4
start city = 8
start city = 2
start city = 1
start city = 10
start city = 7
start city = 6
start city = 5
start city = 8
start city = 4
start city = 6
start city = 5
start city = 3
start city = 5
start city = 7
start city = 4
start city = 6
start city = 5
start city = 5
start city = 8
start city = 7
start city = 3
start city = 6
start city = 7
start city = 3
start city = 8
start city = 5
start city = 6
start city = 5
start city = 9
start city = 4
start city = 6
start city = 5
start city = 3
start city = 5
start city = 5
start city = 4
start city = 4
start city = 6
start city = 5
start city = 4
start city = 6
start city = 5
start city = 8
start city = 3
start city = 3
start city = 6
start city = 8
start city = 5
start city = 8
start city = 8
start city = 1
start city = 7
start city = 7
start city = 4
start city = 3
start city = 3
start city = 9
start city = 6
start city = 3
start city = 5
start city = 3
start city = 3
start city = 6
start city = 4
start city = 2
start city = 6
start city = 7
start city = 7
start city = 4
start city = 3
start city = 4
start city = 2
start city = 4
start city = 10
start city = 3
start city = 4
start city = 5
start city = 4
start city = 1
start city = 5
start city = 5
start city = 9
start city = 1
start city = 8
start city = 8
start city = 4
start city = 2
start city = 7
start city = 9
start city = 6
start city = 1
start city = 8
start city = 5
start city = 5
start city = 5
start city = 8
start city = 2
start city = 6
start city = 4
start city = 7
start city = 7
start city = 4
start city = 2
start city = 7
start city = 6
start city = 4
start city = 8
start city = 5
start city = 3
start city = 2
start city = 1
start city = 1
start city = 6
start city = 6
start city = 6
start city = 6
start city = 3
start city = 6
start city = 6
start city = 5
start city = 7
start city = 4
start city = 2
start city = 9
start city = 9
start city = 6
start city = 3
start city = 5
start city = 6
start city = 4
start city = 5
start city = 6
start city = 8
start city = 4
start city = 9
start city = 5
start city = 10
start city = 2
start city = 8
start city = 4
start city = 8
start city = 6
start city = 4
start city = 7
start city = 7
start city = 4
start city = 5
start city = 4
start city = 6
start city = 5
start city = 8
start city = 3
start city = 5
start city = 8
start city = 9
start city = 9
start city = 5
start city = 2
start city = 10
start city = 6
start city = 7
start city = 3
start city = 6
start city = 2
start city = 10
start city = 5
start city = 2
start city = 1
start city = 5
start city = 4
start city = 9
start city = 3
start city = 3
start city = 6
start city = 4
https://ideone.com/ICx9jd
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!