680.md (35783B)
1 Source: https://codeforces.com/blog/entry/45310 2 3 # [680A - Bear and Five Cards](/contest/680/problem/A "Codeforces Round 356 (Div. 2)") 4 5 Iterate over all pairs and triples of numbers, and for each of them check if all two/three numbers are equal. If yes then consider the sum of remaining numbers as the answer (the final answer will be the minimum of considered sums). Below you can see two ways to implement the solution. 6 7 **code1** 8 9 ``` 10 #include<bits/stdc++.h> 11 using namespace std; 12 int main() { 13 int t[5]; 14 int s = 0; 15 for(int i = 0; i < 5; ++i) { 16 scanf("%d", &t[i]); 17 s += t[i]; 18 } 19 int best = s; 20 21 // discard 2 cards 22 for(int a = 0; a < 5; ++a) 23 for(int b = a + 1; b < 5; ++b) 24 if(t[a] == t[b]) 25 best = min(best, s - 2 * t[a]); 26 27 // or discard 3 cards 28 for(int a = 0; a < 5; ++a) 29 for(int b = a + 1; b < 5; ++b) 30 for(int c = b + 1; c < 5; ++c) 31 if(t[a] == t[b] && t[a] == t[c]) 32 best = min(best, s - 3 * t[a]); 33 34 printf("%d\n", best); 35 return 0; 36 } 37 ``` 38 39 **code2** 40 41 ``` 42 #include<bits/stdc++.h> 43 using namespace std; 44 int main() { 45 int t[5]; 46 for(int i = 0; i < 5; ++i) 47 scanf("%d", &t[i]); 48 sort(t, t + 5); 49 int best_remove = 0; 50 for(int i = 0; i < 5; ++i) { 51 if(i + 1 < 5 && t[i] == t[i+1]) 52 best_remove = max(best_remove, 2 * t[i]); 53 if(i + 2 < 5 && t[i] == t[i+2]) 54 best_remove = max(best_remove, 3 * t[i]); 55 } 56 printf("%dn", t[0]+t[1]+t[2]+t[3]+t[4]-best_remove); 57 return 0; 58 } 59 ``` 60 61 # [680B - Bear and Finding Criminals](/contest/680/problem/B "Codeforces Round 356 (Div. 2)") 62 63 Limak can't catch a criminal only if there are two cities at the same distance and only one of them contains a criminal. You should iterate over the distance and for each distance *d* check if *a* - *d* and *a* + *d* are both in range [1, *n*] and if only one of them has *t**i* = 1. 64 65 **code1** 66 67 ``` 68 #include<bits/stdc++.h> 69 using namespace std; 70 const int nax = 1005; 71 int t[nax]; 72 int main() { 73 int n, a; 74 scanf("%d%d", &n, &a); 75 for(int i = 1; i <= n; ++i) 76 scanf("%d", &t[i]); 77 int answer = 0; 78 for(int i = 1; i <= n; ++i) if(t[i]) { 79 // can we catch criminal in city i? 80 int distance = i - a; // distance from a 81 int j = a - distance; // the other city at the same distance 82 if(j < 1 || j > n || t[i] == t[j]) 83 ++answer; 84 } 85 printf("%dn", answer); 86 return 0; 87 } 88 ``` 89 90 **code2** 91 92 ``` 93 #include<bits/stdc++.h> 94 using namespace std; 95 const int nax = 1005; 96 int t[nax]; 97 bool impossible[nax]; 98 int main() { 99 int n, a; 100 scanf("%d%d", &n, &a); 101 for(int i = 1; i <= n; ++i) 102 scanf("%d", &t[i]); 103 for(int i = 1; i <= n; ++i) 104 for(int j = i + 1; j <= n; ++j) 105 if(abs(i - a) == abs(j - a) && t[i] != t[j]) { 106 // i and j have the same distance to a 107 // also, there is a criminal in exactly one of them 108 impossible[i] = impossible[j] = true; 109 } 110 int answer = 0; 111 for(int i = 1; i <= n; ++i) 112 if(t[i] == 1 && !impossible[i]) 113 ++answer; 114 printf("%dn", answer); 115 return 0; 116 } 117 ``` 118 119 # [679A - Bear and Prime 100](/contest/679/problem/A "Codeforces Round 356 (Div. 1)") 120 121 If a number is composite then it's either divisible by *p*2 for some prime *p*, or divisible by two distinct primes *p* and *q*. To check the first condition, it's enough to check all possible *p*2 (so, numbers 4, 9, 25, 49). If at least one gives "yes" then the hidden number if composite. 122 123 If there are two distinct prime divisors *p* and *q* then both of them are at most 50 — otherwise the hidden number would be bigger than 100 (because for *p* ≥ 2 and *q* > 50 we would get *p*·*q* > 100). So, it's enough to check primes up to 50 (there are 15 of them), and check if at least two of them are divisors. 124 125 **code1** 126 127 ``` 128 #include<bits/stdc++.h> 129 using namespace std; 130 131 bool isPrime(int a) { 132 for(int i = 2; i * i <= a; ++i) 133 if(a % i == 0) 134 return false; 135 return true; 136 } 137 138 bool divisible(int a) { 139 printf("%dn", a); 140 fflush(stdout); 141 char sl[10]; 142 scanf("%s", sl); 143 return sl[0] == 'y' || sl[0] == 'Y'; 144 } 145 146 int HIGH = 100; 147 148 int main() { 149 int counter = 0; // we print "composite" if counter >= 2 150 for(int a = 2; a <= HIGH/2 && counter < 2; ++a) 151 if(isPrime(a)) 152 if(divisible(a)) { 153 ++counter; 154 if(a * a <= HIGH && divisible(a * a)) 155 ++counter; 156 } 157 puts(counter >= 2 ? "composite" : "prime"); 158 return 0; 159 } 160 ``` 161 162 **code2, Python** 163 164 ``` 165 from sys import stdout 166 167 PRIMES = [x for x in range(2,100) if 0 not in [x%i for i in range(2,x)]] 168 169 NORMAL = PRIMES[:15] 170 SQUARES = [x*x for x in PRIMES[:4]] 171 172 for ele in SQUARES: 173 print(ele) 174 stdout.flush() 175 x = input() 176 if x == "yes": 177 print("composite") 178 exit(0) 179 180 yes = 0 181 for ele in NORMAL: 182 print(ele) 183 stdout.flush() 184 x = input() 185 if x == "yes": 186 yes += 1 187 188 print("prime" if yes < 2 else "composite") 189 ``` 190 191 # [679B - Bear and Tower of Cubes](/contest/679/problem/B "Codeforces Round 356 (Div. 1)") 192 193 Let's find the maximum *a* that *a*3 ≤ *m*. Then, it's optimal to choose *X* that the first block will have side *a* or *a* - 1. Let's see why. 194 195 * If the first block has side *a* then we are left with *m*2 = *m* - *first*_*block* = *m* - *a*3. 196 * If the first block has side *a* - 1 then the initial *X* must be at most *a*3 - 1 (because otherwise we would take a block with side *a*), so we are left with *m*2 = *a*3 - 1 - *first*_*block* = *a*3 - 1 - (*a* - 1)3 197 * If the first blocks has side *a* - 2 then the initial *X* must be at most (*a* - 1)3 - 1, so we are left with *m*2 = (*a* - 1)3 - 1 - *first*_*block* = (*a* - 1)3 - 1 - (*a* - 2)3. 198 199 We want to first maximize the number of blocks we can get with new limit *m*2. Secondarily, we want to have the biggest initial *X*. You can analyze the described above cases and see that the first block with side (*a* - 2)3 must be a worse choice than (*a* - 1)3. It's because we start with smaller *X* and we are left with smaller *m*2. The situation for even smaller side of the first block would be even worse. 200 201 Now, you can notice that the answer will be small. From *m* of magnitude *a*3 after one block we get *m*2 of magnitude *a*2. So, from *m* we go to *m*2 / 3, which means that the answer is *O*(*loglog*(*m*)). The exact maximum answer turns out to be 18. 202 203 The intended solution is to use the recursion and brutally check both cases: taking *a*3 and taking (*a* - 1)3 where *a* is maximum that *a*3 ≤ *m*. It's so fast that you can even find *a* in *O*(*m*1 / 3), increasing *a* by one. 204 205 **code1** 206 207 ``` 208 #include<bits/stdc++.h> 209 using namespace std; 210 typedef long long ll; 211 212 pair<ll,ll> best; 213 214 ll my_pow(ll x) { return x * x * x; } 215 216 void rec(ll m, ll steps, ll subtracted) { 217 if(m == 0) { 218 best = max(best, make_pair(steps, subtracted)); 219 return; 220 } 221 ll x = 1; 222 while(my_pow(x+1) <= m) ++x; 223 rec(m - my_pow(x), steps+1, subtracted + my_pow(x)); 224 if(x - 1 >= 0) 225 rec(my_pow(x)-1-my_pow(x-1), steps+1, subtracted + my_pow(x-1)); 226 } 227 228 int main() { 229 ll m; 230 scanf("%lld", &m); 231 rec(m, 0, 0); 232 printf("%lld %lldn", best.first, best.second); 233 return 0; 234 } 235 ``` 236 237 **code2** 238 239 ``` 240 #include<bits/stdc++.h> 241 using namespace std; 242 typedef long long ll; 243 244 ll my_pow(ll x) { return x * x * x; } 245 246 ll steps(ll m) { // works in O(m^(1/3)) 247 if(m <= 7) return m; 248 ll x = 1; 249 while(my_pow(x+1) <= m) ++x; 250 return 1 + steps(max(m - my_pow(x), my_pow(x)-1-my_pow(x-1))); 251 } 252 253 int main() { 254 ll m; 255 scanf("%lld", &m); 256 ll subtracted = 0, steps_so_far = 0; 257 while(m) { 258 ++steps_so_far; 259 ll x = 1; 260 while(my_pow(x+1) <= m) ++x; 261 if(steps(m) == 1 + steps(m - my_pow(x))) { 262 m -= my_pow(x); 263 subtracted += my_pow(x); 264 } 265 else { 266 m = my_pow(x) - 1 - my_pow(x-1); 267 subtracted += my_pow(x-1); 268 } 269 } 270 printf("%lld %lldn", steps_so_far, subtracted); 271 return 0; 272 } 273 ``` 274 275 **code3** 276 277 ``` 278 #include "bits/stdc++.h" 279 280 using namespace std; 281 282 #define ll long long 283 284 vector <ll> X; 285 map <ll, pair <int, ll> > M; 286 287 pair <int, ll> go(ll x) 288 { 289 if(x <= 1) 290 return {x,x}; 291 if(M.find(x) != M.end()) 292 return M[x]; 293 int i = upper_bound(X.begin(), X.end(), x) - X.begin() - 1; 294 int p1, p2; 295 long long q1, q2; 296 tie(p1, q1) = go(x - X[i]); 297 tie(p2, q2) = go(X[i] - 1); 298 return M[x] = max(make_pair(p1+1, q1+X[i]), {p2, q2}); 299 } 300 301 int main() 302 { 303 for(int i=0; i<=1e5+7; i++) 304 X.push_back(1LL*i*i*i); 305 ll x; 306 cin >> x; 307 int a; 308 long long b; 309 tie(a,b) = go(x); 310 cout << a << " " << b << "n"; 311 } 312 ``` 313 314 # [679C - Bear and Square Grid](/contest/679/problem/C "Codeforces Round 356 (Div. 1)") 315 316 Let's first find CC's (connected components) in the given grid, using DFS's. 317 318 We will consider every possible placement of a *k* × *k* square. When the placement is fixed then the answer is equal to the sum of *k*2 the the sum of sizes of CC's touching borders of the square (touching from outside), but for those CC's we should only count their cells that are outside of the square — not to count something twice. We will move a square, and at the same time for each CC we will keep the number of its cells outside the square. 319 320 We will used a sliding-window technique. Let's fix row of the grid — the upper row of the square. Then, we will first place the square on the left, and then we will slowly move a square to the right. As we move a square, we should iterate over cells that stop or start to belong to the square. For each such empty cell we should add or subtract 1 from the size of its CC (ids and sizes of CC's were found at the beginning). 321 322 And for each placement we consider, we should iterate over outside borders of the square (4*k* cells — left, up, right and down side) and sum up sizes of CC's touching our square. Be careful to not count some CC twice — you can e.g. keep an array of booleans and mark visited CC's. After checking all 4*k* cells you should clear an array, but you can't do it in O(number_of_all_components) because it would be too slow. You can e.g. also add visited CC's to some vector, and later in the boolean array clear only CC's from the vector (and then clear vector). 323 324 The complexity is *O*(*n*2·*k*). 325 326 **code1** 327 328 ``` 329 #include<bits/stdc++.h> 330 using namespace std; 331 const int nax = 505; 332 int n; 333 char grid[nax][nax]; // input 334 int cc[nax][nax]; // id of CC in which this cell is 335 int cc_size[nax*nax]; // size of CC 336 int when_added[nax*nax]; 337 338 const int dx[4] = {-1, 1, 0, 0}; 339 const int dy[4] = {0, 0, -1, 1}; 340 const char EMPTY = '.'; 341 342 bool inside(int x, int y) { 343 return 0 <= min(x, y) && max(x, y) < n; 344 } 345 346 void dfs(int x, int y, int which_cc) { 347 cc[x][y] = which_cc; 348 ++cc_size[which_cc]; 349 for(int i = 0; i < 4; ++i) { // iterate of 4 adjacent cells 350 int x2 = x + dx[i]; 351 int y2 = y + dy[i]; 352 if(inside(x2, y2) && grid[x2][y2] == EMPTY && cc[x2][y2] == 0) 353 dfs(x2, y2, which_cc); 354 } 355 } 356 357 void add(int x, int y, int & answer, int current_time) { 358 if(inside(x, y) && grid[x][y] == EMPTY) { 359 int id = cc[x][y]; 360 if(when_added[id] != current_time) { 361 when_added[id] = current_time; 362 answer += cc_size[id]; 363 } 364 } 365 } 366 367 int main() { 368 int k; 369 scanf("%d%d", &n, &k); 370 for(int i = 0; i < n; ++i) 371 scanf("%s", grid[i]); 372 373 // run DFS many times to find CC's (connected components) 374 int how_many_cc = 0; 375 for(int x = 0; x < n; ++x) 376 for(int y = 0; y < n; ++y) 377 if(grid[x][y] == EMPTY && cc[x][y] == 0) 378 dfs(x, y, ++how_many_cc); 379 380 int cur_time = 1; 381 int best_answer = 0; 382 383 for(int y_low = 0; y_low + k <= n; ++y_low) { 384 // first we put a square with corner in (0, y_low) 385 for(int x = 0; x < k; ++x) 386 for(int y = y_low; y < y_low + k; ++y) 387 --cc_size[cc[x][y]]; // subtract cells inside a square 388 389 for(int x_low = 0; x_low + k <= n; ++x_low) { 390 int answer = k * k; // all cells inside a square 391 // consider one row: below, above, left, right 392 for(int x = x_low; x < x_low + k; ++x) { 393 add(x, y_low - 1, answer, cur_time); 394 add(x, y_low + k, answer, cur_time); 395 } 396 for(int y = y_low; y < y_low + k; ++y) { 397 add(x_low - 1, y, answer, cur_time); 398 add(x_low + k, y, answer, cur_time); 399 } 400 ++cur_time; 401 best_answer = max(best_answer, answer); 402 403 if(x_low + k != n) { 404 // move a square to increase x_low by 1 405 for(int y = y_low; y < y_low + k; ++y) { 406 ++cc_size[cc[x_low][y]]; // remove cells with x = x_low 407 --cc_size[cc[x_low+k][y]]; // insert cells with x = x_low+k 408 } 409 } 410 } 411 412 for(int x = n - k; x < n; ++x) 413 for(int y = y_low; y < y_low + k; ++y) 414 ++cc_size[cc[x][y]]; // we don't need cells inside to be subtracted 415 } 416 printf("%dn", best_answer); 417 return 0; 418 } 419 ``` 420 421 **code2** 422 423 ``` 424 #include<bits/stdc++.h> 425 using namespace std; 426 #define FOR(i,a,b) for(int i = (a); i <= (b); ++i) 427 #define FORD(i,a,b) for(int i = (a); i >= (b); --i) 428 #define RI(i,n) FOR(i,1,(n)) 429 #define REP(i,n) FOR(i,0,(n)-1) 430 #define mini(a,b) a=min(a,b) 431 #define maxi(a,b) a=max(a,b) 432 #define mp make_pair 433 #define pb push_back 434 #define st first 435 #define nd second 436 #define sz(w) (int) w.size() 437 typedef vector<int> vi; 438 typedef long long ll; 439 typedef long double ld; 440 typedef pair<int,int> pii; 441 const int inf = 1e9 + 5; 442 const int nax = 500 + 5; 443 const int nax2 = nax * nax; 444 445 int n,k; 446 447 int ile_na_zew, akt_stan = 1; 448 449 char t[nax][nax]; 450 int ojc[nax][nax]; 451 int ilosc[nax2], lewo[nax2], prawo[nax2], gora[nax2], dol[nax2]; 452 int suma[nax][nax], kol[nax], stan[nax2]; 453 bool bylo[nax][nax]; 454 455 vector<pair<pii, int> > wiersz[nax]; 456 457 int ruchi[] = {-1, 0, 1, 0}; 458 int ruchj[] = {0, -1, 0, 1}; 459 460 void dfs(int i, int j, int wsk) { 461 ilosc[wsk]++; 462 ojc[i][j] = wsk; 463 bylo[i][j] = true; 464 lewo[wsk] = min(lewo[wsk], j); 465 prawo[wsk] = max(prawo[wsk], j); 466 gora[wsk] = min(gora[wsk], i); 467 dol[wsk] = max(dol[wsk], i); 468 469 REP(g,4) { 470 int ni = i + ruchi[g]; 471 int nj = j + ruchj[g]; 472 473 if (t[ni][nj] == '.' && bylo[ni][nj] == false) 474 dfs(ni,nj,wsk); 475 } 476 } 477 478 void check(int o) { 479 if (stan[o] != akt_stan) 480 ile_na_zew += ilosc[o]; 481 stan[o] = akt_stan; 482 } 483 484 int main() { 485 scanf("%d%d",&n,&k); 486 FOR(i,1,n) scanf(" %s",t[i]+1); 487 488 int wsk = 1; 489 FOR(i,1,n) FOR(j,1,n) if (t[i][j] == '.' && !bylo[i][j]) { 490 lewo[wsk] = prawo[wsk] = j; 491 gora[wsk] = dol[wsk] = i; 492 dfs(i,j,wsk); 493 //printf("%dn",ilosc[wsk]); 494 if (prawo[wsk] - lewo[wsk] + 1 <= k && dol[wsk] - gora[wsk] + 1 <= k) { 495 //puts("DD"); 496 int x = max(1, dol[wsk] - k + 1); 497 wiersz[x].pb(mp(mp(lewo[wsk], prawo[wsk]), ilosc[wsk])); 498 wiersz[gora[wsk]+1].pb(mp(mp(lewo[wsk], prawo[wsk]), -ilosc[wsk])); 499 } 500 ++wsk; 501 } 502 503 FOR(i,1,n) FOR(j,1,n) suma[i][j] = suma[i-1][j] + suma[i][j-1] - suma[i-1][j-1] + (t[i][j] == '.'); 504 //FOR(i,1,n) FOR(j,1,n) printf("(%d,%d): %dn",i,j,suma[i][j]); 505 506 int res = 0; 507 FOR(i,1,n-k+1) { 508 for (auto p: wiersz[i]) { 509 int l = max(1, p.st.nd - k + 1); 510 //printf("%d %d %dn",l,p.st.st,p.nd); 511 kol[l] += p.nd; 512 kol[p.st.st + 1] -= p.nd; 513 } 514 515 int suma_s = 0; 516 FOR(j,1,n-k+1) { 517 suma_s += kol[j]; 518 int ile_w_s = suma[i+k-1][j+k-1] - suma[i-1][j+k-1] - suma[i+k-1][j-1] + suma[i-1][j-1]; 519 ile_na_zew = 0; 520 REP(g,k) { 521 check(ojc[i-1][j+g]); 522 check(ojc[i+k][j+g]); 523 check(ojc[i+g][j-1]); 524 check(ojc[i+g][j+k]); 525 } 526 527 int x = ile_na_zew + (k * k - ile_w_s) + suma_s; 528 //printf("(%d,%d) : %d %d %d %dn",i,j,ile_na_zew, ile_w_s, suma_s, x); 529 530 res = max(res, x); 531 ++akt_stan; 532 } 533 } 534 printf("%dn",res); 535 return 0; 536 } 537 ``` 538 539 **code3, Java** 540 541 ``` 542 import java.io.OutputStream; 543 import java.io.IOException; 544 import java.io.InputStream; 545 import java.io.PrintWriter; 546 import java.util.Arrays; 547 import java.util.List; 548 import java.util.StringTokenizer; 549 import java.io.IOException; 550 import java.io.BufferedReader; 551 import java.io.InputStreamReader; 552 import java.util.ArrayList; 553 import java.io.InputStream; 554 555 /** 556 * Built using CHelper plug-in 557 * Actual solution is at the top 558 * 559 * @author AlexFetisov 560 */ 561 public class Main { 562 public static void main(String[] args) { 563 InputStream inputStream = System.in; 564 OutputStream outputStream = System.out; 565 InputReader in = new InputReader(inputStream); 566 PrintWriter out = new PrintWriter(outputStream); 567 TaskE_356 solver = new TaskE_356(); 568 solver.solve(1, in, out); 569 out.close(); 570 } 571 572 static class TaskE_356 { 573 int n; 574 int k; 575 boolean[][] f; 576 List<Integer> componentCellCount; 577 int[][] color; 578 int x = 0; 579 int y = 0; 580 int totalEmpty = 0; 581 int sumInComponents = 0; 582 int[] amInComponents; 583 int[] flag; 584 int currentFlagColor = 0; 585 586 public void solve(int testNumber, InputReader in, PrintWriter out) { 587 n = in.nextInt(); 588 k = in.nextInt(); 589 f = new boolean[n][n]; 590 color = new int[n][n]; 591 ArrayUtils.fill(color, -1); 592 for (int i = 0; i < n; ++i) { 593 char[] c = in.nextString().toCharArray(); 594 for (int j = 0; j < n; ++j) { 595 f[i][j] = (c[j] == '.'); 596 } 597 } 598 599 // Caclulate all CC 600 int res = 0; 601 componentCellCount = new ArrayList<Integer>(); 602 int currentComponentId = 0; 603 for (int i = 0; i < n; ++i) { 604 for (int j = 0; j < n; ++j) { 605 if (color[i][j] == -1) { 606 int count = dfs(i, j, currentComponentId++); 607 componentCellCount.add(count); 608 res = Math.max(res, count); 609 } 610 } 611 } 612 613 flag = new int[currentComponentId]; 614 amInComponents = new int[currentComponentId]; 615 // Preprocess first square 616 for (int i = 0; i < k; ++i) { 617 for (int j = 0; j < k; ++j) { 618 addCell(i, j); 619 } 620 } 621 622 res = Math.max(res, checkResult()); 623 624 for (int i = 0; i <= n - k; ++i) { 625 int delta = i % 2 == 0 ? 1 : -1; 626 for (int j = 0; j < n - k; ++j) { 627 moveSquare(0, x, y, x, y + delta); 628 y += delta; 629 res = Math.max(res, checkResult()); 630 } 631 if (i != n - k) { 632 moveSquare(1, x, y, x + 1, y); 633 ++x; 634 res = Math.max(res, checkResult()); 635 } 636 } 637 out.println(res); 638 } 639 640 void moveSquare(int type, int cx, int cy, int nx, int ny) { 641 if (type == 0) { 642 if (ny < cy) { 643 for (int i = 0; i < k; ++i) { 644 removeCell(cx + i, cy + k - 1); 645 addCell(cx + i, ny); 646 } 647 } else { 648 for (int i = 0; i < k; ++i) { 649 removeCell(cx + i, cy); 650 addCell(cx + i, ny + k - 1); 651 } 652 } 653 } else { 654 for (int i = 0; i < k; ++i) { 655 removeCell(cx, cy + i); 656 addCell(nx + k - 1, cy + i); 657 } 658 } 659 } 660 661 void removeCell(int cx, int cy) { 662 if (f[cx][cy]) { 663 --totalEmpty; 664 amInComponents[color[cx][cy]]--; 665 if (amInComponents[color[cx][cy]] == 0) { 666 sumInComponents -= componentCellCount.get(color[cx][cy]); 667 } 668 } 669 } 670 671 void addCell(int cx, int cy) { 672 if (f[cx][cy]) { 673 ++totalEmpty; 674 amInComponents[color[cx][cy]]++; 675 if (amInComponents[color[cx][cy]] == 1) { 676 sumInComponents += componentCellCount.get(color[cx][cy]); 677 } 678 } 679 } 680 681 int dfs(int cx, int cy, int cId) { 682 if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0; 683 if (color[cx][cy] != -1) return 0; 684 if (!f[cx][cy]) return 0; 685 color[cx][cy] = cId; 686 int am = 1; 687 am += dfs(cx - 1, cy, cId); 688 am += dfs(cx + 1, cy, cId); 689 am += dfs(cx, cy - 1, cId); 690 am += dfs(cx, cy + 1, cId); 691 return am; 692 } 693 694 int checkResult() { 695 ++currentFlagColor; 696 int res = k * k - totalEmpty + sumInComponents; 697 for (int i = 0; i < k; ++i) { 698 res += checkCell(x - 1, y + i); 699 res += checkCell(x + k, y + i); 700 res += checkCell(x + i, y - 1); 701 res += checkCell(x + i, y + k); 702 } 703 return res; 704 } 705 706 int checkCell(int cx, int cy) { 707 if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0; 708 if (!f[cx][cy]) return 0; 709 if (amInComponents[color[cx][cy]] > 0) return 0; 710 if (flag[color[cx][cy]] == currentFlagColor) return 0; 711 flag[color[cx][cy]] = currentFlagColor; 712 return componentCellCount.get(color[cx][cy]); 713 } 714 715 } 716 717 static class ArrayUtils { 718 public static void fill(int[][] f, int value) { 719 for (int i = 0; i < f.length; ++i) { 720 Arrays.fill(f[i], value); 721 } 722 } 723 724 } 725 726 static class InputReader { 727 private BufferedReader reader; 728 private StringTokenizer stt; 729 730 public InputReader(InputStream stream) { 731 reader = new BufferedReader(new InputStreamReader(stream)); 732 } 733 734 public String nextLine() { 735 try { 736 return reader.readLine(); 737 } catch (IOException e) { 738 return null; 739 } 740 } 741 742 public String nextString() { 743 while (stt == null || !stt.hasMoreTokens()) { 744 stt = new StringTokenizer(nextLine()); 745 } 746 return stt.nextToken(); 747 } 748 749 public int nextInt() { 750 return Integer.parseInt(nextString()); 751 } 752 753 } 754 } 755 ``` 756 757 # [679D - Bear and Chase](/contest/679/problem/D "Codeforces Round 356 (Div. 1)") 758 759 Check my code below, because it has a lot of comments. 760 761 First, in *O*(*n*3) or faster find all distances between pairs of cities. 762 763 Iterate over all *g*1 — the first city in which you use the BCD. Then, for iterate over all *d*1 — the distance you get. Now, for all cities calculate the probability that Limak will be there in the second day (details in my code below). Also, in a vector `interesting` let's store all cities that are at distance *d*1 from city *g*1. 764 765 Then, iterate over all *g*2 — the second city in which you use the BCD. For cities from `interesting`, we want to iterate over them and for each distinct distance from *g*2 to choose the biggest probability (because we will make the best guess there is). 766 767 Magic: the described approach has four loops (one in the other) but it's *O*(*n*3). 768 769 Proof is very nice and I encourage you to try to get it yourself. 770 771 **Proof here** 772 773 After fixing g1 divide cities by their distance from g1. Then, when we get distance d1 in the first day, then in the second day all possible cities are at distance d1-1, d1 and d1+1. So, we will consider each city at most three times. 774 775 **code1** 776 777 ``` 778 #include<bits/stdc++.h> 779 using namespace std; 780 #define FOR(i,a,b) for(int i = (a); i <= (b); ++i) 781 typedef double T; 782 const int nax = 1005; 783 int dist[nax][nax]; 784 vector<int> w[nax]; 785 T p_later[nax]; // p[v] - probability for city v in the second day 786 T p_dist_max[nax]; 787 bool vis[nax]; 788 789 void max_self(T & a, T b) { 790 a = max(a, b); 791 } 792 793 T consider_tomorrow(int n, int g1, int dist1) { 794 T best_tomorrow = 0; 795 // we need complexity O(n * x) 796 // where x denotes the number of v that |dist1-dist[g1][v]| <= 1 797 for(int i = 1; i <= n; ++i) { 798 p_later[i] = 0; 799 vis[i] = false; 800 } 801 vector<int> interesting; 802 for(int v = 1; v <= n; ++v) if(dist[g1][v] == dist1) 803 for(int b : w[v]) { 804 // Limak started in v with prob. 1/n 805 // he then moved to b with prob. 1/degree[v] 806 p_later[b] += (T) 1 / n / w[v].size(); 807 if(!vis[b]) { 808 vis[b] = true; 809 interesting.push_back(b); 810 } 811 } 812 813 // interesting.size() <= x, where x is defined above (needed for complexity) 814 for(int g2 = 1; g2 <= n; ++g2) { 815 T local_sum = 0; // over situations with fixed g1, dist1, g2 816 817 for(int b : interesting) 818 max_self(p_dist_max[dist[g2][b]], p_later[b]); 819 for(int b : interesting) { 820 local_sum += p_dist_max[dist[g2][b]]; 821 p_dist_max[dist[g2][b]] = 0; // so it won't be calculated twice 822 } 823 max_self(best_tomorrow, local_sum); 824 } 825 return best_tomorrow; 826 } 827 828 int main() { 829 int n, m; 830 scanf("%d%d", &n, &m); 831 FOR(i,1,n) FOR(j, 1, n) if(i != j) 832 dist[i][j] = n + 1; // infinity 833 FOR(i,1,m) { 834 int a, b; 835 scanf("%d%d", &a, &b); 836 w[a].push_back(b); 837 w[b].push_back(a); 838 dist[a][b] = dist[b][a] = 1; 839 } 840 // Floyd-Warshall 841 FOR(b,1,n)FOR(a,1,n)FOR(c,1,n) 842 dist[a][c] = min(dist[a][c], dist[a][b] + dist[b][c]); 843 844 // g1 is the first guess 845 T answer = 0; 846 FOR(g1, 1, n) { 847 T sum_over_dist1 = 0; 848 FOR(dist1, 0, n) { 849 int cnt_cities = 0; 850 FOR(i, 1, n) if(dist[g1][i] == dist1) 851 ++cnt_cities; 852 if(cnt_cities == 0) continue; // there are no cities within distance dist1 853 854 // 1) consider guessing immediately 855 T immediately = (T) 1 / n; // how much it counts towards the answer 856 // 2) consider waiting for tomorrow 857 T second_day = consider_tomorrow(n, g1, dist1); 858 sum_over_dist1 += max(immediately, second_day); 859 } 860 max_self(answer, sum_over_dist1); 861 } 862 printf("%.12lfn", (double) answer); 863 return 0; 864 } 865 ``` 866 867 # [679E - Bear and Bad Powers of 42](/contest/679/problem/E "Codeforces Round 356 (Div. 1)") 868 869 The only special thing in numbers 1, 42, ... was that there are only few such numbers (in the possible to achieve range, so up to about 1014). 870 871 Let's first solve the problem without queries "in the interval change all numbers to x". Then, we can make a tree with operations (possible with lazy propagation): 872 873 * add on the interval 874 * find minimum in the whole tree 875 876 In a tree for each index  let's keep the distance to the next power of 42. After each "add on the interval" we should find the minimum and check if it's positive. If not then we should change value of the closest power of 42 for this index, and change the value in the tree. Then, we should again find the minimum in the tree, and so on. The amortized complexity is *O*((*n* + *q*) * *log*(*n*) * *log*42(*values*)). It can be proved that numbers won't exceed (*n* + *q*) * 1*e*9 * *log*. 877 878 Now let's think about the remaining operation of changing all interval to some value. We can set only one number (the last one) to the given value, and set other values to INF. We want to guarantee that if *t*[*i*] ≠ *t*[*i* + 1] then the *i*-th value is correctly represented in the tree. Otherwise, it can be INF instead (or sometimes it may be correctly represented, it doesn't bother me). When we have the old query of type "add something to interval [*a*, *b*]" then if index *a* - 1 or index *b* contains INF in the tree then we should first retrieve the true value there. You can see that each operation changes *O*(1) values from INF to something finite. So, the amortized complexity is still *O*((*n* + *q*) * *log*(*n*) * *log*42(*values*). 879 880 One thing regarding implementation. In my solution there is "*set* < *int* > *interesting*" containing indices with INF value. I think it's easier to implemement the solution with this set. 881 882 **code1** 883 884 ``` 885 #include<bits/stdc++.h> 886 using namespace std; 887 typedef long long ll; 888 const int nax = 1e6 + 5; 889 const int pot = 256 * 1024; 890 const ll INF = 3e18L; 891 ll cur_power[nax]; // the least power of 42 larger than the current value 892 // true_value + remaining = cur_power, where remaining=tr[pot+i] 893 894 struct Node { 895 ll local; 896 ll lazy; 897 ll smallest() { return local + lazy; } // smallest value in this subtree 898 } tr[2*pot]; 899 900 void propagate(int i) { 901 assert(i < pot); 902 tr[2*i].lazy += tr[i].lazy; 903 tr[2*i+1].lazy += tr[i].lazy; 904 tr[i].local += tr[i].lazy; 905 tr[i].lazy = 0; 906 } 907 void act(int i) { 908 assert(i < pot); 909 assert(tr[i].lazy == 0); 910 tr[i].local = min(tr[2*i].smallest(), tr[2*i+1].smallest()); 911 } 912 913 void change(int i, int low, int high, int q_low, int q_high, ll val) { 914 if(q_low <= low && high <= q_high) { 915 tr[i].lazy += val; 916 return; 917 } 918 propagate(i); 919 int mid1 = (low + high) / 2; 920 if(q_low <= mid1) 921 change(2*i, low, mid1, q_low, q_high, val); 922 if(q_high >= mid1+1) 923 change(2*i+1, mid1+1, high, q_low, q_high, val); 924 act(i); 925 } 926 void change(int q_low, int q_high, ll val) { 927 change(1, 0, pot - 1, q_low, q_high, val); 928 } 929 930 int where_smallest(int i = 1) { 931 if(i >= pot) return i - pot; 932 propagate(i); 933 int ret; 934 if(tr[2*i].smallest() < tr[2*i+1].smallest()) 935 ret = where_smallest(2*i); 936 else 937 ret = where_smallest(2*i+1); 938 act(i); 939 return ret; 940 } 941 942 ll move_power(int i, ll rem) { 943 assert(rem <= 0); 944 while(rem < 0) { 945 ll cur_value = cur_power[i] - rem; 946 cur_power[i] *= 42; 947 rem = cur_power[i] - cur_value; 948 } 949 return rem; 950 } 951 952 set<int> interesting; // the set of indices i that t[i] != t[i+1] (and maybe few others) 953 // all other indices have value INF in the tree 954 955 ll get_value(int i) { 956 assert(interesting.count(i)); 957 vector<int> w; 958 for(int x = (pot + i) / 2; x >= 1; x /= 2) 959 w.push_back(x); 960 reverse(w.begin(), w.end()); 961 for(int x : w) propagate(x); // top-down 962 return tr[pot+i].smallest(); 963 } 964 965 const int SET_TYPE = 10042; 966 const int INC_TYPE = 10043; 967 void set_or_inc(int i, ll val, const int type) { 968 vector<int> w; 969 for(int x = (pot + i) / 2; x >= 1; x /= 2) 970 w.push_back(x); 971 reverse(w.begin(), w.end()); 972 for(int x : w) propagate(x); // top-down 973 if(type == SET_TYPE) { 974 tr[pot+i].lazy = 0; 975 tr[pot+i].local = val; 976 } 977 else if(type == INC_TYPE) { 978 tr[pot+i].local += val; 979 } 980 else assert(false); 981 reverse(w.begin(), w.end()); 982 for(int x : w) act(x); // bottom-up 983 } 984 985 void re_insert(int i) { 986 int j = *interesting.lower_bound(i); 987 if(i == j) return; 988 cur_power[i] = cur_power[j]; 989 set_or_inc(i, get_value(j), SET_TYPE); 990 interesting.insert(i); 991 } 992 993 void init_value(int i, int val) { 994 cur_power[i] = 1; 995 ll how_much_remains = 1 - val; // how much remains to cur_power[i] 996 ll rem = move_power(i, how_much_remains); 997 set_or_inc(i, rem, SET_TYPE); 998 } 999 1000 int main() { 1001 int n, q; 1002 scanf("%d%d", &n, &q); 1003 for(int i = 0; i < 2 * pot; ++i) 1004 tr[i].local = INF; 1005 for(int i = 1; i <= n; ++i) { 1006 interesting.insert(i); // we don't mind that maybe t[i] = t[i+1] 1007 int val; 1008 scanf("%d", &val); 1009 init_value(i, val); 1010 } 1011 // queries 1012 while(q--) { 1013 int type; 1014 scanf("%d", &type); 1015 if(type == 1) { // print value 1016 int i; 1017 scanf("%d", &i); 1018 i = *interesting.lower_bound(i); 1019 printf("%lldn", cur_power[i] - get_value(i)); 1020 } 1021 else if(type == 2) { // set interval to x 1022 int low, high, val; 1023 scanf("%d%d%d", &low, &high, &val); 1024 // t[low] = t[low+1] = ... = t[high-1] = INF 1025 // t[high] = val 1026 if(low - 1 >= 1) 1027 re_insert(low - 1); 1028 interesting.insert(high); 1029 init_value(high, val); 1030 while(true) { 1031 auto it = interesting.lower_bound(low); 1032 assert(it != interesting.end()); 1033 int i = *it; 1034 assert(i <= high); 1035 if(i == high) break; // we only want [low, high-1] 1036 interesting.erase(it); 1037 set_or_inc(i, INF, SET_TYPE); 1038 } 1039 } 1040 else { // increase by x 1041 assert(type == 3); 1042 int low, high, val; 1043 scanf("%d%d%d", &low, &high, &val); 1044 if(low - 1 >= 1) 1045 re_insert(low - 1); 1046 re_insert(high); 1047 bool ok = false; 1048 while(!ok) { 1049 ok = true; 1050 change(low, high, -val); 1051 while(true) { 1052 int i = where_smallest(); 1053 ll rem = tr[pot+i].smallest(); 1054 assert(1 <= i && i <= n); 1055 if(rem > 0) break; 1056 if(rem == 0) { 1057 ok = false; 1058 break; 1059 } 1060 ll new_rem = move_power(i, rem); 1061 set_or_inc(i, new_rem, SET_TYPE); 1062 } 1063 } 1064 } 1065 } 1066 return 0; 1067 } 1068 ``` 1069 1070 **code2** 1071 1072 ``` 1073 #include <bits/stdc++.h> 1074 using namespace std; 1075 1076 int n, q; 1077 1078 vector <long long> poty; 1079 1080 int n1; 1081 1082 long long inf=(long long)1000000000*1000000000; 1083 1084 long long narz[1000007]; 1085 int czybom[1000007]; 1086 long long bom[1000007]; 1087 1088 long long maxd[1000007]; 1089 long long mind[1000007]; 1090 long long zos[1000007]; 1091 1092 int typ, p1, p2, p3; 1093 1094 inline int potenga(int v) 1095 { 1096 for (int i=1; 1; i<<=1) 1097 { 1098 if (i>=v) 1099 { 1100 return i; 1101 } 1102 } 1103 } 1104 1105 inline long long wie(long long v) 1106 { 1107 return poty[lower_bound(poty.begin(), poty.end(), v)-poty.begin()]; 1108 } 1109 1110 inline long long brak(long long v) 1111 { 1112 return wie(v)-v; 1113 } 1114 1115 inline void pusz(int v) 1116 { 1117 if (v>=n1) 1118 { 1119 czybom[v]=1; 1120 bom[v]+=narz[v]; 1121 narz[v]=0; 1122 maxd[v]=bom[v]; 1123 mind[v]=bom[v]; 1124 zos[v]=brak(bom[v]); 1125 return; 1126 } 1127 int cel1, cel2; 1128 cel1=(v<<1); 1129 cel2=(cel1^1); 1130 if (czybom[v]) 1131 { 1132 czybom[cel1]=1; 1133 bom[cel1]=bom[v]; 1134 narz[cel1]=0; 1135 1136 czybom[cel2]=1; 1137 bom[cel2]=bom[v]; 1138 narz[cel2]=0; 1139 1140 czybom[v]=0; 1141 bom[v]=0; 1142 } 1143 narz[cel1]+=narz[v]; 1144 narz[cel2]+=narz[v]; 1145 narz[v]=0; 1146 1147 mind[v]=inf; 1148 maxd[v]=-inf; 1149 zos[v]=inf; 1150 1151 for (int h=0; h<2; h++) 1152 { 1153 1154 if (czybom[cel1]) 1155 { 1156 bom[cel1]+=narz[cel1]; 1157 narz[cel1]=0; 1158 maxd[v]=max(maxd[v], bom[cel1]); 1159 mind[v]=min(mind[v], bom[cel1]); 1160 zos[v]=min(zos[v], brak(bom[cel1])); 1161 } 1162 else 1163 { 1164 maxd[v]=max(maxd[v], maxd[cel1]+narz[cel1]); 1165 mind[v]=min(mind[v], mind[cel1]+narz[cel1]); 1166 zos[v]=min(zos[v], zos[cel1]-narz[cel1]); 1167 } 1168 1169 swap(cel1, cel2); 1170 } 1171 } 1172 1173 void dod(int v, int a, int b, int graa, int grab, long long w) 1174 { 1175 if (a>=graa && b<=grab) 1176 { 1177 narz[v]+=w; 1178 return; 1179 } 1180 if (a>grab || b<graa) 1181 { 1182 return; 1183 } 1184 pusz(v); 1185 dod((v<<1), a, (a+b)>>1, graa, grab, w); 1186 dod((v<<1)^1, (a+b+2)>>1, b, graa, grab, w); 1187 pusz(v); 1188 } 1189 1190 void zmi(int v, int a, int b, int graa, int grab, long long w) 1191 { 1192 if (a>=graa && b<=grab) 1193 { 1194 narz[v]=0; 1195 czybom[v]=1; 1196 bom[v]=w; 1197 return; 1198 } 1199 if (a>grab || b<graa) 1200 { 1201 return; 1202 } 1203 pusz(v); 1204 zmi((v<<1), a, (a+b)>>1, graa, grab, w); 1205 zmi((v<<1)^1, (a+b+2)>>1, b, graa, grab, w); 1206 pusz(v); 1207 } 1208 1209 void popr(int v) 1210 { 1211 pusz(v); 1212 if (zos[v]>=0) 1213 { 1214 return; 1215 } 1216 if (mind[v]==maxd[v]) 1217 { 1218 czybom[v]=1; 1219 bom[v]=mind[v]; 1220 narz[v]=0; 1221 pusz(v); 1222 return; 1223 } 1224 popr((v<<1)); 1225 popr((v<<1)^1); 1226 pusz(v); 1227 } 1228 1229 long long wyn; 1230 1231 void czyt(int v, int a, int b, int cel) 1232 { 1233 if (a>cel || b<cel) 1234 return; 1235 pusz(v); 1236 if (a==b) 1237 { 1238 wyn=bom[v]; 1239 return; 1240 } 1241 czyt((v<<1), a, (a+b)>>1, cel); 1242 czyt((v<<1)^1, (a+b+2)>>1, b, cel); 1243 } 1244 1245 int main() 1246 { 1247 scanf("%d%d", &n, &q); 1248 n1=potenga(n+2); 1249 poty.push_back(1); 1250 for (int i=1; i<=11; i++) 1251 poty.push_back(poty.back()*42); 1252 zmi(1, 1, n1, 1, n1, 0); 1253 for (int i=1; i<=n; i++) 1254 { 1255 scanf("%d", &p1); 1256 zmi(1, 1, n1, i, i, p1); 1257 } 1258 while(q--) 1259 { 1260 scanf("%d", &typ); 1261 if (typ==1) 1262 { 1263 scanf("%d", &p1); 1264 czyt(1, 1, n1, p1); 1265 printf("%lldn", wyn); 1266 } 1267 if (typ==2) 1268 { 1269 scanf("%d%d%d", &p1, &p2, &p3); 1270 zmi(1, 1, n1, p1, p2, p3); 1271 } 1272 if (typ==3) 1273 { 1274 scanf("%d%d%d", &p1, &p2, &p3); 1275 dod(1, 1, n1, p1, p2, p3); 1276 while(1) 1277 { 1278 popr(1); 1279 if (zos[1]==0) 1280 { 1281 dod(1, 1, n1, p1, p2, p3); 1282 } 1283 else 1284 { 1285 break; 1286 } 1287 } 1288 } 1289 } 1290 return 0; 1291 } 1292 ```