fork download
  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
stdin
4 1
8 1 9 2

4 2
1 2 3 4

4 3
1 2 3 4
stdout
No solution
2/1
19/10