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
|
#include <algorithm>
#include <iostream>
#include <vector>
template <typename T>
void orderedInsert(T & v, typename T::value_type addMe)
{
v.insert(std::lower_bound(std::begin(v), std::end(v), addMe), addMe);
}
typedef std::vector<unsigned> vec;
unsigned waysToTravel(vec::iterator beg, vec::iterator end, unsigned min, unsigned max)
{
vec::iterator lb = std::lower_bound(beg, end, *beg + min); // *lb is the first motel in range for the day.
if (lb == end) // We've reached the end of the journey
return 1;
vec::iterator ub = std::upper_bound(beg, end, *beg + max); // *ub is the first motel that isn't in range for the day.
unsigned count = 0;
while (lb != ub) // for each motel in range, count the ways to travel.
count += waysToTravel(lb++, end, min, max);
return count;
}
int main()
{
vec motels = { 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 };
unsigned minDist;
unsigned maxDist;
unsigned numAdditionalMotels;
std::cin >> minDist >> maxDist >> numAdditionalMotels ;
for (unsigned i = 0; i < numAdditionalMotels; ++i)
{
unsigned motel;
std::cin >> motel;
orderedInsert(motels, motel);
}
std::cout << waysToTravel(std::begin(motels), std::end(motels), minDist, maxDist) << '\n';
}
|