1264.md (14101B)
1 Source: https://codeforces.com/blog/entry/71995 2 3 Tutorial is loading... 4 5 **Python Solution** 6 7 ``` 8 T = int(input()) 9 for tc in range(T): 10 s = [c for c in input()] 11 n = len(s) 12 i = 0 13 while (i < n): 14 if (s[i] == '?'): 15 prv = 'd' if i == 0 else s[i - 1] 16 nxt = 'e' if i + 1 >= n else s[i + 1] 17 for x in ['a', 'b', 'c']: 18 if (x != prv) and (x != nxt): 19 s[i] = x 20 break 21 else: 22 i += 1 23 24 ok = True 25 for i in range(n - 1): 26 if (s[i] == s[i + 1]): 27 print("-1") 28 ok = False 29 break 30 if (ok == True): 31 print("".join(s)) 32 ``` 33 34 Author: [isaf27](/profile/isaf27 "International Grandmaster isaf27"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 35 36 Tutorial is loading... 37 38 **C++ solution** 39 40 ``` 41 #include <bits/stdc++.h> 42 43 using namespace std; 44 45 const int M = 2e5 + 239; 46 47 int n, p[M], x; 48 49 void solve() 50 { 51 cin >> n; 52 for (int i = 0; i < n; i++) 53 { 54 cin >> x; 55 p[x - 1] = i; 56 } 57 int l = n; 58 int r = 0; 59 string ans = ""; 60 for (int i = 0; i < n; i++) 61 { 62 l = min(l, p[i]); 63 r = max(r, p[i]); 64 if (r - l == i) 65 ans += '1'; 66 else 67 ans += '0'; 68 } 69 cout << ans << "\n"; 70 } 71 72 int main() 73 { 74 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 75 int t; 76 cin >> t; 77 while (t--) 78 solve(); 79 return 0; 80 } 81 ``` 82 83 Author: [isaf27](/profile/isaf27 "International Grandmaster isaf27"), prepare [isaf27](/profile/isaf27 "International Grandmaster isaf27") 84 85 Tutorial is loading... 86 87 **C++ solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 #define forn(i, n) for (int i = 0; i < int(n); i++) 95 96 int main() { 97 int t; 98 cin >> t; 99 forn(tt, t) { 100 int n; 101 cin >> n; 102 map<int,int> c; 103 forn(i, n) { 104 int pi; 105 cin >> pi; 106 c[-pi]++; 107 } 108 vector<int> pp; 109 for (auto p: c) 110 pp.push_back(p.second); 111 bool ok = false; 112 int g = pp[0]; 113 int i = 1; 114 int s = 0; 115 while (s <= g && i < pp.size()) 116 s += pp[i++]; 117 if (g < s) { 118 int b = 0; 119 while (b <= g && i < pp.size()) 120 b += pp[i++]; 121 while (i < pp.size() && g + s + b + pp[i] <= n / 2) 122 b += pp[i++]; 123 if (g < b && g + s + b <= n / 2) { 124 ok = true; 125 cout << g << " " << s << " " << b << endl; 126 } 127 } 128 if (!ok) 129 cout << 0 << " " << 0 << " " << 0 << endl; 130 } 131 } 132 ``` 133 134 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), prepare [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 135 136 Tutorial is loading... 137 138 **C++ Solution** 139 140 ``` 141 #include <bits/stdc++.h> 142 using namespace std; 143 144 int main() { 145 map<int, int> hs; 146 cin >> hs[0] >> hs[1] >> hs[2] >> hs[3]; 147 int total = hs[0] + hs[1] + hs[2] + hs[3]; 148 for (int st = 0; st < 4; st++) if (hs[st]) { 149 vector<int> res; 150 auto ths = hs; 151 ths[st]--; 152 res.push_back(st); 153 int last = st; 154 for (int i = 0; i < total - 1; i++) { 155 if (ths[last - 1]) { 156 ths[last - 1]--; 157 res.push_back(last - 1); 158 last--; 159 } 160 else if (ths[last + 1]) { 161 ths[last + 1]--; 162 res.push_back(last + 1); 163 last++; 164 } 165 else { 166 break; 167 } 168 } 169 if ((int) res.size() == total) { 170 cout << "YES\n"; 171 for (int i = 0; i < (int) res.size(); i++) { 172 cout << res[i] << " \n"[i == (int) res.size() - 1]; 173 } 174 return 0; 175 } 176 } 177 cout << "NO\n"; 178 return 0; 179 } 180 ``` 181 182 Author: [laoriu](/profile/laoriu "Master laoriu"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 183 184 Tutorial is loading... 185 186 **C++ Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 using namespace std; 191 192 const int MOD = 119 << 23 | 1; 193 194 int inv(int a) { 195 int r = 1, t = a, k = MOD - 2; 196 while (k) { 197 if (k & 1) r = (long long) r * t % MOD; 198 t = (long long) t * t % MOD; 199 k >>= 1; 200 } 201 return r; 202 } 203 204 int main() { 205 int n; cin >> n; 206 vector<int> p(n); 207 for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD; 208 int a = 1, b = 0; 209 for (int i = 0; i < n; i++) { 210 a = (long long) a * inv(p[i]) % MOD; 211 b = (long long) b * inv(p[i]) % MOD; 212 a = (a + (long long) (p[i] - 1) * inv(p[i])) % MOD; 213 b = (b - inv(p[i]) + MOD) % MOD; 214 } 215 cout << (long long) (MOD - b) * inv(a) % MOD << "\n"; 216 return 0; 217 } 218 ``` 219 220 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 221 222 Tutorial is loading... 223 224 **C++ Solution** 225 226 ``` 227 #include <bits/stdc++.h> 228 using namespace std; 229 230 const int MOD = 119 << 23 | 1; 231 232 int fpow(int a, int k) { 233 int r = 1, t = a; 234 while (k) { 235 if (k & 1) r = (long long) r * t % MOD; 236 t = (long long) t * t % MOD; 237 k >>= 1; 238 } 239 return r; 240 } 241 242 int main() { 243 string s; cin >> s; 244 int n = s.size(); 245 vector<vector<int>> dp(n, vector<int>(n)); 246 vector<int> f(n + 1); 247 for (int i = 0; i < n; i++) { 248 f[i + 1] = f[i]; 249 f[i + 1] += s[i] == '?'; 250 } 251 for (int len = 2; len <= n; len++) { 252 for (int i = 0; i < n - len + 1; i++) { 253 int j = i + len - 1; 254 if (s[i] != '(') { 255 dp[i][j] += dp[i + 1][j]; 256 dp[i][j] %= MOD; 257 } 258 if (s[j] != ')') { 259 dp[i][j] += dp[i][j - 1]; 260 dp[i][j] %= MOD; 261 } 262 if (s[i] != '(' && s[j] != ')') { 263 dp[i][j] -= dp[i + 1][j - 1]; 264 dp[i][j] += MOD; 265 dp[i][j] %= MOD; 266 } 267 if (s[i] != ')' && s[j] != '(') { 268 dp[i][j] += dp[i + 1][j - 1]; 269 dp[i][j] %= MOD; 270 dp[i][j] += fpow(2, f[j] - f[i + 1]); 271 dp[i][j] %= MOD; 272 } 273 } 274 } 275 cout << dp[0][n - 1] << "\n"; 276 return 0; 277 } 278 ``` 279 280 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 281 282 Tutorial is loading... 283 284 **C++ Solution** 285 286 ``` 287 #include <bits/stdc++.h> 288 using namespace std; 289 290 const int MOD = 119 << 23 | 1; 291 292 struct node_t { 293 int prd; 294 int val; 295 node_t() { 296 prd = val = 0; 297 } 298 }; 299 300 node_t operator + (node_t a, node_t b) { 301 if (!a.prd) return b; 302 if (!b.prd) return a; 303 node_t c; 304 c.prd = (long long) a.prd * b.prd % MOD; 305 c.val = (long long) a.val * b.prd % MOD; 306 c.val = (c.val + b.val) % MOD; 307 return c; 308 } 309 310 int inv(int a) { 311 int r = 1, t = a, k = MOD - 2; 312 while (k) { 313 if (k & 1) r = (long long) r * t % MOD; 314 t = (long long) t * t % MOD; 315 k >>= 1; 316 } 317 return r; 318 } 319 320 int main() { 321 int n, q; cin >> n >> q; 322 vector<int> p(n); 323 for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD; 324 vector<node_t> st(n << 2); 325 auto upd = [&] (int p, node_t val) { 326 for (st[p += n] = val; 1 < p; ) p >>= 1, st[p] = st[p << 1] + st[p << 1 | 1]; 327 }; 328 auto query = [&] (int l, int r) { 329 node_t lres, rres; 330 for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { 331 if (l & 1) { 332 lres = lres + st[l++]; 333 } 334 if (r & 1) { 335 rres = st[--r] + rres; 336 } 337 } 338 return (lres + rres).val; 339 }; 340 for (int i = 0; i < n; i++) { 341 node_t c; 342 c.val = c.prd = inv(p[i]); 343 upd(i, c); 344 } 345 set<int> ss; 346 ss.insert(0); 347 int res = query(0, n - 1); 348 for (int i = 0; i < q; i++) { 349 string op; int u; cin >> u; u--; 350 auto it = ss.lower_bound(u); 351 if (it == ss.end() || *it != u) { 352 it = ss.insert(u).first; 353 int lo = *(--it); 354 it++; 355 int hi = n; 356 if (++it != ss.end()) { 357 hi = *it; 358 } 359 res -= query(lo, hi - 1); 360 res += MOD; 361 res %= MOD; 362 res += query(lo, u - 1); 363 res %= MOD; 364 res += query(u, hi - 1); 365 res %= MOD; 366 } 367 else { 368 int lo = *(--it); 369 it++; 370 int hi = n; 371 if (++it != ss.end()) { 372 hi = *it; 373 } 374 res += query(lo, hi - 1); 375 res %= MOD; 376 res -= query(lo, u - 1); 377 res += MOD; 378 res %= MOD; 379 res -= query(u, hi - 1); 380 res += MOD; 381 res %= MOD; 382 ss.erase(u); 383 } 384 cout << res << "\n"; 385 } 386 return 0; 387 } 388 ``` 389 390 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 391 392 Tutorial is loading... 393 394 **C++ Solution** 395 396 ``` 397 #include <bits/stdc++.h> 398 using namespace std; 399 400 const int MOD = 119 << 23 | 1; 401 402 int inv(int a) { 403 int r = 1, t = a, k = MOD - 2; 404 while (k) { 405 if (k & 1) r = (long long) r * t % MOD; 406 t = (long long) t * t % MOD; 407 k >>= 1; 408 } 409 return r; 410 } 411 412 int main() { 413 string s; cin >> s; 414 int k = s.size() + 1; 415 int a = 0, b = 0, c = 0, d = 0; 416 for (char e : s) { 417 if (e == ')') { 418 b++; 419 } 420 if (e == '?') { 421 d++; 422 } 423 } 424 map<int, vector<int>> dps; 425 auto calc = [&] (int a, int b, int c, int d) { 426 int x = b + d - a; 427 if (x < 0) return 0; 428 int k = c + d; 429 if (k < x) x = k; 430 if (dps.count(k)) return dps[k][x]; 431 auto& dp = dps[k]; 432 dp.resize(k + 1); 433 int t = 0, w = 1; 434 for (int i = 0; i <= k; i++) { 435 t += w; 436 t %= MOD; 437 dp[i] = t; 438 w = (long long) w * (c + d - i) % MOD; 439 w = (long long) w * inv(i + 1) % MOD; 440 } 441 return dp[x]; 442 }; 443 int res = 0; 444 for (int i = 0; i < (int) s.size(); i++) { 445 char e = s[i]; 446 if (e == '(') { 447 a++; 448 } 449 if (e == ')') { 450 b--; 451 } 452 if (e == '?') { 453 c++; 454 d--; 455 } 456 if (e == '(') { 457 res += calc(a, b, c, d); 458 res %= MOD; 459 } 460 else if (e == '?') { 461 a++, c--; 462 res += calc(a, b, c, d); 463 res %= MOD; 464 a--, c++; 465 } 466 } 467 cout << res << "\n"; 468 return 0; 469 } 470 ``` 471 472 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 473 474 Tutorial is loading... 475 476 **C++ Solution** 477 478 ``` 479 #include <bits/stdc++.h> 480 using namespace std; 481 482 int main() { 483 int n, m; cin >> n >> m; 484 vector<int> d(n); 485 vector<vector<int>> g(n, vector<int>(n)); 486 vector<vector<int>> f(n, vector<int>(n, 1)); 487 for (int i = 0; i < m; i++) { 488 int u, v; cin >> u >> v; u--, v--; 489 d[u]++; 490 g[u][v] = 1, g[v][u] = 2; 491 f[u][v] = f[v][u] = 0; 492 } 493 priority_queue<pair<int, int>> heap; 494 for (int i = 0; i < n; i++) { 495 if (d[i] < n - 1) { 496 heap.push({-d[i], i}); 497 } 498 } 499 while (!heap.empty()) { 500 int u = heap.top().second; 501 heap.pop(); 502 queue<int> que; 503 vector<int> vis(n), from(n); 504 que.push(u), vis[u] = 1; 505 int id = -1; 506 while (!que.empty()) { 507 int v = que.front(); que.pop(); 508 int found = 0; 509 for (int w = 0; w < n; w++) if (w != v && !g[v][w]) { 510 found = 1; 511 break; 512 } 513 if (found) { 514 id = v; 515 break; 516 } 517 for (int w = 0; w < n; w++) if (!vis[w] && g[v][w] == 2 && f[v][w] == 1) { 518 que.push(w), vis[w] = 1; 519 from[w] = v; 520 } 521 } 522 if (id == -1) { 523 continue; 524 } 525 for (int v = 0; v < n; v++) if (v != id && !g[id][v]) { 526 g[id][v] = 1, g[v][id] = 2; 527 break; 528 } 529 while (id != u) { 530 int nid = from[id]; 531 swap(g[id][nid], g[nid][id]); 532 id = nid; 533 } 534 d[u]++; 535 if (d[u] < n - 1) { 536 heap.push({-d[u], u}); 537 } 538 } 539 for (int i = 0; i < n; i++) { 540 for (int j = 0; j < n; j++) { 541 if (i == j) { 542 cout << 0; 543 } 544 else { 545 cout << 2 - g[i][j]; 546 } 547 } 548 cout << "\n"; 549 } 550 return 0; 551 } 552 ``` 553 554 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 555 556 Another cool problem: [WEICOM](https://www.codechef.com/LTIME53/problems/WEICOM). 557 558 Tutorial is loading... 559 560 **Python Solution** 561 562 ``` 563 n,a,d=map(int,input().split()) 564 print(368131125*a%10**9*12*10**9+1,368131125*d%10**9*12*10**9) 565 ``` 566 567 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen") 568 569 Bonus: [another beautiful problem](https://www.hackerearth.com/problem/algorithm/lucky-sequence-1-77a76688/).