Advertisement
Guest User

Untitled

a guest
Jul 23rd, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1.  
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include <bits/stdc++.h>
  5. #define dbg(x) cerr<<#x": "<<x<<"\n"
  6. using namespace std;
  7.  
  8. const int N = 10005;
  9.  
  10. int i, j, n, a[N], s, m, b[N];
  11. set<int> dp[N / 2];
  12.  
  13. void solve() {
  14. for(int i = 1; i <= n; i++)
  15. cin >> a[i] >> b[i], s += a[i];
  16.  
  17. int tot = n * m;
  18.  
  19. dp[0].insert(0);
  20. for(i = 1; i <= n; ++i)
  21. for(j = min(n / 2 - 1, i); j >= 0; --j)
  22. for(auto it : dp[j])
  23. dp[j + 1].insert(it + a[i]);
  24.  
  25. // dbg(s);
  26. int req = s / 2;
  27.  
  28. if(dp[n / 2].lower_bound(req) == dp[n / 2].end()) {
  29. cout << "Nu stiu ce fac aici :P\n";
  30. }
  31. int has1 = *dp[n / 2].lower_bound(req);
  32. // dbg(has1);
  33. if(2 * has1 == tot / 2) {
  34. cout << "No solution\n";
  35. return;
  36. }
  37. int has2 = s - has1;
  38. int half = tot / 2;
  39. double p;
  40. // dbg(has1);
  41. // dbg(has2);
  42. if(2 * s >= tot)
  43. cout << "W ";
  44. else
  45. cout << "B ",
  46. has1 = half - has1,
  47. has2 = half - has2;
  48.  
  49. p = min(1. * has1 / half, 1. * has2 / half);;
  50. cout << p * 100 << '\n';
  51. }
  52.  
  53. void reset() {
  54. for(int i = 0; i <= N/2; i++)
  55. dp[i].clear();
  56. s = 0;
  57. }
  58.  
  59. int main() {
  60. cout << fixed << setprecision(2);
  61. // citesc a[i] de la 1 la n
  62. freopen("d.in", "r", stdin);
  63.  
  64. cin >> n >> m;
  65. while(!cin.eof()) {
  66. reset();
  67. solve();
  68. cin >> n >> m;
  69. }
  70.  
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement