1697.md (9912B)
1 Source: https://codeforces.com/blog/entry/103835 2 3 [1697A - Parkway Walk](/contest/1697/problem/A "Educational Codeforces Round 130 (Rated for Div. 2)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (vovuh)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", H"r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int tc; 25 cin >> tc; 26 while (tc--) { 27 int n, m; 28 cin >> n >> m; 29 int sum = 0; 30 for (int i = 0; i < n; ++i) { 31 int x; 32 cin >> x; 33 sum += x; 34 } 35 cout << max(0, sum - m) << endl; 36 } 37 38 return 0; 39 } 40 ``` 41 42 [1697B - Promo](/contest/1697/problem/B "Educational Codeforces Round 130 (Rated for Div. 2)") 43 44 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution (Neon)** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 int main() { 58 ios::sync_with_stdio(false); cin.tie(0); 59 int n, q; 60 cin >> n >> q; 61 vector<long long> p(n), s(n + 1); 62 for (auto& x : p) cin >> x; 63 sort(p.begin(), p.end()); 64 for (int i = 0; i < n; ++i) s[i + 1] = s[i] + p[i]; 65 while (q--) { 66 int x, y; 67 cin >> x >> y; 68 cout << s[n - x + y] - s[n - x] << '\n'; 69 } 70 } 71 ``` 72 73 [1697C - awoo's Favorite Problem](/contest/1697/problem/C "Educational Codeforces Round 130 (Rated for Div. 2)") 74 75 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 76 77 **Tutorial** 78 79 Tutorial is loading... 80 81 **Solution (awoo)** 82 83 ``` 84 for _ in range(int(input())): 85 n = int(input()) 86 s = input() 87 t = input() 88 if s.count('b') != t.count('b'): 89 print("NO") 90 continue 91 j = 0 92 for i in range(n): 93 if s[i] == 'b': 94 continue 95 while t[j] == 'b': 96 j += 1 97 if s[i] != t[j] or (s[i] == 'a' and i > j) or (s[i] == 'c' and i < j): 98 print("NO") 99 break 100 j += 1 101 else: 102 print("YES") 103 ``` 104 105 [1697D - Guess The String](/contest/1697/problem/D "Educational Codeforces Round 130 (Rated for Div. 2)") 106 107 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 108 109 **Tutorial** 110 111 Tutorial is loading... 112 113 **Solution (BledDest)** 114 115 ``` 116 #include<bits/stdc++.h> 117 118 using namespace std; 119 120 char ask_character(int i) 121 { 122 cout << "? 1 " << i << endl; 123 cout.flush(); 124 string s; 125 cin >> s; 126 return s[0]; 127 } 128 129 int ask_cnt(int l, int r) 130 { 131 cout << "? 2 " << l << " " << r << endl; 132 cout.flush(); 133 int x; 134 cin >> x; 135 return x; 136 } 137 138 int main() 139 { 140 int n; 141 cin >> n; 142 string s = ""; 143 vector<vector<int>> cnt(n + 1); 144 for(int i = 0; i < n; i++) 145 { 146 if(i == 0) 147 { 148 s.push_back(ask_character(1)); 149 cnt[0] = {1}; 150 } 151 else 152 { 153 int cur = ask_cnt(1, i + 1); 154 if(cur > cnt[i - 1][0]) 155 s.push_back(ask_character(i + 1)); 156 else 157 { 158 map<char, int> last; 159 for(int j = 0; j < s.size(); j++) 160 last[s[j]] = j; 161 vector<int> lasts; 162 for(auto x : last) lasts.push_back(x.second); 163 sort(lasts.begin(), lasts.end()); 164 int l = 0; 165 int r = lasts.size(); 166 // there is always an occurrence in [lasts[l], i) 167 // there is no occurrence in [lasts[r], i) 168 while(r - l > 1) 169 { 170 int m = (l + r) / 2; 171 int c = ask_cnt(lasts[m] + 1, i + 1); 172 if (c == cnt[i - 1][lasts[m]]) 173 l = m; 174 else 175 r = m; 176 } 177 s.push_back(s[lasts[l]]); 178 } 179 cnt[i].resize(i + 1); 180 set<char> q; 181 for(int j = i; j >= 0; j--) 182 { 183 q.insert(s[j]); 184 cnt[i][j] = q.size(); 185 } 186 } 187 } 188 cout << "! " << s << endl; 189 cout.flush(); 190 return 0; 191 } 192 ``` 193 194 [1697E - Coloring](/contest/1697/problem/E "Educational Codeforces Round 130 (Rated for Div. 2)") 195 196 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 197 198 **Tutorial** 199 200 Tutorial is loading... 201 202 **Solution (BledDest)** 203 204 ``` 205 #include<bits/stdc++.h> 206 207 using namespace std; 208 209 const int N = 143; 210 const int K = 5; 211 const int MOD = 998244353; 212 213 int add(int x, int y) 214 { 215 x += y; 216 while(x >= MOD) x -= MOD; 217 while(x < 0) x += MOD; 218 return x; 219 } 220 221 int mul(int x, int y) 222 { 223 return (x * 1ll * y) % MOD; 224 } 225 226 int binpow(int x, int y) 227 { 228 int z = 1; 229 while(y > 0) 230 { 231 if(y % 2 == 1) z = mul(z, x); 232 x = mul(x, x); 233 y /= 2; 234 } 235 return z; 236 } 237 238 int fact[N]; 239 int rfact[N]; 240 241 int A(int n, int k) 242 { 243 return mul(fact[n], rfact[n - k]); 244 } 245 246 int n; 247 248 vector<int> g[N]; 249 int x[N]; 250 int y[N]; 251 int dist[N][N]; 252 int color[N]; 253 int dp[N][N]; 254 255 int cc = 0; 256 set<int> pts; 257 vector<int> compsize; 258 259 void dfs1(int i) 260 { 261 //cerr << i << endl; 262 if(pts.count(i) == 1) return; 263 pts.insert(i); 264 for(auto v : g[i]) 265 { 266 dfs1(v); 267 } 268 } 269 270 void dfs2(int i, int c) 271 { 272 if(color[i] == c) return; 273 color[i] = c; 274 for(auto v : g[i]) 275 dfs2(v, c); 276 } 277 278 int main() 279 { 280 fact[0] = 1; 281 for(int i = 1; i < N; i++) 282 fact[i] = mul(i, fact[i - 1]); 283 for(int i = 0; i < N; i++) 284 rfact[i] = binpow(fact[i], MOD - 2); 285 286 scanf("%d", &n); 287 for(int i = 0; i < n; i++) 288 { 289 scanf("%d %d", &x[i], &y[i]); 290 } 291 for(int i = 0; i < n; i++) 292 { 293 dist[i][i] = int(1e9); 294 for(int j = 0; j < n; j++) 295 if(i != j) 296 dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]); 297 } 298 for(int i = 0; i < n; i++) 299 { 300 int d = *min_element(dist[i], dist[i] + n); 301 for(int j = 0; j < n; j++) 302 if(dist[i][j] == d) g[i].push_back(j); 303 } 304 305 for(int i = 0; i < n; i++) 306 { 307 if(color[i] != 0) continue; 308 cc++; 309 pts.clear(); 310 dfs1(i); 311 //cerr << "!" << endl; 312 int d = *min_element(dist[i], dist[i] + n); 313 set<int> pts2 = pts; 314 bool bad = false; 315 for(auto x : pts) 316 for(auto y : pts2) 317 if(x != y && dist[x][y] != d) 318 bad = true; 319 if(bad) 320 { 321 color[i] = cc; 322 compsize.push_back(1); 323 } 324 else 325 { 326 dfs2(i, cc); 327 compsize.push_back(pts.size()); 328 } 329 } 330 331 dp[0][0] = 1; 332 int m = compsize.size(); 333 for(int i = 0; i < m; i++) 334 for(int j = 0; j < n; j++) 335 { 336 if(dp[i][j] == 0) continue; 337 dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]); 338 if(compsize[i] != 1) 339 { 340 dp[i + 1][j + compsize[i]] = add(dp[i + 1][j + compsize[i]], dp[i][j]); 341 } 342 } 343 int ans = 0; 344 for(int i = 1; i <= n; i++) 345 ans = add(ans, mul(dp[m][i], A(n, i))); 346 cout << ans << endl; 347 } 348 ``` 349 350 [1697F - Too Many Constraints](/contest/1697/problem/F "Educational Codeforces Round 130 (Rated for Div. 2)") 351 352 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 353 354 **Tutorial** 355 356 Tutorial is loading... 357 358 **Solution (awoo)** 359 360 ``` 361 #include <bits/stdc++.h> 362 363 #define forn(i, n) for (int i = 0; i < int(n); i++) 364 365 using namespace std; 366 367 struct constraint{ 368 int tp, i, j, x; 369 }; 370 371 vector<vector<int>> g, tg; 372 vector<char> used; 373 vector<int> clr, ord; 374 375 void ts(int v){ 376 used[v] = true; 377 for (int u : g[v]) if (!used[u]) 378 ts(u); 379 ord.push_back(v); 380 } 381 382 void dfs(int v, int k){ 383 clr[v] = k; 384 for (int u : tg[v]) if (clr[u] == -1) 385 dfs(u, k); 386 } 387 388 void either(int x, int y){ 389 g[x ^ 1].push_back(y); 390 g[y ^ 1].push_back(x); 391 tg[y].push_back(x ^ 1); 392 tg[x].push_back(y ^ 1); 393 } 394 395 void implies(int x, int y){ 396 either(x ^ 1, y); 397 } 398 399 void must(int x){ 400 either(x, x); 401 } 402 403 int main() { 404 int t; 405 scanf("%d", &t); 406 forn(_, t){ 407 int n, m, k; 408 scanf("%d%d%d", &n, &m, &k); 409 vector<constraint> c(m); 410 forn(i, m){ 411 scanf("%d%d", &c[i].tp, &c[i].i); 412 if (c[i].tp != 1) scanf("%d", &c[i].j); 413 scanf("%d", &c[i].x); 414 --c[i].i, --c[i].j; 415 } 416 int vts = n * (k + 2); 417 g.assign(2 * vts, vector<int>()); 418 tg.assign(2 * vts, vector<int>()); 419 forn(i, n){ 420 forn(j, (k + 2) - 1) 421 implies(2 * (i * (k + 2) + j + 1) + 1, 2 * (i * (k + 2) + j) + 1); 422 must(2 * (i * (k + 2) + 1) + 1); 423 must(2 * (i * (k + 2) + k + 1)); 424 } 425 forn(i, n - 1) forn(j, k + 2){ 426 implies(2 * (i * (k + 2) + j) + 1, 2 * ((i + 1) * (k + 2) + j) + 1); 427 } 428 forn(i, m){ 429 if (c[i].tp == 1) 430 either(2 * (c[i].i * (k + 2) + c[i].x + 1) + 1, 2 * (c[i].i * (k + 2) + c[i].x)); 431 else if (c[i].tp == 2){ 432 for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){ 433 implies(2 * (c[i].i * (k + 2) + a) + 1, 2 * (c[i].j * (k + 2) + (c[i].x - a) + 1)); 434 implies(2 * (c[i].j * (k + 2) + a) + 1, 2 * (c[i].i * (k + 2) + (c[i].x - a) + 1)); 435 } 436 } 437 else{ 438 for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){ 439 implies(2 * (c[i].i * (k + 2) + a + 1), 2 * (c[i].j * (k + 2) + (c[i].x - a)) + 1); 440 implies(2 * (c[i].j * (k + 2) + a + 1), 2 * (c[i].i * (k + 2) + (c[i].x - a)) + 1); 441 } 442 } 443 } 444 used.assign(2 * vts, 0); 445 ord.clear(); 446 forn(i, used.size()) if (!used[i]) ts(i); 447 reverse(ord.begin(), ord.end()); 448 clr.assign(2 * vts, -1); 449 int cc = 0; 450 for (int v : ord) if (clr[v] == -1){ 451 dfs(v, cc); 452 ++cc; 453 } 454 vector<int> vals(vts); 455 bool ans = true; 456 forn(i, vts){ 457 if (clr[2 * i] == clr[2 * i + 1]){ 458 ans = false; 459 break; 460 } 461 vals[i] = (clr[2 * i] < clr[2 * i + 1]); 462 } 463 if (!ans){ 464 puts("-1"); 465 continue; 466 } 467 forn(i, n){ 468 int lst = 0; 469 forn(j, k + 2) if (vals[i * (k + 2) + j]) 470 lst = j; 471 printf("%d ", lst); 472 } 473 puts(""); 474 } 475 return 0; 476 } 477 ```