1675.md (8646B)
1 Source: https://codeforces.com/blog/entry/102550 2 3 [1675A - Food for Animals](/contest/1675/problem/A "Codeforces Round 787 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 20 int main() { 21 int t; 22 cin >> t; 23 forn(tt, t) { 24 int a, b, c, x, y; 25 cin >> a >> b >> c >> x >> y; 26 int ax = min(a, x); 27 int by = min(b, y); 28 a -= ax; 29 x -= ax; 30 b -= by; 31 y -= by; 32 if (c >= x + y) 33 cout << "YES" << endl; 34 else 35 cout << "NO" << endl; 36 } 37 } 38 ``` 39 40 [1675B - Make It Increasing](/contest/1675/problem/B "Codeforces Round 787 (Div. 3)") 41 42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution** 49 50 ``` 51 #include<bits/stdc++.h> 52 using namespace std; 53 void solve(){ 54 int n; 55 cin >> n; 56 vector<int>a(n); 57 for(auto &i : a) cin >> i; 58 int ans = 0; 59 for(int i = n - 2; i >= 0; i--){ 60 while(a[i] >= a[i + 1] && a[i] > 0){ 61 a[i] /= 2; 62 ans++; 63 } 64 if(a[i] == a[i+1]){ 65 cout << -1 << '\n'; 66 return; 67 } 68 } 69 cout << ans << '\n'; 70 } 71 int main(){ 72 int t; 73 cin >> t; 74 while(t--){ 75 solve(); 76 } 77 } 78 ``` 79 80 [1675C - Detective Task](/contest/1675/problem/C "Codeforces Round 787 (Div. 3)") 81 82 Idea: [Gol_D](/profile/Gol_D "Candidate Master Gol_D") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution** 89 90 ``` 91 #include <bits/stdc++.h> 92 93 using namespace std; 94 95 #define forn(i, n) for (int i = 0; i < int(n); i++) 96 97 int main() { 98 int t; 99 cin >> t; 100 forn(tt, t) { 101 string s; 102 cin >> s; 103 int n = s.length(); 104 vector<bool> a(n + 1); 105 a[0] = true; 106 forn(i, n) 107 a[i + 1] = a[i] && (s[i] == '1' || s[i] == '?'); 108 vector<bool> b(n + 1); 109 b[0] = true; 110 for (int i = n - 1; i >= 0; i--) 111 b[n - i] = b[n - i - 1] && (s[i] == '0' || s[i] == '?'); 112 int result = 0; 113 forn(i, n) 114 if (a[i] && b[n - i - 1]) 115 result++; 116 cout << result << endl; 117 } 118 } 119 ``` 120 121 [1675D - Vertical Paths](/contest/1675/problem/D "Codeforces Round 787 (Div. 3)") 122 123 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 124 125 **Tutorial** 126 127 Tutorial is loading... 128 129 **Solution** 130 131 ``` 132 #include<bits/stdc++.h> 133 using namespace std; 134 135 void solve(){ 136 int n; 137 cin >> n; 138 vector<int>b(n + 1); 139 vector<bool>leaf(n + 1, true); 140 for(int i = 1; i <= n; i++) { 141 cin >> b[i]; 142 leaf[b[i]] = false; 143 } 144 145 if(n == 1){ 146 cout << "1\n1\n1\n\n"; 147 return; 148 } 149 150 vector<int>paths[n + 1]; 151 vector<bool>used(n + 1, false); 152 int color = 0; 153 154 for(int i = 1; i <= n; i++){ 155 if(!leaf[i]) continue; 156 used[i] = true; 157 paths[color].emplace_back(i); 158 159 int v = i; 160 while (b[v] != v && !used[b[v]]){ 161 v = b[v]; 162 used[v] = true; 163 paths[color].emplace_back(v); 164 } 165 color++; 166 } 167 168 cout << color << '\n'; 169 for(auto &path : paths){ 170 if(path.empty()) continue; 171 cout << (int)path.size() << '\n'; 172 reverse(path.begin(), path.end()); 173 for(auto &v: path) cout << v << ' '; 174 cout << '\n'; 175 } 176 cout << '\n'; 177 } 178 int main(){ 179 int t; 180 cin >> t; 181 while(t--){ 182 solve(); 183 } 184 } 185 ``` 186 187 [1675E - Replace With the Previous, Minimize](/contest/1675/problem/E "Codeforces Round 787 (Div. 3)") 188 189 Idea: [myav](/profile/myav "Pupil myav") 190 191 **Tutorial** 192 193 Tutorial is loading... 194 195 **Solution** 196 197 ``` 198 #include <bits/stdc++.h> 199 200 using namespace std; 201 202 #define forn(i, n) for (int i = 0; i < int(n); i++) 203 #define sz(v) (int)v.size() 204 #define all(v) v.begin(),v.end() 205 #define eb emplace_back 206 207 template <class T> bool ckmax(T &a, T b) {return a<b ? a=b, true : false;} 208 209 void solve() { 210 int n,k; cin >> n >> k; 211 string s; cin >> s; 212 213 char mn = 'a'; 214 for (int i = 0; i < n; i++) if(s[i] > mn) { 215 if (s[i] - 'a' > k) { 216 k -= mn - 'a'; 217 int to = s[i] - k; 218 for (char c = s[i]; c > to; c--) { 219 for (char &e:s) if (e == c) { 220 e = char(c-1); 221 } 222 } 223 break; 224 } else ckmax(mn, s[i]); 225 } 226 for (char &e:s) if (e <= mn) { 227 e = 'a'; 228 } 229 cout << s << endl; 230 } 231 232 int main() { 233 int t; 234 cin >> t; 235 236 forn(tt, t) { 237 solve(); 238 } 239 } 240 ``` 241 242 [1675F - Vlad and Unfinished Business](/contest/1675/problem/F "Codeforces Round 787 (Div. 3)") 243 244 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 245 246 **Tutorial** 247 248 Tutorial is loading... 249 250 **Solution** 251 252 ``` 253 #include <bits/stdc++.h> 254 255 using namespace std; 256 257 //#define int long long 258 #define ll long long 259 //#define double long double 260 #define all(a) a.begin(), a.end() 261 #define rall(a) a.rbegin(), a.rend() 262 263 const int MOD = 1e9 + 7; 264 const int maxN = 5e3 + 1; 265 const int INF = 2e9; 266 const int MB = 20; 267 268 vector<vector<int>> g; 269 vector<bool> todo, good; 270 271 void dfs(int v, int p = -1) { 272 for (int u : g[v]) { 273 if (u != p) { 274 dfs(u, v); 275 if (todo[u]) { 276 todo[v] = true; 277 } 278 if (good[u]) { 279 good[v] = true; 280 } 281 } 282 } 283 } 284 285 void solve() { 286 int n, k; 287 cin >> n >> k; 288 g.clear(); 289 g.resize(n); 290 int x, y; 291 cin >> x >> y; 292 --x; 293 --y; 294 todo.resize(n); 295 fill(all(todo), false); 296 good.resize(n); 297 fill(all(good), false); 298 for (int i = 0; i < k; ++i) { 299 int v; 300 cin >> v; 301 --v; 302 todo[v] = true; 303 } 304 good[y] = true; 305 for (int i = 0; i < n - 1; ++i) { 306 int v, u; 307 cin >> v >> u; 308 --v; 309 --u; 310 g[v].push_back(u); 311 g[u].push_back(v); 312 } 313 dfs(x); 314 int ans = 0; 315 for (int i = 0; i < n; ++i) { 316 if (i == x) { 317 continue; 318 } 319 if (good[i]) { 320 ++ans; 321 } else if (todo[i]) { 322 ans += 2; 323 } 324 } 325 cout << ans << '\n'; 326 } 327 328 signed main() { 329 ios_base::sync_with_stdio(false); 330 cin.tie(0); 331 cout.tie(0); 332 // srand(time(0)); 333 int t = 1; 334 cin >> t; 335 while (t--) solve(); 336 } 337 ``` 338 339 [1675G - Sorting Pancakes](/contest/1675/problem/G "Codeforces Round 787 (Div. 3)") 340 341 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 342 343 **Tutorial** 344 345 Tutorial is loading... 346 347 **Solution** 348 349 ``` 350 #include <bits/stdc++.h> 351 352 //#define int long long 353 #define mp make_pair 354 #define x first 355 #define y second 356 #define all(a) (a).begin(), (a).end() 357 #define rall(a) (a).rbegin(), (a).rend() 358 359 typedef long double ld; 360 typedef long long ll; 361 362 using namespace std; 363 364 mt19937 rnd(143); 365 366 const ll inf = 1e9 + 7; 367 const ll M = 998'244'353; 368 const ld pi = atan2(0, -1); 369 const ld eps = 1e-4; 370 371 void solve(int test_case) { 372 int n, m; 373 cin >> n >> m; 374 vector<int> a(n), pancakes(1); 375 for(int &e: a) cin >> e; 376 for(int i = 0; i < n; ++i){ 377 for(int j = 0; j < a[i]; ++j){ 378 pancakes.emplace_back(i); 379 int c = pancakes.size(); 380 pancakes[c - 1] += pancakes[c - 2]; 381 } 382 if(i > 0) a[i] += a[i - 1]; 383 } 384 vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1, inf))); 385 for(int j = 0; j <= m; j++){ 386 if(a[0] >= j) dp[0][j][j] = a[0] - j;//moved right 387 else dp[0][j][j] = pancakes[j];//moved from right 388 } 389 for(int j = m - 1; j >= 0; --j){ 390 for(int k = j; k <= m; ++k){ 391 dp[0][j][k] = min(dp[0][j][k], dp[0][j + 1][k]); 392 } 393 } 394 for(int i = 1; i < n; ++i){ 395 for(int j = 0; j <= m; ++j){ 396 for(int k = j; k <= m; ++k){ 397 int add = 0; 398 if(a[i] >= k) add = a[i] - k;//moved to i + 1 399 else { 400 int lend = min(j, k - a[i]); 401 add = pancakes[k] - pancakes[k - lend] - i * (lend);//moved from greater i 402 } 403 dp[i][j][k] = dp[i - 1][j][k - j] + add; 404 } 405 } 406 407 for(int j = m - 1; j >= 0; --j){ 408 for(int k = (i + 1) * j; k <= m; ++k){ 409 dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k]); 410 } 411 } 412 } 413 cout << dp[n-1][0][m]; 414 } 415 416 bool multi = false; 417 418 signed main() { 419 int t = 1; 420 if (multi) { 421 cin >> t; 422 } 423 for (int i = 1; i <= t; ++i) { 424 solve(i); 425 cout << "\n"; 426 } 427 return 0; 428 } 429 ```