fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3. #define isz(x) (int)(x).size()
  4. typedef long long ll;
  5. int main() {
  6.     for (int n, k; std::cin >> n >> k; ) {
  7.         std::vector<ll> arr(n), curr, tmp; for (auto &it : arr) { std::cin >> it; }
  8.         if (n-- > (1 << std::min(30,k))) {
  9.             std::cout << "No solution" << std::endl; continue; 
  10.         }
  11.         ll p = 0, q = std::accumulate(all(arr), ll(0));
  12.         std::sort(all(arr));
  13.         for (int len = -k; len < 30; ++len) {
  14.             if (len < 0) {
  15.                 tmp.clear();
  16.                 std::merge(all(curr), all(arr), std::back_inserter(tmp));
  17.                 curr = tmp;
  18.             }
  19.             int sz = 0, st = 0;
  20.             if (len >= 0 && ((n >> len) & 1)) {
  21.                 st = 1; p += curr.front();
  22.             }
  23.             for (int i = st; i + 1 < isz(curr); i += 2) {
  24.                 curr[sz++] = curr[i] + curr[i+1];
  25.             }
  26.             curr.resize(sz);
  27.         }
  28.         std::cout << p / std::__gcd(p,q) << '/' << q / std::__gcd(p, q) << std::endl;
  29.     }
  30.     return 0;
  31. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4 1
8 1 9 2

4 2
1 2 3 4

4 3
1 2 3 4
stdout
copy 
No solution
2/1
19/10
https://ideone.com/6KkVfM
language:
C++14 (gcc 8.3)
created:
4 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!