Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct frac {
  8.     long long int num, den;
  9.     bool operator < (frac b) {
  10.         return (1ll * num * b.den > 1ll * den * b.num);
  11.     }
  12. };
  13.  
  14. void reduce(frac &x) {
  15.     long long int a = x.num, b = x.den;
  16.     while (a != 0 and b != 0)
  17.         if (a > b) a %= b; else b %= a;
  18.     x.num /= (a + b); x.den /= (a + b);
  19. }
  20.  
  21. int main()
  22. {
  23.     long long int n, w;
  24.     cin >> n >> w;
  25.     vector <frac> a(n);
  26.     for (long long int i = 0; i < n; i++)
  27.         cin >> a[i].num >> a[i].den;
  28.  
  29.     sort(a.begin(), a.end());
  30.     long long int sum = a[0].den;
  31.  
  32.     long long int ind = 0;
  33.     while (sum < w and ind < n) {
  34.         ind++;
  35.         sum += a[ind].den;
  36.     }
  37.  
  38.     if (ind < n)
  39.         sum -= a[ind].den;
  40.  
  41.     frac add;
  42.     if (ind < n)
  43.         add = {a[ind].num * (w - sum), a[ind].den};
  44.     else
  45.         add = {0,1};
  46.  
  47.     long long int int_part = 0;
  48.     for (long long int i = 0; i < ind; i++)
  49.         int_part += a[i].num;
  50.     int_part += add.num / add.den;
  51.     add.num = add.num % add.den;
  52.  
  53.     reduce(add);
  54.  
  55.     if (int_part == 0 && add.num == 0)
  56.         cout << int_part;
  57.     else if (int_part == 0)
  58.         cout << add.num << "/" << add.den;
  59.     else if (add.num == 0)
  60.         cout << int_part;
  61.     else
  62.         cout << int_part << "+" << add.num << "/" << add.den;
  63.  
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement