Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct frac {
- long long int num, den;
- bool operator < (frac b) {
- return (1ll * num * b.den > 1ll * den * b.num);
- }
- };
- void reduce(frac &x) {
- long long int a = x.num, b = x.den;
- while (a != 0 and b != 0)
- if (a > b) a %= b; else b %= a;
- x.num /= (a + b); x.den /= (a + b);
- }
- int main()
- {
- long long int n, w;
- cin >> n >> w;
- vector <frac> a(n);
- for (long long int i = 0; i < n; i++)
- cin >> a[i].num >> a[i].den;
- sort(a.begin(), a.end());
- long long int sum = a[0].den;
- long long int ind = 0;
- while (sum < w and ind < n) {
- ind++;
- sum += a[ind].den;
- }
- if (ind < n)
- sum -= a[ind].den;
- frac add;
- if (ind < n)
- add = {a[ind].num * (w - sum), a[ind].den};
- else
- add = {0,1};
- long long int int_part = 0;
- for (long long int i = 0; i < ind; i++)
- int_part += a[i].num;
- int_part += add.num / add.den;
- add.num = add.num % add.den;
- reduce(add);
- if (int_part == 0 && add.num == 0)
- cout << int_part;
- else if (int_part == 0)
- cout << add.num << "/" << add.den;
- else if (add.num == 0)
- cout << int_part;
- else
- cout << int_part << "+" << add.num << "/" << add.den;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement