codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

664.md (22788B)


      1 Source: https://codeforces.com/blog/entry/44408
      2 
      3 ## [664A - Complicated GCD](/contest/664/problem/A "Codeforces Round 347 (Div. 2)")
      4 
      5 Author of the idea — [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP")
      6 
      7 We examine two cases:
      8 
      9 1. *a* = *b* — the segment consists of a single number, hence the answer is *a*.
     10 2. *a* < *b* — we have *gcd*(*a*, *a* + 1, *a* + 2, ..., *b*) = *gcd*(*gcd*(*a*, *a* + 1), *a* + 2, ..., *b*) = *gcd*(1, *a* + 2, ..., *b*) = 1.
     11 
     12 **Code**
     13 
     14 ```
     15 #include <bits/stdc++.h>
     16 
     17 using namespace std;
     18 
     19 int main() {
     20     string a, b;
     21     cin >> a >> b;
     22 
     23     if (a == b) cout << a;
     24     else cout << 1;
     25 
     26     return 0;
     27 }
     28 ```
     29 
     30 ## [663A - Rebus](/contest/663/problem/A "Codeforces Round 347 (Div. 1)")
     31 
     32 Author of the idea — [gen](/profile/gen "Master gen")
     33 
     34 First we check whether any solution exists at all. For that purpose, we calculate the number of positive (the first one and any other with the  +  sign) and negative elements (with the  -  sign) in the sum. Let them be *pos* and *neg*, respectively. Then the minimum value of the sum that can be possibly obtained is equal to *min* = (1 · *pos* - *n* · *neg*), as each positive number can be 1, but all negative can be  - *n*. Similarly, the maximum possible value is equal to *max* = (*n* · *pos* - 1 · *neg*). The solution therefore exists if and only if *min* ≤ *n* ≤ *max*.
     35 
     36 Now suppose a solution exists. Let's insert the numbers into the sum one by one from left to right. Suppose that we have determined the numbers for some prefix of the expression with the sum of *S*. Let the sign of the current unknown be *sgn* ( + 1 or  - 1) and there are some unknown numbers left to the right, excluding the examined unknown, among them *pos*_*left* positive and *neg*_*left* negative elements. Suppose that the current unknown number takes value *x*. How do we find out whether this leads to a solution? The answer is: in the same way we checked it in the beginning of the solution. Examine the smallest and the largest values of the total sum that we can get. These are equal to *min*_*left* = (*S* + *sgn* · *x* + *pos*_*left* - *n* · *neg*_*left*) and *max*_*left* = (*S* + *sgn* · *x* + *n* · *pos*_*left* - *neg*_*left*), respectively. Then we may set the current number to *x*, if *min*_*left* ≤ *n* ≤ *max*_*left* holds. To find the value of *x*, we can solve a system of inequalities, but it is easier simply to check all possible values from 1 to *n*.
     37 
     38 **BONUS** Let *k* be the number of unknowns in the rebus. Prove that the complexity of the described solution (implementation shown below) is *O*(*k*2 + *n*), not *O*(*k* · *n*).
     39 
     40 **Code**
     41 
     42 ```
     43 #include<bits/stdc++.h>
     44 
     45 using namespace std;
     46 
     47 char s[100];
     48 
     49 int main() {
     50     int k = 0, n, pos = 1, neg = 0;
     51     while (true) {
     52         char c;
     53         scanf(" %c", &c);
     54         scanf(" %c", &c);
     55 
     56         if (c == '=') break;
     57         if (c == '+') pos++;
     58         if (c == '-') neg++;
     59 
     60         s[k++] = c;
     61     }
     62 
     63     scanf("%d", &n);
     64 
     65     if (pos - n * neg > n || n * pos - neg < n) {
     66         printf("Impossible\\n");
     67 
     68         return 0;
     69     }
     70 
     71     printf("Possible\\n");
     72 
     73     int S = 0;
     74     for (int i = 0; i < k; i++) {
     75         int sgn = 1;
     76         if (i > 0 && s[i - 1] == '-') sgn = -1;
     77 
     78         if (sgn == 1) pos--;
     79         if (sgn == -1) neg--;
     80 
     81         for (int x = 1; x <= n; x++)
     82             if (S + x * sgn + pos - n * neg <= n && S + x * sgn + n * pos - neg >= n) {
     83                 printf("%d %c ", x, s[i]);
     84 
     85                 S += x * sgn;
     86 
     87                 break;
     88             }
     89 	}
     90 
     91     printf("%d = %d\\n", abs(n - m), n);
     92 
     93     return 0;
     94 }
     95 ```
     96 
     97 ## [662D - International Olympiad](/contest/662/problem/D "CROC 2016 - Final Round [Private, For Onsite Finalists Only]")
     98 
     99 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8")
    100 
    101 Consider the abbreviations that are given to the first Olympiads. The first 10 Olympiads (from year 1989 to year 1998) receive one-digit abbreviations (*IAO*'9, *IAO*'0, ..., *IAO*'8). The next 100 Olympiads (1999 - 2098) obtain two-digit abbreviations, because all one-digit abbreviations are already taken, but the last two digits of 100 consecutive integers are pairwise different. Similarly, the next 1000 Olympiads get three-digit abbreviations and so on.
    102 
    103 Now examine the inversed problem (extract the year from an abbreviation). Let the abbreviation have *k* digits, then we know that all Olympiads with abbreviations of lengths (*k* - 1), (*k* - 2), ..., 1 have passed before this one. The number of such Olympiads is 10*k* - 1 + 10*k* - 2 + ... + 101 = *F* and the current Olympiad was one of the 10*k* of the following. Therefore this Olympiad was held in years between (1989 + *F*) and (1989 + *F* + 10*k* - 1). As this segment consists of exactly 10*k* consecutive natural numbers, it contains a single number with a *k*-digit suffix that matches the current abbreviation. It is also the corresponding year.
    104 
    105 **Code**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 
    110 using namespace std;
    111 
    112 char s[42];
    113 
    114 int main() {
    115     int n;
    116     scanf("%d", &n);
    117     while (n--) {
    118         scanf(" %s", s);
    119         
    120         int k = strlen(s + 4), year = atoi(s + 4), F = 0, tenPow = 10;
    121         for (int i = 1; i < k; i++) {
    122             F += tenPow;
    123             tenPow *= 10;
    124         }
    125         
    126         while (year < 1989 + F) year += tenPow;
    127         
    128         printf("%d\\n", year);
    129     }
    130 
    131     return 0;
    132 }
    133 ```
    134 
    135 ## [662B - Graph Coloring](/contest/662/problem/B "CROC 2016 - Final Round [Private, For Onsite Finalists Only]")
    136 
    137 Author of the problem — [gen](/profile/gen "Master gen")
    138 
    139 Examine the two choices for the final color separately, and pick the best option afterwards. Now suppose we want to color the edges red.
    140 
    141 Each vertex should be recolored at most once, since choosing a vertex two times changes nothing (even if the moves are not consecutive). Thus we need to split the vertices into two sets *S* and *T*, the vertices that are recolored and the vertices that are not affected, respectively. Let *u* and *v* be two vertices connected by a red edge. Then for the color to remain red, both *u* and *v* should belong to the same set (either *S* or *T*). On the other hand, if *u* and *v* are connected by a blue edge, then exactly one of the vertices should be recolored. In that case *u* and *v* should belong to different sets (one to *S* and the other to *T*).
    142 
    143 This problem reduces to 0-1 graph coloring, which can be solved by either *DFS* or *BFS*. As the graph may be disconnected, we need to process the components separately. If any component does not have a 0-1 coloring, there is no solution. Otherwise we need to add the smallest of the two partite sets of the 0-1 coloring of this component to *S*, as we require *S* to be of minimum size.
    144 
    145 **Code**
    146 
    147 ```
    148 #include<bits/stdc++.h>
    149 
    150 using namespace std;
    151 
    152 const int MX = 100000;
    153 
    154 int n, vis[MX];
    155 vector<pair<int, char>> G[MX];
    156 vector<int> part[3];
    157 
    158 bool dfs(int v, int p, char c) {
    159     if (vis[v] != 0) {
    160         return vis[v] == p;
    161     }
    162 
    163     vis[v] = p;
    164     part[p].push_back(v);
    165 
    166     for (auto x : G[v]) {
    167         if (dfs(x.first, x.second == c ? p : p ^ 3, c) == false)
    168             return false;
    169     }
    170 
    171     return true;
    172 }
    173 
    174 vector<int> solve(char c) {
    175     memset(vis, 0, sizeof vis);
    176 
    177     vector<int> ans;
    178     for (int i = 0; i < n; i++)
    179         if (vis[i] == 0) {
    180             part[1].clear();
    181             part[2].clear();
    182 
    183             if (dfs(i, 1, c) == false) {
    184                 for (int j = 0; j < n + 1; j++) ans.push_back(-1);
    185 
    186                 return ans;
    187             }
    188 
    189             int f = 1;
    190             if (part[2].size() < part[1].size()) f = 2;
    191 
    192             ans.insert(ans.end(), part[f].begin(), part[f].end());
    193         }
    194 
    195     return ans;
    196 }
    197 
    198 int main() {
    199     int m;
    200     scanf("%d %d", &n, &m);
    201     for (int i = 0; i < m; i++) {
    202         int u, v;
    203         char c;
    204         scanf("%d %d %c", &u, &v, &c);
    205         u--;
    206         v--;
    207 
    208         G[u].emplace_back(v, c);
    209         G[v].emplace_back(u, c);
    210     }
    211 
    212     auto f = solve('R');
    213     auto g = solve('B');
    214 
    215     if (g.size() < f.size()) f = g;
    216 
    217     if (f.size() > n) {
    218         printf("-1\\n");
    219 
    220         return 0;
    221     }
    222 
    223     printf("%d\\n", (int)f.size());
    224     for (int x : f) printf("%d ", x + 1);
    225     printf("\\n");
    226 
    227     return 0;
    228 }
    229 ```
    230 
    231 ## [662A - Gambling Nim](/contest/662/problem/A "CROC 2016 - Final Round [Private, For Onsite Finalists Only]")
    232 
    233 Author of the idea — [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP")
    234 
    235 It is known that the first player loses if and only if the *xor*-sum of all numbers is 0. Therefore the problem essentially asks to calculate the number of ways to arrange the cards in such a fashion that the *xor*-sum of the numbers on the upper sides of the cards is equal to zero.
    236 
    237 Let ![](https://espresso.codeforces.com/a26deaddb97e114e96ef250a4162f6759150d52b.png) and ![](https://espresso.codeforces.com/4621138b202a80218ea4dca737d50d2cccf4d616.png). Suppose that the cards with indices *j*1, *j*2, ..., *j**k* are faced with numbers of type *b* and all the others with numbers of type *a*. Then the *xor*-sum of this arrangement is equal to ![](https://espresso.codeforces.com/bbf6882ddd10f09f87d402e2e86e8769a06e14aa.png), that is, ![](https://espresso.codeforces.com/53b40640d3e64b7a0b4059ef6107d23567b17d2a.png). Hence we want to find the number of subsets *c**i* with *xor*-sum of *S*.
    238 
    239 Note that we can replace *c*1 with ![](https://espresso.codeforces.com/180d7ae1d6491001ffafb334237d9d73ff6d406c.png), as applying *c*1 is the same as applying ![](https://espresso.codeforces.com/8ce3a7e3be9318c6eb513cfb8187da3e754e0fd0.png). Thus we can freely replace {*c*1, *c*2} with ![](https://espresso.codeforces.com/180d7ae1d6491001ffafb334237d9d73ff6d406c.png) and *c*2 with ![](https://espresso.codeforces.com/42f30dd3482f0887db35fd8544ccd870dae5dd97.png). This means that we can apply the following procedure to simplify the set of *c**i*:
    240 
    241 1. Pick *c**f* with the most significant bit set to one
    242 2. Replace each *c**i* with the bit in that position set to one to ![](https://espresso.codeforces.com/31460a8a3485c37eca35ec6a5c04a974af44c4b0.png)
    243 3. Remove *c**f* from the set
    244 4. Repeat steps 1-5 with the remaining set
    245 5. Add *c**f* back to the set
    246 
    247 After this procedure we get a set that contains *k* zeros and *n* - *k* numbers with the property that the positions of the most significant bit set to one strictly decrease. How do we check now whether it is possible to obtain a subset with *xor*-sum *S*? As we have at most one number with a one in the most significant bit, then it tells us whether we should include that number in the subset or not. Similarly we apply the same argument for all other bits. If we don't obtain a subset with the *xor*-sum equal to *S*, then there is no such subset at all. If we do get a subset with *xor*-sum *S*, then the total number of such subsets is equal to 2*k*, as for each of the *n* - *k* non-zero numbers we already know whether it must be include in such a subset or not, but any subset of *k* zeros doesn't change the *xor*-sum. In this case the probability of the second player winning the game is equal to ![](https://espresso.codeforces.com/2cbd184cc133f21bfaf9b15491acbafe0d7ef061.png), so the first player wins with probability ![](https://espresso.codeforces.com/f7555e9bd9a17fd36a5119ca0b782af6df9cb2ba.png).
    248 
    249 **Code**
    250 
    251 ```
    252 #include <bits/stdc++.h>
    253 
    254 using namespace std;
    255 
    256 const int size = 1000 * 1000 + 1;
    257 const int ssize = 100;
    258 
    259 int n;
    260 long long a[size], b[size];
    261 long long ort[ssize];
    262 long long p[ssize];
    263 
    264 int main() {
    265     long long cur = 0ll;
    266     scanf("%d", &n);
    267     for (int i = 0; i < n; i++) {
    268         scanf("%lld%lld", &a[i], &b[i]);
    269         cur ^= a[i];
    270         a[i] ^= b[i];
    271     }
    272     a[n] = cur;
    273 
    274     int len = 0;
    275     for (int i = 0; i <= n; i++) {
    276         for (int j = 0; j < len; j++) {
    277             if (a[i] & p[j])
    278                 a[i] ^= ort[j];
    279         }
    280         if (a[i]) {
    281             ort[len++] = a[i];
    282             p[len - 1] = ((a[i] ^ (a[i] - 1)) + 1) >> 1;
    283         }        
    284     }
    285     if (a[n]) {
    286         printf("1/1\\n");
    287     } else {
    288         printf("%lld/%lld\\n", (1ll << len) - 1, (1ll << len));
    289     }
    290 
    291     return 0;
    292 }
    293 ```
    294 
    295 ## [662C - Binary Table](/contest/662/problem/C "CROC 2016 - Final Round [Private, For Onsite Finalists Only]")
    296 
    297 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8")
    298 
    299 First let's examine a slow solution that works in *O*(2*n* · *m*). Since each row can be either inverted or not, the set of options of how we can invert the rows may be encoded in a bitmask of length *n*, an integer from 0 to (2*n* - 1), where the *i*-th bit is equal to 1 if and only if we invert the *i*-th row. Each column also represents a bitmask of length *n* (the bits correspond to the values of that row in each of the *n* rows). Let the bitmask of the *i*-th column be *col**i*, and the bitmask of the inverted rows be *mask*. After inverting the rows the *i*-th column will become ![](https://espresso.codeforces.com/5cdb53b9c35b093b093d3b0c92d1ee892fec9a67.png). Suppose that ![](https://espresso.codeforces.com/5cdb53b9c35b093b093d3b0c92d1ee892fec9a67.png) contains ![](https://espresso.codeforces.com/0877b1f024281b9524185ed8ca652f4ae02029c9.png) ones. Then we can obtain either *k* or (*n* - *k*) ones in this column, depending on whether we invert the *i*-th column itself. It follows that for a fixed bitmask *mask* the minimum possible number of ones that can be obtained is equal to ![](https://espresso.codeforces.com/f5695233dacf6cf0c631ce6cae8b588762063137.png).
    300 
    301 Now we want to calculate this sum faster than *O*(*m*). Note that we are not interested in the value of the mask ![](https://espresso.codeforces.com/5cdb53b9c35b093b093d3b0c92d1ee892fec9a67.png) itself, but only in the number of ones it contains (from 0 to *n*). Therefore we may group the columns by the value of ![](https://espresso.codeforces.com/ddeeb2d263675697aac7e27e5330c844deb5f530.png). Let *dp*[*k*][*mask*] be the number of such *i* that ![](https://espresso.codeforces.com/10b6673083f6b760c543f5f2b33a110c2134680c.png), then for a fixed bitmask *mask* we can calculate the sum in *O*(*n*) — ![](https://espresso.codeforces.com/6b91195bebe70c827de6195a434acf675567352f.png).
    302 
    303 What remains is to calculate the value of *dp*[*k*][*mask*] in a quick way. As the name suggests, we can use dynamic programming for this purpose. The value of *dp*[0][*mask*] can be found in *O*(*m*) for all bitmasks *mask*: each column *col**i* increases *dp*[0][*col**i*] by 1. For *k* > 0, *col**i* and *mask* differ in exactly *k* bits. Suppose *mask* and *col**i* differ in position *p*. Then *col**i* and ![](https://espresso.codeforces.com/804575f93d05a51fd830ebc0c5ec9f5fbbf3eda3.png) differ in exactly (*k* - 1) bits. The number of such columns is equal to ![](https://espresso.codeforces.com/eb4691abb18cbf3d5095955139ac6016655be39b.png), except we counted in also the number of columns *col**i* that differ with ![](https://espresso.codeforces.com/804575f93d05a51fd830ebc0c5ec9f5fbbf3eda3.png) in bit *p* (thus, *mask* and *col**i* have the same value in bit *p*). Thus we need to subtract *dp*[*k* - 2][*mask*], but again, except the columns among these that differ with *mask* in bit *p*. Let ![](https://espresso.codeforces.com/7b8f485c73a79c996a4e697840019b28168e166a.png); by expanding this inclusion-exclusion type argument, we get that the number of masks we are interested in can be expressed as *dp*[*k* - 1][*next*] - *dp*[*k* - 2][*mask*] + *dp*[*k* - 3][*next*] - *dp*[*k* - 4][*mask*] + *dp*[*k* - 5][*next*] - .... By summing all these expressions for each bit *p* from 0 to *n*, we get *dp*[*k*][*mask*] · *k*, since each column is counted in *k* times (for each of the bits *p* where the column differs from *mask*).
    304 
    305 Therefore, we are now able to count the values of *dp*[*k*][*mask*] in time *O*(2*n* · *n*3) using the following recurrence:
    306 
    307 ![](https://espresso.codeforces.com/c731e4b9c3d7089f9561f365e31aca69b672489c.png)
    308 
    309 This is still a tad slow, but we can speed it up to *O*(2*n* · *n*2), for example, in a following fashion:
    310 
    311 ![](https://espresso.codeforces.com/f599c7d4847d1d8d35146bc4a8b921cc26d1d2c4.png)  ![](https://espresso.codeforces.com/329cd5a718069ef571121b26e80bb4b88f373357.png)
    312 
    313 ![](https://espresso.codeforces.com/e0a577f5e6a4ade2410e050791deb8c4f92bb5d5.png)
    314 
    315 **BONUS** Are you able to come up with an even faster solution?
    316 
    317 **Code**
    318 
    319 ```
    320 #include<bits/stdc++.h>
    321 
    322 using namespace std;
    323 
    324 char s[100000];
    325 int col[100000], dp[21][1 << 20];
    326 
    327 int main() {
    328     int n, m;
    329     scanf("%d %d", &n, &m);
    330     for (int i = 0; i < n; i++) {
    331         scanf(" %s", s);
    332 
    333         for (int j = 0; j < m; j++) col[j] |= (s[j] - '0') << i;
    334     }
    335 
    336     for (int i = 0; i < m; i++) dp[0][col[i]]++;
    337 
    338     for (int k = 1; k <= n; k++)
    339         for (int mask = 0; mask < (1 << n); mask++) {
    340             int sum = k > 1 ? (k - 2 - n) * dp[k - 2][mask] : 0;
    341             for (int p = 0; p < n; p++) sum += dp[k - 1][mask ^ (1 << p)];
    342 
    343             dp[k][mask] = sum / k;
    344         }
    345 
    346     int ans = n * m;
    347     for (int mask = 0; mask < (1 << n); mask++) {
    348         int cnt = 0;
    349         for (int k = 0; k <= n; k++) cnt += min(k, n - k) * dp[k][mask];
    350 
    351         ans = min(ans, cnt);
    352     }
    353 
    354     printf("%d\\n", ans);
    355 
    356     return 0;
    357 }
    358 ```
    359 
    360 ## [662E - To Hack or not to Hack](/contest/662/problem/E "CROC 2016 - Final Round [Private, For Onsite Finalists Only]")
    361 
    362 Author of the idea — [Alex_2oo8](/profile/Alex_2oo8 "International Grandmaster Alex_2oo8")
    363 
    364 Observation number one — as you are the only participant who is able to hack, the total score of any other participant cannot exceed 9000 (3 problems for 3000 points). Hence hacking at least 90 solutions automatically guarantees the first place (the hacks alone increase the score by 9000 points).
    365 
    366 Now we are left with the problem where the number of hacks we make is at most 90. We can try each of the 63 possible score assignments for the problems in the end of the round. As we know the final score for each problem, we can calculate the maximum number of hacks we are allowed to make so the problem gets the assigned score. This is also the exact amount of hacks we will make in that problem. As we know the number of hacks we will make, we can calculate our final total score. Now there are at most 90 participants who we can possibly hack. We are interested only in those who are on top of us. By hacking we want to make their final score less than that of us. This problem can by solved by means of dynamic programming:
    367 
    368 *dp*[*p*][*i*][*j*][*k*] — the maximum number of participants among the top *p*, whom we can push below us by hacking first problem *i* times, second problem *j* times and third problem *k* times.
    369 
    370 The recurrence: we pick a subset of solutions of the current participant that we will hack, and if after these hacks we will push him below us, we update the corresponding dp state. For example, if it is enough to hack the first and the third problems, then *dp*[*p* + 1][*i* + 1][*j*][*k* + 1] = *max*(*dp*[*p* + 1][*i* + 1][*j*][*k* + 1], *dp*[*p*][*i*][*j*][*k*] + 1)
    371 
    372 **BONUS** Can you solve this problem if each hack gives only 10 points, not 100?
    373 
    374 **Code**
    375 
    376 ```
    377 #include<bits/stdc++.h>
    378 
    379 #define time ololo
    380 
    381 using namespace std;
    382 
    383 int time[5000][3], n, solved[3], canHack[3], score[3], willHack[3], bestPlace, dp[2][90][90][90], ci, li;
    384 
    385 int submissionScore(int sc, int tm) {
    386     if (tm == 0) return 0;
    387 
    388     return sc * (250 - abs(tm)) / 250;
    389 }
    390 
    391 int calcScore(int p) {
    392     int sum = 0;
    393     for (int i = 0; i < 3; i++) sum += submissionScore(score[i], time[p][i]);
    394 
    395     return sum;
    396 }
    397 
    398 int countHacks(int p) {
    399     int cnt = 0;
    400     for (int i = 0; i < 3; i++) cnt += time[p][i] < 0;
    401 
    402     return cnt;
    403 }
    404 
    405 int solve() {
    406     memset(dp, 0, sizeof dp);
    407 
    408     int myScore = 0;
    409     for (int i = 0; i < 3; i++) myScore += 100 * willHack[i] + submissionScore(score[i], time[0][i]);
    410 
    411     ci = 0;
    412     li = 1;
    413     for (int p = 1; p < n; p++)
    414         if (countHacks(p) > 0 && calcScore(p) > myScore) {
    415             ci ^= 1;
    416             li ^= 1;
    417 
    418             for (int i = 0; i <= willHack[0]; i++)
    419                 for (int j = 0; j <= willHack[1]; j++)
    420                     for (int k = 0; k <= willHack[2]; k++)
    421                         dp[ci][i][j][k] = dp[li][i][j][k];
    422 
    423             for (int ii = 0; ii < 2; ii++)
    424                 for (int jj = 0; jj < 2; jj++)
    425                     for (int kk = 0; kk < 2; kk++) {
    426                         if (ii == 1 && time[p][0] >= 0) continue;
    427                         if (jj == 1 && time[p][1] >= 0) continue;
    428                         if (kk == 1 && time[p][2] >= 0) continue;
    429 
    430                         int s = submissionScore(score[0], time[p][0]) * (ii ^ 1)
    431                               + submissionScore(score[1], time[p][1]) * (jj ^ 1)
    432                               + submissionScore(score[2], time[p][2]) * (kk ^ 1);
    433 
    434                         if (s > myScore) continue;
    435 
    436                         for (int i = ii; i <= willHack[0]; i++)
    437                             for (int j = jj; j <= willHack[1]; j++)
    438                                 for (int k = kk; k <= willHack[2]; k++)
    439                                     dp[ci][i][j][k] = max(dp[ci][i][j][k], dp[li][i - ii][j - jj][k - kk] + 1);
    440                     }
    441         }
    442 
    443     int res = 1 - dp[ci][willHack[0]][willHack[1]][willHack[2]];
    444     for (int p = 1; p < n; p++) if (calcScore(p) > myScore) res++;
    445 
    446     return res;
    447 }
    448 
    449 void brute(int p) {
    450     if (p == 3) {
    451         int res = solve();
    452 
    453         bestPlace = min(bestPlace, res);
    454 
    455         return;
    456     }
    457 
    458     for (int i = 0; i < 6; i++) {
    459         int mn = i == 5 ? 0 : (n >> (i + 1)) + 1;
    460         int mx = (n >> i);
    461 
    462         if (solved[p] >= mn && solved[p] - canHack[p] <= mx) {
    463             score[p] = 500 * (i + 1);
    464             willHack[p] = min(canHack[p], solved[p] - mn);
    465 
    466             brute(p + 1);
    467         }
    468     }
    469 }
    470 
    471 int main() {
    472     memset(solved, 0, sizeof solved);
    473     memset(canHack, 0, sizeof canHack);
    474     
    475     scanf("%d", &n);
    476     for (int i = 0; i < n; i++)
    477         for (int j = 0; j < 3; j++) {
    478             scanf("%d", &time[i][j]);
    479 
    480             solved[j] += time[i][j] != 0;
    481             canHack[j] += time[i][j] < 0;
    482         }
    483 
    484     if (canHack[0] + canHack[1] + canHack[2] > 89) {
    485         printf("1\\n");
    486 
    487         return 0;
    488     }
    489 
    490     bestPlace = n;
    491     brute(0);
    492 
    493     printf("%d\\n", bestPlace);
    494 
    495     return 0;
    496 }
    497 ```