codeforces-scrape

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

1272.md (6742B)


      1 Source: https://codeforces.com/blog/entry/72132
      2 
      3 All ideas except the problem C belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). The author of C is [Rox](/profile/Rox "Candidate Master Rox").
      4 
      5 Special thanks to [_overrated_](/profile/_overrated_ "Master _overrated_") for the invaluable help with the round preparation!
      6 
      7 [1272A - Three Friends](/contest/1272/problem/A "Codeforces Round 605 (Div. 3)")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int calc(int a, int b, int c) {
     21 	return abs(a - b) + abs(a - c) + abs(b - c);
     22 }
     23 
     24 int main() {
     25 #ifdef _DEBUG
     26 	freopen("input.txt", "r", stdin);
     27 //	freopen("output.txt", "w", stdout);
     28 #endif
     29 	
     30 	int q;
     31 	cin >> q;
     32 	for (int i = 0; i < q; ++i) {
     33 		int a, b, c;
     34 		cin >> a >> b >> c;
     35 		int ans = calc(a, b, c);
     36 		for (int da = -1; da <= 1; ++da) {
     37 			for (int db = -1; db <= 1; ++db) {
     38 				for (int dc = -1; dc <= 1; ++dc) {
     39 					int na = a + da;
     40 					int nb = b + db;
     41 					int nc = c + dc;
     42 					ans = min(ans, calc(na, nb, nc));
     43 				}
     44 			}
     45 		}
     46 		cout << ans << endl;
     47 	}
     48 	
     49 	return 0;
     50 }
     51 ```
     52 
     53 [1272B - Snow Walking Robot](/contest/1272/problem/B "Codeforces Round 605 (Div. 3)")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63 
     64 using namespace std;
     65 
     66 const string MOVES = "LRUD";
     67 
     68 int main() {
     69 #ifdef _DEBUG
     70 	freopen("input.txt", "r", stdin);
     71 //	freopen("output.txt", "w", stdout);
     72 #endif
     73 	
     74 	int q;
     75 	cin >> q;
     76 	for (int i = 0; i < q; ++i) {
     77 		string s;
     78 		cin >> s;
     79 		map<char, int> cnt;
     80 		for (auto c : MOVES) cnt[c] = 0;
     81 		for (auto c : s) ++cnt[c];
     82 		int v = min(cnt['U'], cnt['D']);
     83 		int h = min(cnt['L'], cnt['R']);
     84 		if (min(v, h) == 0) {
     85 			if (v == 0) {
     86 				h = min(h, 1);
     87 				cout << 2 * h << endl << string(h, 'L') + string(h, 'R') << endl;
     88 			} else {
     89 				v = min(v, 1);
     90 				cout << 2 * v << endl << string(v, 'U') + string(v, 'D') << endl;
     91 			}
     92 		} else {
     93 			string res;
     94 			res += string(h, 'L');
     95 			res += string(v, 'U');
     96 			res += string(h, 'R');
     97 			res += string(v, 'D');
     98 			cout << res.size() << endl << res << endl;
     99 		}
    100 	}
    101 	
    102 	return 0;
    103 }
    104 ```
    105 
    106 [1272C - Yet Another Broken Keyboard](/contest/1272/problem/C "Codeforces Round 605 (Div. 3)")
    107 
    108 **Tutorial**
    109 
    110 Tutorial is loading...
    111 
    112 **Solution**
    113 
    114 ```
    115 #include <bits/stdc++.h>
    116 
    117 using namespace std;
    118 
    119 int main() {
    120 #ifdef _DEBUG
    121 	freopen("input.txt", "r", stdin);
    122 //	freopen("output.txt", "w", stdout);
    123 #endif
    124 	
    125 	int n, k;
    126 	cin >> n >> k;
    127 	string s;
    128 	cin >> s;
    129 	set<char> st;
    130 	for (int i = 0; i < k; ++i) {
    131 		char c;
    132 		cin >> c;
    133 		st.insert(c);
    134 	}
    135 	
    136 	long long ans = 0;
    137 	for (int i = 0; i < n; ++i) {
    138 		int j = i;
    139 		while (j < n && st.count(s[j])) ++j;
    140 		int len = j - i;
    141 		ans += len * 1ll * (len + 1) / 2;
    142 		i = j;
    143 	}
    144 	cout << ans << endl;
    145 	
    146 	return 0;
    147 }
    148 ```
    149 
    150 [1272D - Remove One Element](/contest/1272/problem/D "Codeforces Round 605 (Div. 3)")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 int main() {
    164 #ifdef _DEBUG
    165 	freopen("input.txt", "r", stdin);
    166 //	freopen("output.txt", "w", stdout);
    167 #endif
    168 	
    169 	int n;
    170 	cin >> n;
    171 	vector<int> a(n);
    172 	for (int i = 0; i < n; ++i) {
    173 		cin >> a[i];
    174 	}
    175 	int ans = 1;
    176 	
    177 	vector<int> rg(n, 1);
    178 	for (int i = n - 2; i >= 0; --i) {
    179 		if (a[i + 1] > a[i]) rg[i] = rg[i + 1] + 1;
    180 		ans = max(ans, rg[i]);
    181 	}
    182 	
    183 	vector<int> lf(n, 1);
    184 	for (int i = 1; i < n; ++i) {
    185 		if (a[i - 1] < a[i]) lf[i] = lf[i - 1] + 1;
    186 		ans = max(ans, lf[i]);
    187 	}
    188 	
    189 	for (int i = 0; i < n - 2; ++i) {
    190 		if (a[i] < a[i + 2]) ans = max(ans, lf[i] + rg[i + 2]);
    191 	}
    192 	
    193 	cout << ans << endl;
    194 	
    195 	return 0;
    196 }
    197 ```
    198 
    199 [1272E - Nearest Opposite Parity](/contest/1272/problem/E "Codeforces Round 605 (Div. 3)")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 
    210 using namespace std;
    211 
    212 const int INF = 1e9;
    213 
    214 int n;
    215 vector<int> a;
    216 vector<int> ans;
    217 vector<vector<int>> g;
    218 
    219 void bfs(const vector<int> &start, const vector<int> &end) {
    220 	vector<int> d(n, INF);
    221 	queue<int> q;
    222 	for (auto v : start) {
    223 		d[v] = 0;
    224 		q.push(v);
    225 	}
    226 	while (!q.empty()) {
    227 		int v = q.front();
    228 		q.pop();
    229 		for (auto to : g[v]) {
    230 			if (d[to] == INF) {
    231 				d[to] = d[v] + 1;
    232 				q.push(to);
    233 			}
    234 		}
    235 	}
    236 	for (auto v : end) {
    237 		if (d[v] != INF) {
    238 			ans[v] = d[v];
    239 		}
    240 	}
    241 }
    242 
    243 int main() {
    244 #ifdef _DEBUG
    245 	freopen("input.txt", "r", stdin);
    246 //	freopen("output.txt", "w", stdout);
    247 #endif
    248 	
    249 	cin >> n;
    250 	a = vector<int>(n);
    251 	g = vector<vector<int>>(n);
    252 	vector<int> even, odd;
    253 	for (int i = 0; i < n; ++i) {
    254 		cin >> a[i];
    255 		if (a[i] & 1) odd.push_back(i);
    256 		else even.push_back(i);
    257 	}
    258 	for (int i = 0; i < n; ++i) {
    259 		int lf = i - a[i];
    260 		int rg = i + a[i];
    261 		if (0 <= lf) g[lf].push_back(i);
    262 		if (rg < n) g[rg].push_back(i);
    263 	}
    264 	
    265 	ans = vector<int>(n, -1);
    266 	bfs(odd, even);
    267 	bfs(even, odd);
    268 	for (auto it : ans) cout << it << " ";
    269 	cout << endl;
    270 	
    271 	return 0;
    272 }
    273 ```
    274 
    275 [1272F - Two Bracket Sequences](/contest/1272/problem/F "Codeforces Round 605 (Div. 3)")
    276 
    277 **Tutorial**
    278 
    279 Tutorial is loading...
    280 
    281 **Solution**
    282 
    283 ```
    284 #include <bits/stdc++.h>
    285 
    286 using namespace std;
    287 
    288 const int N = 202;
    289 const int INF = 1e9;
    290 
    291 int dp[N][N][2 * N];
    292 pair<pair<int, int>, pair<int, char>> p[N][N][2 * N];
    293 
    294 int main() {
    295 #ifdef _DEBUG
    296 	freopen("input.txt", "r", stdin);
    297 //	freopen("output.txt", "w", stdout);
    298 #endif
    299 	
    300 	string s, t;
    301 	cin >> s >> t;
    302 	int n = s.size(), m = t.size();
    303 	
    304 	for (int i = 0; i <= n; ++i) {
    305 		for (int j = 0; j <= m; ++j) {
    306 			for (int bal = 0; bal < 2 * N; ++bal) {
    307 				dp[i][j][bal] = INF;
    308 			}
    309 		}
    310 	}
    311 	
    312 	dp[0][0][0] = 0;
    313 	for (int i = 0; i <= n; ++i) {
    314 		for (int j = 0; j <= m; ++j) {
    315 			for (int bal = 0; bal < 2 * N; ++bal) {
    316 				if (dp[i][j][bal] == INF) continue;
    317 				
    318 				int nxti = i + (i < n && s[i] == '(');
    319 				int nxtj = j + (j < m && t[j] == '(');
    320 				if (bal + 1 < 2 * N && dp[nxti][nxtj][bal + 1] > dp[i][j][bal] + 1) {
    321 					dp[nxti][nxtj][bal + 1] = dp[i][j][bal] + 1;
    322 					p[nxti][nxtj][bal + 1] = make_pair(make_pair(i, j), make_pair(bal, '('));
    323 				}
    324 				
    325 				nxti = i + (i < n && s[i] == ')');
    326 				nxtj = j + (j < m && t[j] == ')');
    327 				if (bal > 0 && dp[nxti][nxtj][bal - 1] > dp[i][j][bal] + 1) {
    328 					dp[nxti][nxtj][bal - 1] = dp[i][j][bal] + 1;
    329 					p[nxti][nxtj][bal - 1] = make_pair(make_pair(i, j), make_pair(bal, ')'));
    330 				}
    331 			}
    332 		}
    333 	}
    334 	
    335 	int ci = n, cj = m, cbal = 0;
    336 	for (int bal = 0; bal < 2 * N; ++bal) {
    337 		if (dp[n][m][bal] + bal < dp[n][m][cbal] + cbal) {
    338 			cbal = bal;
    339 		}
    340 	}
    341 	string res = string(cbal, ')');
    342 	while (ci > 0 || cj > 0 || cbal != 0) {
    343 		int nci = p[ci][cj][cbal].first.first;
    344 		int ncj = p[ci][cj][cbal].first.second;
    345 		int ncbal = p[ci][cj][cbal].second.first;
    346 		res += p[ci][cj][cbal].second.second;
    347 		ci = nci;
    348 		cj = ncj;
    349 		cbal = ncbal;
    350 	}
    351 	reverse(res.begin(), res.end());
    352 	cout << res << endl;
    353 	
    354 	return 0;
    355 }
    356 ```