Untitled
unknown
plain_text
20 days ago
4.2 kB
2
Indexable
Never
It is science class of middle standard of MissMihye. Today they are studying acid and alkalireactions. There are N bottles of acid/alkaline/neutral acid. On each glass bottle its weight is markedin gram unit, the reactivity is indicated in -3 to +3, + means acidic solution,- means alkaline solution and 0 means neutral And absolute value of these show strengthof reactivity. Here 1 g of +2 strength acid can react with1g of -2 alkaline and it will generate 2 calories of energy and resultingsolution would be neutral. So when we mix acid and alkaline it would generateenergy as much as solution is neutralized. Like 10g of +3 acid have acidstrength 10x3 = +30 and it can neutralize alkaline of 15g and -2 (strength -30)to generate energy 30 calories and weight of resultant material is 10+ 15 g =25g. Miss Mihye is asked to select R chemicalssuch that it generate maximum energy. She should select exact R bottles, notless than R bottles. Let’s take an example : Glass Bottle 1 2 3 4 5 Weight 30 10 70 50 50 Reactivity 1 -1 0 -3 -1 Here we need to select 3 bottles. For {1, 2, 5} .. Weight is 90 and energy is30( 30x1 = +30, it can neutralize only 30 strength of alkaline even we havealkaline -10 -50 = -60. ) For {1,3,4} weight is 150, energy is again30. In case we have same energy for somecombination we select with less weight. [Input] First line have number of test cases: T Next line have N (5<= N <= 20):number of glass bottles and R(2<=R<=20) number of bottles Miss Mihye shouldselect. Next we have weight Wi Wi(1<= Wi <= 100),Pi(-3 <= Pi <= 3) reactivity for N bottles. [Output] Output maximum calories which can begenerated along with weight.. [Inputexample 5 // Testcase 5 5 3 30 1 10 -1 70 0 50 -3 50 -1 5 3 30 -3 30 3 40 1 30 -3 10 -2 5 2 30 -1 90 2 70 -3 40 0 60 2 5 3 60 0 50 -1 20 2 80 3 40 2 5 5 80 -2 20 0 80 1 60 3 50 -2 [Outputexample] 30 90 90 70 180 160 50 110 260 290 15 5 3 23 1 41 -1 17 0 95 -3 45 -1 5 3 43 -3 43 3 64 1 13 -3 81 -2 5 5 73 0 99 2 67 1 34 0 76 2 7 5 46 0 35 -1 42 2 28 3 54 2 36 3 20 -2 7 7 18 1 86 3 95 -2 20 -3 36 -2 33 1 64 -3 7 6 77 -3 65 -2 58 2 36 -3 97 -2 100 0 26 -1 10 2 17 2 15 -1 21 -2 99 -3 88 -2 42 3 11 2 16 1 65 -3 55 -1 10 2 1 -1 20 2 44 2 40 1 8 -2 50 -1 38 -1 10 -1 38 0 13 -3 10 3 28 -3 31 -2 5 2 22 -2 17 1 99 1 82 -1 60 3 35 2 96 -1 15 9 25 2 96 2 84 -1 63 -3 42 -1 95 0 34 -3 59 1 30 3 7 3 46 0 50 -3 66 2 52 2 24 0 15 13 56 -2 62 0 95 -3 82 3 81 0 85 0 98 0 21 3 75 0 83 3 10 1 10 -3 54 -3 41 -1 75 -3 15 6 25 -3 71 2 90 0 37 -1 99 -3 14 -3 76 -1 27 -1 10 1 85 3 12 1 54 1 75 0 54 -1 70 -3 20 18 29 -3 57 -1 7 3 98 -2 49 3 10 0 40 2 86 -1 87 -3 56 3 41 -1 81 -3 50 -3 80 -1 6 -1 14 -3 55 3 78 -1 53 1 35 1 20 17 82 3 36 3 4 2 48 3 85 1 71 3 88 0 67 3 47 2 40 3 32 1 34 1 28 -3 54 -3 89 -1 100 3 66 -3 31 2 51 3 54 0 20 6 35 1 22 0 38 0 17 3 64 -2 43 2 6 1 65 3 1 -1 63 -3 32 -2 35 0 58 -3 59 -3 94 2 1 -2 47 0 46 0 58 2 34 -3 23 81 162 188 0 349 75 161 309 352 116 359 126 107 50 94 180 184 525 482 568 735 463 391 669 827 533 834 499 397 #include<iostream> #define rint register int using namespace std; #define N 22 const int INF = 1e9 + 7; int P[N], W[N]; int ans_e, ans_w, n, r; void dfs(int k, int p, int e, int w, int d) { if (k == n) { if (d == r) { int me = min(p, e); if (ans_e < me) { ans_e = me; ans_w = w; } else if (ans_e == me) { ans_w = min(ans_w, w); } } return; } dfs(k + 1, p, e, w, d); if (P[k] > 0) dfs(k + 1, p + W[k] * P[k], e, w + W[k], d + 1); else dfs(k + 1, p, e - W[k] * P[k], w + W[k], d + 1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int T, tc = 1; cin >> T; while (T--) { cin >> n >> r; for (int i = 0; i < n; i++) cin >> W[i] >> P[i]; ans_e = -INF, ans_w = INF; dfs(0, 0, 0, 0, 0); cout << ans_e << ' ' << ans_w << '\n'; } return 0; }