// PA 2024 5C - migawka #include <iostream> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; long long t, n, a; vector<long long> input; long long sum, before, after, cand; vector<long long> twos, threes; #define MIL 1000000 //#define MIL 100 long long splitAlg2(long long pos, long long left, long long right) { long long mid = (left + right) / 2; //cout << " split2 " << left << " " << mid << " " << right << endl; cand = before * (after - mid) * mid + before * twos[mid] + (after - mid) * twos[mid] + threes[mid]; if (cand >= input[pos]) { if (left == right) { return left; } return splitAlg2(pos, left, mid); } else { if (left == right) { return -1; } return splitAlg2(pos, mid + 1, right); } } bool testForNum(long long people) { before = 0; after = people; //cout << " testing: " << people << endl; for (long long i = 0; i < n; ++i) { cand = splitAlg2(i, 0, after); //cout << " cand " << cand << endl; if (cand < 0) { return false; } before += cand; after -= cand; if (after < 0) { return false; } } return true; } long long splitAlg(long long left, long long right) { //cout << "split " << left << " " << right << endl; if (left == right) { return left; } long long mid = (left + right) / 2; if (testForNum(mid)) { return splitAlg(left, mid); } else { return splitAlg(mid + 1, right); } } int main() { ios_base::sync_with_stdio(0); twos.push_back(0); twos.push_back(0); twos.push_back(1); a = 1; for (long long i = 3; a <= 3 * MIL; ++i) { a = a * i / (i - 2); twos.push_back(a); } threes.push_back(0); threes.push_back(0); threes.push_back(0); threes.push_back(1); a = 1; for (long long i = 4; a <= 3 * MIL; ++i) { a = a * i / (i - 3); threes.push_back(a); } a = twos.size() - threes.size(); for (long long i = 0; i < a; ++i) { threes.push_back(3 * MIL); } cin >> t; for (long long i = 0; i < t; ++i) { cin >> n; sum = 0; for (long long j = 0; j < n; ++j) { cin >> a; input.push_back(a); sum += a; } cout << splitAlg(0, 3 * sum) << endl; input.clear(); } /*for (unsigned long long i = 0; i < twos.size(); ++i) { cout << twos[i] << " "; } cout << endl; for (unsigned long long i = 0; i < threes.size(); ++i) { cout << threes[i] << " "; } cout << endl;*/ return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | // PA 2024 5C - migawka #include <iostream> #include <string> #include <vector> #include <queue> #include <algorithm> using namespace std; long long t, n, a; vector<long long> input; long long sum, before, after, cand; vector<long long> twos, threes; #define MIL 1000000 //#define MIL 100 long long splitAlg2(long long pos, long long left, long long right) { long long mid = (left + right) / 2; //cout << " split2 " << left << " " << mid << " " << right << endl; cand = before * (after - mid) * mid + before * twos[mid] + (after - mid) * twos[mid] + threes[mid]; if (cand >= input[pos]) { if (left == right) { return left; } return splitAlg2(pos, left, mid); } else { if (left == right) { return -1; } return splitAlg2(pos, mid + 1, right); } } bool testForNum(long long people) { before = 0; after = people; //cout << " testing: " << people << endl; for (long long i = 0; i < n; ++i) { cand = splitAlg2(i, 0, after); //cout << " cand " << cand << endl; if (cand < 0) { return false; } before += cand; after -= cand; if (after < 0) { return false; } } return true; } long long splitAlg(long long left, long long right) { //cout << "split " << left << " " << right << endl; if (left == right) { return left; } long long mid = (left + right) / 2; if (testForNum(mid)) { return splitAlg(left, mid); } else { return splitAlg(mid + 1, right); } } int main() { ios_base::sync_with_stdio(0); twos.push_back(0); twos.push_back(0); twos.push_back(1); a = 1; for (long long i = 3; a <= 3 * MIL; ++i) { a = a * i / (i - 2); twos.push_back(a); } threes.push_back(0); threes.push_back(0); threes.push_back(0); threes.push_back(1); a = 1; for (long long i = 4; a <= 3 * MIL; ++i) { a = a * i / (i - 3); threes.push_back(a); } a = twos.size() - threes.size(); for (long long i = 0; i < a; ++i) { threes.push_back(3 * MIL); } cin >> t; for (long long i = 0; i < t; ++i) { cin >> n; sum = 0; for (long long j = 0; j < n; ++j) { cin >> a; input.push_back(a); sum += a; } cout << splitAlg(0, 3 * sum) << endl; input.clear(); } /*for (unsigned long long i = 0; i < twos.size(); ++i) { cout << twos[i] << " "; } cout << endl; for (unsigned long long i = 0; i < threes.size(); ++i) { cout << threes[i] << " "; } cout << endl;*/ return 0; } |