1997.md (8309B)
1 Source: https://codeforces.com/blog/entry/132154 2 3 [1997A - Strong Password](/contest/1997/problem/A "Educational Codeforces Round 168 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 void solve() 19 { 20 string s; 21 cin >> s; 22 int n = s.size(); 23 int idx = -1; 24 for(int i = 0; i + 1 < n; i++) 25 if(s[i] == s[i + 1]) 26 idx = i; 27 if(idx == -1) 28 { 29 if(s.back() == 'a') cout << (s + "b") << endl; 30 else cout << (s + "a") << endl; 31 } 32 else 33 { 34 string t = "a"; 35 if(s[idx] == 'a') t = "b"; 36 cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl; 37 } 38 } 39 40 int main() 41 { 42 int t; 43 cin >> t; 44 for(int i = 0; i < t; i++) 45 solve(); 46 } 47 ``` 48 49 [1997B - Make Three Regions](/contest/1997/problem/B "Educational Codeforces Round 168 (Rated for Div. 2)") 50 51 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Solution (Neon)** 58 59 ``` 60 #include <bits/stdc++.h> 61 62 using namespace std; 63 64 int main() { 65 int t; 66 cin >> t; 67 while (t--) { 68 int n; 69 cin >> n; 70 vector<string> s(2); 71 for (auto& x : s) cin >> x; 72 int ans = 0; 73 for (int i = 1; i < n - 1; ++i) { 74 bool ok = true; 75 ok &= (s[0][i] == '.' && s[1][i] == '.'); 76 ok &= (s[0][i - 1] != s[1][i - 1]); 77 ok &= (s[0][i + 1] != s[1][i + 1]); 78 ok &= (s[0][i - 1] == s[0][i + 1]); 79 ans += ok; 80 } 81 cout << ans << '\n'; 82 } 83 } 84 ``` 85 86 [1997C - Even Positions](/contest/1997/problem/C "Educational Codeforces Round 168 (Rated for Div. 2)") 87 88 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution (adedalic)** 95 96 ``` 97 import java.util.LinkedList 98 99 fun main() { 100 repeat(readln().toInt()) { 101 val n = readln().toInt() 102 val s = readln() 103 104 var ans = 0L 105 val bracketPositions = LinkedList<Int>() 106 for (i in s.indices) { 107 var c = s[i] 108 if (c == '_') { 109 c = if (bracketPositions.isEmpty()) '(' else ')' 110 } 111 if (c == ')') { 112 ans += i - bracketPositions.pollLast() 113 } 114 else 115 bracketPositions.addLast(i) 116 } 117 println(ans) 118 } 119 } 120 ``` 121 122 [1997D - Maximize the Root](/contest/1997/problem/D "Educational Codeforces Round 168 (Rated for Div. 2)") 123 124 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 125 126 **Tutorial** 127 128 Tutorial is loading... 129 130 **Solution (Neon)** 131 132 ``` 133 #include <bits/stdc++.h> 134 135 using namespace std; 136 137 const int INF = 1e9; 138 139 int main() { 140 ios::sync_with_stdio(false); cin.tie(0); 141 int t; 142 cin >> t; 143 while (t--) { 144 int n; 145 cin >> n; 146 vector<int> a(n); 147 for (auto& x : a) cin >> x; 148 vector<vector<int>> g(n); 149 for (int i = 1; i < n; ++i) { 150 int p; 151 cin >> p; 152 g[p - 1].push_back(i); 153 } 154 155 auto check = [&](auto&& self, int v, int x) -> bool { 156 if (x > INF) return false; 157 bool isLeaf = true; 158 if (v) x += max(0, x - a[v]); 159 for (auto u : g[v]) { 160 isLeaf = false; 161 if (!self(self, u, x)) return false; 162 } 163 return (!isLeaf || x <= a[v]); 164 }; 165 166 int l = 1, r = INF; 167 while (l <= r) { 168 int mid = (l + r) / 2; 169 if (check(check, 0, mid)) { 170 l = mid + 1; 171 } else { 172 r = mid - 1; 173 } 174 } 175 176 cout << a[0] + l - 1 << '\n'; 177 } 178 } 179 ``` 180 181 [1997E - Level Up](/contest/1997/problem/E "Educational Codeforces Round 168 (Rated for Div. 2)") 182 183 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Solution 1 (awoo)** 190 191 ``` 192 #include <bits/stdc++.h> 193 #include "ext/pb_ds/assoc_container.hpp" 194 195 #define forn(i, n) for (int i = 0; i < int(n); i++) 196 197 using namespace __gnu_pbds; 198 using namespace std; 199 200 template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 201 202 struct query{ 203 int i, j; 204 }; 205 206 int main() { 207 cin.tie(0); 208 ios::sync_with_stdio(false); 209 int n, m; 210 cin >> n >> m; 211 vector<int> a(n); 212 forn(i, n) cin >> a[i]; 213 vector<vector<query>> q(n + 1); 214 forn(j, m){ 215 int i, x; 216 cin >> i >> x; 217 --i; 218 q[x].push_back({i, j}); 219 } 220 forn(i, n + 1){ 221 sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){ 222 return a.i > b.i; 223 }); 224 } 225 vector<int> ord(n); 226 iota(ord.begin(), ord.end(), 0); 227 sort(ord.begin(), ord.end(), [&](int i, int j){ 228 return a[i] > a[j]; 229 }); 230 231 vector<int> cur(n + 1); 232 vector<char> ans(m); 233 ordered_set<int> alive(ord.begin(), ord.end()); 234 for (int lvl = 1; lvl <= n; ++lvl){ 235 for (int k = 1; k <= n; ++k){ 236 if (cur[k] >= n) break; 237 int x = alive.order_of_key(cur[k]); 238 int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1); 239 while (!q[k].empty() && q[k].back().i <= nxt){ 240 ans[q[k].back().j] = (a[q[k].back().i] >= lvl); 241 q[k].pop_back(); 242 } 243 cur[k] = nxt + 1; 244 } 245 while (!ord.empty() && a[ord.back()] == lvl){ 246 alive.erase(ord.back()); 247 ord.pop_back(); 248 } 249 } 250 251 for (auto x : ans) cout << (x ? "YES" : "NO") << '\n'; 252 return 0; 253 } 254 ``` 255 256 **Solution 2 (awoo)** 257 258 ``` 259 #include <bits/stdc++.h> 260 261 #define forn(i, n) for (int i = 0; i < int(n); i++) 262 263 using namespace std; 264 265 struct query{ 266 int i, j; 267 }; 268 269 int main() { 270 cin.tie(0); 271 ios::sync_with_stdio(false); 272 int n, m; 273 cin >> n >> m; 274 vector<int> a(n); 275 forn(i, n) cin >> a[i]; 276 vector<vector<query>> q(n + 1); 277 forn(j, m){ 278 int i, x; 279 cin >> i >> x; 280 --i; 281 q[x].push_back({i, j}); 282 } 283 forn(i, n + 1) sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){ 284 return a.i > b.i; 285 }); 286 287 int P = min(1000, n + 1); 288 289 vector<char> ans(m); 290 for (int k = 1; k < P; ++k){ 291 int cur = 1; 292 int cnt = 0; 293 forn(i, n){ 294 bool fl = false; 295 if (a[i] >= cur){ 296 ++cnt; 297 fl = true; 298 if (cnt == k){ 299 ++cur; 300 cnt = 0; 301 } 302 } 303 while (!q[k].empty() && q[k].back().i == i){ 304 ans[q[k].back().j] = fl; 305 q[k].pop_back(); 306 } 307 } 308 } 309 310 vector<int> sum1(n), sum2(n); 311 int p2 = ceil(sqrt(n + 2)); 312 313 auto add = [&](int i){ 314 int bl = i / p2; 315 for (int j = bl + 1; j * p2 < n; ++j) 316 ++sum1[j]; 317 for (int j = i; j < (bl + 1) * p2 && j < n; ++j) 318 ++sum2[j]; 319 }; 320 321 int mx = n / P + 5; 322 vector<vector<int>> pos(mx); 323 forn(i, n){ 324 if (a[i] < mx) 325 pos[a[i]].push_back(i); 326 else 327 add(i); 328 } 329 for (auto &it : pos) reverse(it.begin(), it.end()); 330 331 for (int k = P; k <= n; ++k){ 332 while (true){ 333 int mn = n; 334 int who = -1; 335 forn(lvl, mx) if (!pos[lvl].empty()){ 336 int i = pos[lvl].back(); 337 if (mn < i) continue; 338 int cnt = sum1[i / p2] + sum2[i]; 339 if (a[i] >= cnt / k + 1){ 340 mn = i; 341 who = lvl; 342 } 343 } 344 if (who == -1) break; 345 add(mn); 346 pos[who].pop_back(); 347 } 348 for (auto it : q[k]){ 349 int lvl = a[it.i]; 350 ans[it.j] = (lvl >= mx || pos[lvl].empty() || pos[lvl].back() > it.i); 351 } 352 } 353 354 for (auto x : ans) cout << (x ? "YES" : "NO") << '\n'; 355 return 0; 356 } 357 ``` 358 359 [1997F - Chips on a Line](/contest/1997/problem/F "Educational Codeforces Round 168 (Rated for Div. 2)") 360 361 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 362 363 **Tutorial** 364 365 Tutorial is loading... 366 367 **Solution (BledDest)** 368 369 ``` 370 #include<bits/stdc++.h> 371 372 using namespace std; 373 374 const int MOD = 998244353; 375 376 int add(int x, int y) 377 { 378 x += y; 379 while(x >= MOD) x -= MOD; 380 while(x < 0) x += MOD; 381 return x; 382 } 383 384 int mul(int x, int y) 385 { 386 return (x * 1ll * y) % MOD; 387 } 388 389 int main() 390 { 391 int n, x, m; 392 cin >> n >> x >> m; 393 vector<int> fib = {0, 1}; 394 for(int i = 2; i <= 30; i++) 395 fib.push_back(fib[i - 1] + fib[i - 2]); 396 397 398 int max_sum = fib[x] * n; 399 vector<vector<int>> dp(max_sum + 1, vector<int>(n + 1)); 400 dp[0][0] = 1; 401 for(int i = 1; i <= x; i++) 402 for(int j = 0; j < max_sum; j++) 403 for(int k = 0; k < n; k++) 404 { 405 if(j + fib[i] <= max_sum) 406 dp[j + fib[i]][k + 1] = add(dp[j + fib[i]][k + 1], dp[j][k]); 407 } 408 409 vector<int> cost(max_sum + 1, 1e9); 410 cost[0] = 0; 411 for(int j = 1; j <= max_sum; j++) 412 for(int i = 1; i <= 30; i++) 413 if(j >= fib[i]) 414 cost[j] = min(cost[j], cost[j - fib[i]] + 1); 415 416 int ans = 0; 417 for(int i = 0; i <= max_sum; i++) 418 if(cost[i] == m) 419 ans = add(ans, dp[i][n]); 420 cout << ans << endl; 421 } 422 ```