Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #define dbg(x) cerr<<#x": "<<x<<"\n"
- using namespace std;
- const int N = 10005;
- int i, j, n, a[N], s, m, b[N];
- set<int> dp[N / 2];
- void solve() {
- for(int i = 1; i <= n; i++)
- cin >> a[i] >> b[i], s += a[i];
- int tot = n * m;
- dp[0].insert(0);
- for(i = 1; i <= n; ++i)
- for(j = min(n / 2 - 1, i); j >= 0; --j)
- for(auto it : dp[j])
- dp[j + 1].insert(it + a[i]);
- // dbg(s);
- int req = s / 2;
- if(dp[n / 2].lower_bound(req) == dp[n / 2].end()) {
- cout << "Nu stiu ce fac aici :P\n";
- }
- int has1 = *dp[n / 2].lower_bound(req);
- // dbg(has1);
- if(2 * has1 == tot / 2) {
- cout << "No solution\n";
- return;
- }
- int has2 = s - has1;
- int half = tot / 2;
- double p;
- // dbg(has1);
- // dbg(has2);
- if(2 * s >= tot)
- cout << "W ";
- else
- cout << "B ",
- has1 = half - has1,
- has2 = half - has2;
- p = min(1. * has1 / half, 1. * has2 / half);;
- cout << p * 100 << '\n';
- }
- void reset() {
- for(int i = 0; i <= N/2; i++)
- dp[i].clear();
- s = 0;
- }
- int main() {
- cout << fixed << setprecision(2);
- // citesc a[i] de la 1 la n
- freopen("d.in", "r", stdin);
- cin >> n >> m;
- while(!cin.eof()) {
- reset();
- solve();
- cin >> n >> m;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement