# Marc's Cakewalk

See the original problem on HackerRank.

## Solutions

This easy problem can be solved by first sorting the calories in decreasing order:

  1 2 3 4 5 6 7 8 9 10  long long n; cin >> n; vector v(n); copy_n(istream_iterator(cin), n, begin(v)); sort(begin(v), end(v), greater<>{}); auto miles = 0ll; for (auto i=0; i

The zip | map | reduce pattern emerges from the code: conceptually, it’s like zipping each calory with the ith power of 2, mapping the pair with product and summing along the way:

 1 2 3 4 5 6  long long n; cin >> n; vector v(n), twos(n, 2); twos.front() = 1; copy_n(istream_iterator(cin), n, begin(v)); partial_sum(begin(twos), end(twos), begin(twos), multiplies<>{}); sort(begin(v), end(v), greater<>{}); cout << inner_product(begin(v), end(v), begin(twos), 0ll, plus<>{}, multiplies<>{}); 

partial_sum used this way generates the first n powers of 2.

Using C++ ranges (actually, some functionals are not yet in C++20 - however, you can test them using the range-v3 library):

 1 2 3 4 5 6  long long n; cin >> n; vector v(n); copy_n(istream_iterator(cin), n, begin(v)); sort(v, std::greater<>{}); auto twos = views::partial_sum(views::concat(views::single(1ll), views::repeat_n(2ll, n-1)), std::multiplies<>{}); std::cout << accumulate(views::zip_with(std::multiplies<>{}, v, twos), 0ll); 

Similar approach in Python:

 1 2  input() print(sum(c * 2 ** j for (j, c) in enumerate(sorted(map(int, input().split()), reverse=True)))) 

Javascript one-liner:

 1  calorie.sort((p,c) => c - p).reduce((p,c,i) => p + c * Math.pow(2, i), 0) 
We've worked on this challenge in these gyms: modena