fork(2) download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. template <typename T>
  6. void orderedInsert(T & v, typename T::value_type addMe)
  7. {
  8.     v.insert(std::lower_bound(std::begin(v), std::end(v), addMe), addMe);
  9. }
  10.  
  11. typedef std::vector<unsigned> vec;
  12.  
  13.  
  14. unsigned waysToTravel(vec::iterator beg, vec::iterator end, unsigned min, unsigned max)
  15. {
  16.     vec::iterator lb = std::lower_bound(beg, end, *beg + min);  // *lb is the first motel in range for the day.
  17.  
  18.     if (lb == end)                                              // We've reached the end of the journey
  19.         return 1;
  20.  
  21.     vec::iterator ub = std::upper_bound(beg, end, *beg + max);  // *ub is the first motel that isn't in range for the day.
  22.  
  23.     unsigned count = 0;
  24.     while (lb != ub)                                            // for each motel in range, count the ways to travel.
  25.         count += waysToTravel(lb++, end, min, max);
  26.  
  27.     return count;
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33.     vec motels = { 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 };
  34.  
  35.     unsigned minDist;
  36.     unsigned maxDist;
  37.     unsigned numAdditionalMotels;
  38.     std::cin >> minDist >> maxDist >> numAdditionalMotels ;
  39.  
  40.     for (unsigned i = 0; i < numAdditionalMotels; ++i)
  41.     {
  42.         unsigned motel;
  43.         std::cin >> motel;
  44.         orderedInsert(motels, motel);
  45.     }
  46.  
  47.     std::cout << waysToTravel(std::begin(motels), std::end(motels), minDist, maxDist) << '\n';
  48. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
970
1030
1
4960
stdout
copy 
2
https://ideone.com/NgkhMS
language:
C++14 (gcc 8.3)
created:
10 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!