codeforces-scrape

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

1157.md (8935B)


      1 Source: https://codeforces.com/blog/entry/66737
      2 
      3 [1157A - Reachable Numbers](/contest/1157/problem/A "Codeforces Round 555 (Div. 3)")
      4 
      5 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def f(x):
     15 	x += 1
     16 	while(x % 10 == 0):
     17 		x //= 10
     18 	return x
     19 
     20 a = set()
     21 n = int(input())
     22 
     23 while(not(n in a)):
     24 	a.add(n)
     25 	n = f(n)
     26 
     27 print(len(a))
     28 ```
     29 
     30 [1157B - Long Number](/contest/1157/problem/B "Codeforces Round 555 (Div. 3)")
     31 
     32 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution**
     39 
     40 ```
     41 #include<bits/stdc++.h>
     42 
     43 using namespace std;
     44 
     45 int f[10];
     46 string s;
     47 
     48 int main()
     49 {
     50 	int n;
     51 	cin >> n;
     52 	cin >> s;
     53 	for(int i = 1; i <= 9; i++)
     54 		cin >> f[i];
     55 	vector<int> diff;
     56 	for(int i = 0; i < n; i++)
     57 		diff.push_back(f[s[i] - '0'] - (s[i] - '0'));
     58 	for(int i = 0; i < n; i++)
     59 		if(diff[i] > 0)
     60 		{
     61 			while(i < n && diff[i] >= 0)
     62 			{
     63 				s[i] = char(f[s[i] - '0'] + '0');
     64 				i++;
     65 			}
     66 			break;
     67 		}
     68 	cout << s << endl;
     69 }
     70 ```
     71 
     72 [1157C1 - Increasing Subsequence (easy version)](/contest/1157/problem/C1 "Codeforces Round 555 (Div. 3)")
     73 
     74 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 
     85 using namespace std;
     86 
     87 int main() {
     88 #ifdef _DEBUG
     89 	freopen("input.txt", "r", stdin);
     90 //	freopen("output.txt", "w", stdout);
     91 #endif
     92 	
     93 	int n;
     94 	cin >> n;
     95 	vector<int> a(n);
     96 	for (int i = 0; i < n; ++i) {
     97 		cin >> a[i];
     98 	}
     99 	
    100 	string res;
    101 	int l = 0, r = n - 1;
    102 	int lst = 0;
    103 	while (l <= r) {
    104 		vector<pair<int, char>> cur;
    105 		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
    106 		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
    107 		sort(cur.begin(), cur.end());
    108 		if (int(cur.size()) == 2) {
    109 			cur.pop_back();
    110 		}
    111 		if (int(cur.size()) == 1) {
    112 			if (cur[0].second == 'L') {
    113 				res += 'L';
    114 				lst = a[l];
    115 				++l;
    116 			} else {
    117 				res += 'R';
    118 				lst = a[r];
    119 				--r;
    120 			}
    121 		} else {
    122 			break;
    123 		}
    124 	}
    125 	
    126 	cout << res.size() << endl << res << endl;
    127 	
    128 	return 0;
    129 }
    130 ```
    131 
    132 [1157C2 - Increasing Subsequence (hard version)](/contest/1157/problem/C2 "Codeforces Round 555 (Div. 3)")
    133 
    134 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 
    145 using namespace std;
    146 
    147 int main() {
    148 #ifdef _DEBUG
    149 	freopen("input.txt", "r", stdin);
    150 //	freopen("output.txt", "w", stdout);
    151 #endif
    152 	
    153 	int n;
    154 	cin >> n;
    155 	vector<int> a(n);
    156 	for (int i = 0; i < n; ++i) {
    157 		cin >> a[i];
    158 	}
    159 	
    160 	string res;
    161 	int l = 0, r = n - 1;
    162 	int lst = 0;
    163 	while (l <= r) {
    164 		vector<pair<int, char>> cur;
    165 		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
    166 		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
    167 		sort(cur.begin(), cur.end());
    168 		if (int(cur.size()) == 2 && cur[0].first != cur[1].first) {
    169 			cur.pop_back();
    170 		}
    171 		if (int(cur.size()) == 1) {
    172 			if (cur[0].second == 'L') {
    173 				res += 'L';
    174 				lst = a[l];
    175 				++l;
    176 			} else {
    177 				res += 'R';
    178 				lst = a[r];
    179 				--r;
    180 			}
    181 		} else if (int(cur.size()) == 2) {
    182 			int cl = 1, cr = 1;
    183 			while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl;
    184 			while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr;
    185 			if (cl > cr) {
    186 				res += string(cl, 'L');
    187 			} else {
    188 				res += string(cr, 'R');
    189 			}
    190 			break;
    191 		} else {
    192 			break;
    193 		}
    194 	}
    195 	
    196 	cout << res.size() << endl << res << endl;
    197 	
    198 	return 0;
    199 }
    200 ```
    201 
    202 [1157D - N Problems During K Days](/contest/1157/problem/D "Codeforces Round 555 (Div. 3)")
    203 
    204 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    205 
    206 **Tutorial**
    207 
    208 Tutorial is loading...
    209 
    210 **Solution**
    211 
    212 ```
    213 #include <bits/stdc++.h>
    214 
    215 using namespace std;
    216 
    217 int main() {
    218 #ifdef _DEBUG
    219 	freopen("input.txt", "r", stdin);
    220 //	freopen("output.txt", "w", stdout);
    221 #endif
    222 	
    223 	int n, k;
    224 	cin >> n >> k;
    225 	if (n < k * 1ll * (k + 1) / 2) {
    226 		cout << "NO" << endl;
    227 		return 0;
    228 	}
    229 	
    230 	int nn = n - k * (k + 1) / 2;
    231 	vector<int> a(k);
    232 	for (int i = 0; i < k; ++i) {
    233 		a[i] = i + 1 + (nn / k) + (i >= k - nn % k);
    234 	}
    235 	
    236 	if (nn != k - 1) {
    237 		cout << "YES" << endl;
    238 		for (int i = 0; i < k; ++i) cout << a[i] << " ";
    239 		cout << endl;
    240 	} else {
    241 		if (k > 3) {
    242 			--a[1];
    243 			++a[k - 1];
    244 		}
    245 		if (k == 2 || k == 3) {
    246 			cout << "NO" << endl;
    247 		} else {
    248 			cout << "YES" << endl;
    249 			for (int i = 0; i < k; ++i) cout << a[i] << " ";
    250 			cout << endl;
    251 		}
    252 	}
    253 	
    254 	return 0;
    255 }
    256 ```
    257 
    258 [1157E - Minimum Array](/contest/1157/problem/E "Codeforces Round 555 (Div. 3)")
    259 
    260 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    261 
    262 **Tutorial**
    263 
    264 Tutorial is loading...
    265 
    266 **Solution**
    267 
    268 ```
    269 #include <bits/stdc++.h>
    270 
    271 using namespace std;
    272 
    273 int main() {
    274 #ifdef _DEBUG
    275 	freopen("input.txt", "r", stdin);
    276 //	freopen("output.txt", "w", stdout);
    277 #endif
    278 	
    279 	int n;
    280 	cin >> n;
    281 	vector<int> a(n);
    282 	multiset<int> b;
    283 	for (int i = 0; i < n; ++i) {
    284 		cin >> a[i];
    285 	}
    286 	for (int i = 0; i < n; ++i) {
    287 		int x;
    288 		cin >> x;
    289 		b.insert(x);
    290 	}
    291 	
    292 	for (int i = 0; i < n; ++i) {
    293 		auto it = b.lower_bound(n - a[i]);
    294 		if (it == b.end()) it = b.begin();
    295 		cout << (a[i] + *it) % n << " ";
    296 		b.erase(it);
    297 	}
    298 	cout << endl;
    299 	
    300 	return 0;
    301 }
    302 ```
    303 
    304 [1157F - Maximum Balanced Circle](/contest/1157/problem/F "Codeforces Round 555 (Div. 3)")
    305 
    306 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    307 
    308 **Tutorial**
    309 
    310 Tutorial is loading...
    311 
    312 **Solution**
    313 
    314 ```
    315 #include <bits/stdc++.h>
    316 
    317 using namespace std;
    318 
    319 int main() {
    320 #ifdef _DEBUG
    321 	freopen("input.txt", "r", stdin);
    322 //	freopen("output.txt", "w", stdout);
    323 #endif
    324 	
    325 	int n;
    326 	cin >> n;
    327 	vector<int> a(n);
    328 	vector<int> cnt(200 * 1000 + 1);
    329 	for (int i = 0; i < n; ++i) {
    330 		cin >> a[i];
    331 		++cnt[a[i]];
    332 	}
    333 	
    334 	sort(a.begin(), a.end());
    335 	a.resize(unique(a.begin(), a.end()) - a.begin());
    336 	
    337 	int l = 0, r = 0;
    338 	int ans = cnt[a[0]];
    339 	for (int i = 0; i < int(a.size()); ++i) {
    340 		int j = i + 1;
    341 		int sum = cnt[a[i]];
    342 		while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) {
    343 			sum += cnt[a[j]];
    344 			++j;
    345 		}
    346 		int cr = j - 1;
    347 		if (j < n && a[j] - a[j - 1] == 1) {
    348 			sum += cnt[a[j]];
    349 			cr = j;
    350 		}
    351 		if (ans < sum) {
    352 			ans = sum;
    353 			l = i;
    354 			r = cr;
    355 		}
    356 		i = j - 1;
    357 	}
    358 	
    359 	cout << ans << endl;
    360 	for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " ";
    361 	for (int i = l + 1; i < r; ++i) {
    362 		for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " ";
    363 	}
    364 	for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " ";
    365 	for (int i = r - 1; i > l; --i) cout << a[i] << " ";
    366 	cout << endl;
    367 	
    368 	return 0;
    369 }
    370 ```
    371 
    372 [1157G - Inverse of Rows and Columns](/contest/1157/problem/G "Codeforces Round 555 (Div. 3)")
    373 
    374 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh")
    375 
    376 [This](https://codeforces.com/blog/entry/66703?#comment-508037) is the comment about the quadratic solution. Thank you so much for mentioning this fact, [STommydx](/profile/STommydx "Candidate Master STommydx")!
    377 
    378 **Tutorial**
    379 
    380 Tutorial is loading...
    381 
    382 **Solution**
    383 
    384 ```
    385 #include <bits/stdc++.h>
    386 
    387 using namespace std;
    388 
    389 int n, m;
    390 
    391 void invRow(vector<vector<int>> &a, int idx) {
    392 	for (int pos = 0; pos < m; ++pos) {
    393 		a[idx][pos] ^= 1;
    394 	}
    395 }
    396 
    397 void invCol(vector<vector<int>> &a, int idx) {
    398 	for (int pos = 0; pos < n; ++pos) {
    399 		a[pos][idx] ^= 1;
    400 	}
    401 }
    402 
    403 int main() {
    404 #ifdef _DEBUG
    405 	freopen("input.txt", "r", stdin);
    406 //	freopen("output.txt", "w", stdout);
    407 #endif
    408 	
    409 	cin >> n >> m;
    410 	vector<vector<int>> a(n, vector<int>(m));
    411 	for (int i = 0; i < n; ++i) {
    412 		for (int j = 0; j < m; ++j) {
    413 			cin >> a[i][j];
    414 		}
    415 	}
    416 	
    417 	for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
    418 		string r(n, '0');
    419 		string c(m, '0');
    420 		vector<vector<int>> b = a;
    421 		for (int j = 0; j < m; ++j) {
    422 			if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) {
    423 				invCol(b, j);
    424 				c[j] = '1';
    425 			}
    426 		}
    427 		bool ok = true;
    428 		if (cnt0 < m) {
    429 			for (int i = 1; i < n; ++i) {
    430 				int sum = accumulate(b[i].begin(), b[i].end(), 0);
    431 				if (sum != 0 && sum != m) {
    432 					ok = false;
    433 				} else if (sum == 0) {
    434 					invRow(b, i);
    435 					r[i] = '1';
    436 				}
    437 			}
    438 		} else {
    439 			int idx = -1;
    440 			for (int i = 1; i < n; ++i) {
    441 				int sum = accumulate(b[i].begin(), b[i].end(), 0);
    442 				if (sum != 0 && sum != m) {
    443 					if (idx != -1) ok = false;
    444 					else idx = i;
    445 				}
    446 			}
    447 			if (idx == -1) {
    448 				for (int i = 1; i < n; ++i) {
    449 					int sum = accumulate(b[i].begin(), b[i].end(), 0);
    450 					if (sum == 0) {
    451 						invRow(b, i);
    452 						r[i] = '1';
    453 					}
    454 				}
    455 			} else {
    456 				for (int i = 1; i < idx; ++i) {
    457 					int sum = accumulate(b[i].begin(), b[i].end(), 0);
    458 					if (sum == m) {
    459 						invRow(b, i);
    460 						r[i] = '1';
    461 					}
    462 				}
    463 				if (b[idx][0] == 1) {
    464 					invRow(b, idx);
    465 					r[idx] = '1';
    466 				}
    467 				for (int j = 1; j < m; ++j) {
    468 					if (b[idx][j] < b[idx][j - 1]) {
    469 						ok = false;
    470 					}
    471 				}
    472 				for (int i = idx + 1; i < n; ++i) {
    473 					int sum = accumulate(b[i].begin(), b[i].end(), 0);
    474 					if (sum == 0) {
    475 						invRow(b, i);
    476 						r[i] = '1';
    477 					}
    478 				}
    479 			}
    480 		}
    481 		if (ok) {
    482 			cout << "YES" << endl << r << endl << c << endl;
    483 			return 0;
    484 		}
    485 	}
    486 	
    487 	cout << "NO" << endl;
    488 	
    489 	return 0;
    490 }
    491 ```