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 ```