codeforces-scrape

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

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 ![](https://espresso.codeforces.com/29cd41d3b7a01103f80f7f1a061fdf146ffa49b1.png) 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 ```