1650.md (9964B)
1 Source: https://codeforces.com/blog/entry/100712 2 3 [1650A - Deletions of Two Adjacent Letters](/contest/1650/problem/A "Codeforces Round 776 (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 string s, t; 25 cin >> s >> t; 26 bool yes = false; 27 forn(i, s.length()) 28 if (s[i] == t[0] && i % 2 == 0) 29 yes = true; 30 cout << (yes ? "YES" : "NO") << endl; 31 } 32 } 33 ``` 34 35 [1650B - DIV + MOD](/contest/1650/problem/B "Codeforces Round 776 (Div. 3)") 36 37 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 //#define int long long 49 #define mp make_pair 50 #define x first 51 #define y second 52 #define all(a) (a).begin(), (a).end() 53 #define rall(a) (a).rbegin(), (a).rend() 54 55 #pragma GCC optimize("Ofast") 56 #pragma GCC optimize("no-stack-protector") 57 #pragma GCC optimize("unroll-loops") 58 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 59 #pragma GCC optimize("fast-math") 60 61 typedef long double ld; 62 typedef long long ll; 63 64 using namespace std; 65 66 mt19937 rnd(143); 67 68 const ll inf = 1e9; 69 const ll M = 1e9; 70 const ld pi = atan2(0, -1); 71 const ld eps = 1e-4; 72 73 void solve() { 74 int l, r, x; 75 cin >> l >> r >> x; 76 int ans = r / x + r % x; 77 int m = r / x * x - 1; 78 if(m >= l)ans = max(ans, m / x + m % x); 79 cout << ans; 80 } 81 82 bool multi = true; 83 84 signed main() { 85 //freopen("in.txt", "r", stdin); 86 //freopen("in.txt", "w", stdout); 87 int t = 1; 88 if (multi) { 89 cin >> t; 90 } 91 for (; t != 0; --t) { 92 solve(); 93 cout << "\n"; 94 } 95 return 0; 96 } 97 ``` 98 99 [1650C - Weight of the System of Nested Segments](/contest/1650/problem/C "Codeforces Round 776 (Div. 3)") 100 101 Idea: [myav](/profile/myav "Pupil myav") 102 103 **Tutorial** 104 105 Tutorial is loading... 106 107 **Solution** 108 109 ``` 110 #include<bits/stdc++.h> 111 using namespace std; 112 using ll = long long; 113 114 #define forn(i, n) for (int i = 0; i < int(n); i++) 115 116 struct point{ 117 int weight, position, id; 118 }; 119 120 void solve(){ 121 int n, m; 122 cin >> n >> m; 123 vector<point>points(m); 124 125 forn(i, m) { 126 cin >> points[i].position >> points[i].weight; 127 points[i].id = i + 1; 128 } 129 130 sort(points.begin(), points.end(), [] (point a, point b){ 131 return a.weight < b.weight; 132 }); 133 134 int sum = 0; 135 forn(i, m){ 136 if(i < 2 * n) sum += points[i].weight; 137 else points.pop_back(); 138 } 139 140 sort(points.begin(), points.end(), [] (point a, point b){ 141 return a.position < b.position; 142 }); 143 144 cout << sum << endl; 145 forn(i, n){ 146 cout << points[i].id << ' ' << points[2 * n - i - 1].id << endl; 147 } 148 } 149 150 int main() { 151 int t; 152 cin >> t; 153 while(t--){ 154 solve(); 155 } 156 return 0; 157 } 158 ``` 159 160 [1650D - Twist the Permutation](/contest/1650/problem/D "Codeforces Round 776 (Div. 3)") 161 162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 163 164 **Tutorial** 165 166 Tutorial is loading... 167 168 **Solution** 169 170 ``` 171 #include <bits/stdc++.h> 172 173 using namespace std; 174 175 typedef long long ll; 176 177 #define forn(i, n) for (int i = 0; i < int(n); i++) 178 179 void solve() { 180 int n; 181 cin >> n; 182 int a[n]; 183 for (int i = 0; i < n; ++i) { 184 cin >> a[i]; 185 } 186 int ans[n]; 187 for (int i = n; i > 0; --i) { 188 int ind = 0; 189 for (int j = 0; j < i; ++j) { 190 ind = a[j] == i ? j : ind; 191 } 192 int b[i]; 193 for (int j = 0; j < i; ++j) { 194 b[(i - 1 - ind + j) % i] = a[j]; 195 } 196 for (int j = 0; j < i; ++j) { 197 a[j] = b[j]; 198 } 199 ans[i - 1] = i != 1 ? (ind + 1) % i : 0; 200 } 201 for (int i = 0; i < n; ++i) { 202 cout << ans[i] << ' '; 203 } 204 cout << '\n'; 205 } 206 int main() { 207 int tests; 208 cin >> tests; 209 forn(tt, tests) { 210 solve(); 211 } 212 } 213 ``` 214 215 [1650E - Rescheduling the Exam](/contest/1650/problem/E "Codeforces Round 776 (Div. 3)") 216 217 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 218 219 **Tutorial** 220 221 Tutorial is loading... 222 223 **Solution** 224 225 ``` 226 #include <bits/stdc++.h> 227 228 #define int long long 229 #define mp make_pair 230 #define x first 231 #define y second 232 #define all(a) (a).begin(), (a).end() 233 #define rall(a) (a).rbegin(), (a).rend() 234 235 typedef long double ld; 236 typedef long long ll; 237 238 using namespace std; 239 240 mt19937 rnd(143); 241 242 const ll inf = 1e9; 243 const ll M = 998'244'353; 244 const ld pi = atan2(0, -1); 245 const ld eps = 1e-4; 246 247 int n, d; 248 249 int cnt(vector<int> &schedule){ 250 int mx = 0, mn = inf; 251 for(int i = 1; i < n; ++i){ 252 mx = max(mx, schedule[i] - schedule[i - 1] - 1); 253 mn = min(mn, schedule[i] - schedule[i - 1] - 1); 254 } 255 return min(mn, max(d - schedule.back() - 1, (mx - 1) / 2)); 256 } 257 258 void solve(int test_case) { 259 cin >> n >> d; 260 vector<int> a(n + 1); 261 int mn = d, min_pos = 0; 262 for(int i = 1; i <= n; ++i){ 263 cin >> a[i]; 264 if(a[i] - a[i - 1] - 1 < mn){ 265 mn = a[i] - a[i - 1] - 1; 266 min_pos = i; 267 } 268 } 269 vector<int> schedule; 270 for(int i = 0; i <= n; ++i){ 271 if(i != min_pos){ 272 schedule.push_back(a[i]); 273 } 274 } 275 int ans = cnt(schedule); 276 if(min_pos > 1){ 277 schedule[min_pos - 1] = a[min_pos]; 278 } 279 ans = max(ans, cnt(schedule)); 280 cout << ans; 281 } 282 283 bool multi = true; 284 285 signed main() { 286 //freopen("in.txt", "r", stdin); 287 //freopen("in.txt", "w", stdout); 288 ios_base::sync_with_stdio(false); 289 cin.tie(nullptr); 290 cout.tie(nullptr); 291 int t = 1; 292 if (multi) { 293 cin >> t; 294 } 295 for (int i = 1; i <= t; ++i) { 296 solve(i); 297 cout << "\n"; 298 } 299 return 0; 300 } 301 ``` 302 303 [1650F - Vitaly and Advanced Useless Algorithms](/contest/1650/problem/F "Codeforces Round 776 (Div. 3)") 304 305 Idea: [Aris](/profile/Aris "Candidate Master Aris") 306 307 **Tutorial** 308 309 Tutorial is loading... 310 311 **Solution** 312 313 ``` 314 #include <bits/stdc++.h> 315 316 using namespace std; 317 318 template<class T> bool ckmin(T &a, T b) {return a > b ? a=b, true : false;} 319 320 #define forn(i, n) for (int i = 0; i < int(n); i++) 321 #define sz(v) (int)v.size() 322 #define all(v) v.begin(),v.end() 323 324 struct option { 325 int t, p, id; 326 option(int _t,int _p, int _id) : t(_t), p(_p), id(_id) { 327 } 328 }; 329 330 const int INF = INT_MAX >> 1; 331 332 vector<int> get_ans(vector<option> &v) { 333 int n = sz(v); 334 vector<vector<int>> dp(101, vector<int>(n+1, INF)); 335 dp[0][0] = 0; 336 for (int k = 1; k <= n; k++) { 337 auto [t,p,id] = v[k-1]; 338 dp[0][k] = 0; 339 for (int i = 100; i > 0; i--) { 340 int prev = max(0,i - p); 341 dp[i][k] = dp[i][k-1]; 342 ckmin(dp[i][k], dp[prev][k-1] + t); 343 } 344 } 345 vector<int> ans; 346 int t = dp[100][n]; 347 348 if (t == INF) return {-1}; 349 for (int i = 100, k = n; k >= 1; k--) { 350 if (dp[i][k] == dp[i][k-1]) { 351 continue; 352 } 353 ans.emplace_back(v[k-1].id); 354 i = max(0, i - v[k-1].p); 355 } 356 357 reverse(all(ans)); 358 ans.emplace_back(t); 359 return ans; 360 } 361 362 void solve(bool flag=true) { 363 364 int n,m; cin >> n >> m; 365 vector<int> a(n); 366 forn(i, n) { 367 cin >> a[i]; 368 } 369 for (int i = n-1; i > 0; i--) { 370 a[i] -= a[i-1]; 371 } 372 373 vector<vector<option>> v(n); 374 forn(j, m) { 375 int e,t,p; cin >> e >> t >> p, e--; 376 v[e].emplace_back(t, p, j+1); 377 } 378 vector<int> ans; 379 forn(i, n) { 380 vector<int> cur = get_ans(v[i]); 381 if (sz(cur) == 1 && cur[0] == -1) { 382 cout << "-1\n"; 383 return; 384 } 385 int t = cur.back(); 386 if (t > a[i]) { 387 cout << "-1\n"; 388 return; 389 } 390 cur.pop_back(); 391 if (i+1 < n) a[i+1] += a[i] - t; 392 393 ans.insert(ans.end(), all(cur)); 394 } 395 396 cout << sz(ans) << '\n'; 397 for (auto e:ans) cout << e << ' '; 398 cout << '\n'; 399 } 400 401 int main() { 402 int t; 403 cin >> t; 404 405 forn(tt, t) { 406 solve(); 407 } 408 } 409 ``` 410 411 [1650G - Counting Shortcuts](/contest/1650/problem/G "Codeforces Round 776 (Div. 3)") 412 413 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 414 415 **Tutorial** 416 417 Tutorial is loading... 418 419 **Solution** 420 421 ``` 422 #include <bits/stdc++.h> 423 424 using namespace std; 425 426 #define forn(i, n) for (int i = 0; i < int(n); i++) 427 #define sz(v) (int)v.size() 428 #define eb emplace_back 429 #define mt make_tuple 430 431 const int INF = INT_MAX >> 1; 432 const int mod = 1e9 + 7; 433 434 void csum(int &a,int b) { 435 a = (a + b) % mod; 436 } 437 438 int s, t; 439 vector<int> us; 440 vector<int> dist; 441 vector<int> dp[2]; 442 int bfs(vector<vector<int>> &g) { 443 queue<tuple<int,int,int>> q; 444 q.push(mt(s, 0, 0)); //[v, dist, count] 445 446 int ans = 0, mnd = INF; 447 us[s] = 1; 448 dp[0][s] = 1; 449 dist[s] = 0; 450 while(!q.empty()) { 451 auto [v,d, x] = q.front(); q.pop(); 452 // cerr << v << ' ' << d << ' ' << dp[x][v] << endl; 453 if (v == t) { 454 if (mnd == INF) { 455 mnd = d; 456 } 457 csum(ans, dp[x][v]); 458 } 459 if (d == mnd + 1) continue; 460 for (int to : g[v]) if(d <= dist[to]) { 461 dist[to] = min(dist[to], d+1); 462 csum(dp[d - dist[to] + 1][to], dp[x][v]); 463 // cerr << "TO: " << to << ' ' << dist[to] << ' ' << d << endl; 464 if(us[to] == 0 || (us[to] == 1 && dist[to] == d)) q.push(mt(to, d+1, us[to]++)); 465 } 466 } 467 return ans; 468 } 469 470 void solve() { 471 int n,m; cin >> n >> m; 472 cin >> s >> t; 473 us.resize(n+1); 474 dp[0].resize(n+1); 475 dp[1].resize(n+1); 476 dist.resize(n+1); 477 forn(i, n+1) { 478 us[i] = dp[0][i] = dp[1][i] = 0; 479 dist[i] = INF; 480 } 481 482 vector<vector<int>> g(n+1); 483 forn(i, m) { 484 int a,b; cin >> a >> b; 485 g[a].eb(b); 486 g[b].eb(a); 487 } 488 489 cout << bfs(g) << '\n'; 490 } 491 492 int main() { 493 int t; 494 cin >> t; 495 496 forn(tt, t) { 497 solve(); 498 } 499 } 500 ```