1739.md (9575B)
1 Source: https://codeforces.com/blog/entry/107461 2 3 [1739A - Immobile Knight](/contest/1739/problem/A "Educational Codeforces Round 136 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 n, m = map(int, input().split()) 16 print(n // 2 + 1, m // 2 + 1) 17 ``` 18 19 **Solution 2 (awoo)** 20 21 ``` 22 #include <bits/stdc++.h> 23 24 #define forn(i, n) for (int i = 0; i < int(n); i++) 25 26 using namespace std; 27 28 int main() { 29 int t; 30 scanf("%d", &t); 31 forn(_, t){ 32 int n, m; 33 scanf("%d%d", &n, &m); 34 int svx = 1, svy = 1; 35 for (int x = 1; x <= n; ++x){ 36 for (int y = 1; y <= m; ++y){ 37 bool ok = true; 38 for (int dx : {-2, -1, 1, 2}){ 39 for (int dy : {-2, -1, 1, 2}){ 40 if (abs(dx * dy) != 2) continue; 41 if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m) 42 ok = false; 43 } 44 } 45 if (ok){ 46 svx = x; 47 svy = y; 48 } 49 } 50 } 51 printf("%d %d\n", svx, svy); 52 } 53 } 54 ``` 55 56 [1739B - Array Recovery](/contest/1739/problem/B "Educational Codeforces Round 136 (Rated for Div. 2)") 57 58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 59 60 **Tutorial** 61 62 Tutorial is loading... 63 64 **Solution (Neon)** 65 66 ``` 67 for _ in range(int(input())): 68 n = int(input()) 69 ans = [0] 70 for x in map(int, input().split()): 71 if x != 0 and ans[-1] - x >= 0: 72 print(-1) 73 break 74 else: 75 ans.append(ans[-1] + x) 76 else: 77 print(*ans[1:]) 78 ``` 79 80 [1739C - Card Game](/contest/1739/problem/C "Educational Codeforces Round 136 (Rated for Div. 2)") 81 82 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 83 84 **Tutorial** 85 86 Tutorial is loading... 87 88 **Solution 1 (BledDest)** 89 90 ``` 91 #include<bits/stdc++.h> 92 93 using namespace std; 94 95 long long dp[65][65][3]; 96 97 void solve(int n) 98 { 99 memset(dp, 0, sizeof dp); 100 int k = n / 2; 101 dp[0][0][2] = 1; 102 for(int i = 0; i <= k; i++) 103 for(int j = 0; j <= k; j++) 104 for(int t = 0; t <= 2; t++) 105 { 106 int turn = (i + j) % 4; 107 if (turn == 0 || turn == 3) 108 { 109 if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t]; 110 if(j < k) dp[i][j + 1][t] += dp[i][j][t]; 111 } 112 else 113 { 114 if(i < k) dp[i + 1][j][t] += dp[i][j][t]; 115 if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t]; 116 } 117 } 118 for(int i = 0; i < 3; i++) 119 cout << dp[k][k][i] % 998244353 << " "; 120 cout << endl; 121 } 122 123 int main() 124 { 125 int t; 126 cin >> t; 127 for(int i = 0; i < t; i++) 128 { 129 int n; 130 cin >> n; 131 solve(n); 132 } 133 } 134 ``` 135 136 **Solution 2 (BledDest)** 137 138 ``` 139 def fact(n): 140 return 1 if n == 0 else n * fact(n - 1) 141 142 def choose(n, k): 143 return fact(n) // fact(k) // fact(n - k) 144 145 def calc(n): 146 if n == 2: 147 return [1, 0, 1] 148 else: 149 a = calc(n - 2) 150 return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1] 151 152 t = int(input()) 153 for i in range(t): 154 mod = 998244353 155 n = int(input()) 156 a = calc(n) 157 a = list(map(lambda x: x % mod, a)) 158 print(*a) 159 ``` 160 161 [1739D - Reset K Edges](/contest/1739/problem/D "Educational Codeforces Round 136 (Rated for Div. 2)") 162 163 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 164 165 **Tutorial** 166 167 Tutorial is loading... 168 169 **Solution (awoo)** 170 171 ``` 172 #include <bits/stdc++.h> 173 174 #define forn(i, n) for (int i = 0; i < int(n); i++) 175 176 using namespace std; 177 178 int n; 179 vector<vector<int>> g; 180 181 vector<int> st; 182 vector<int> pd; 183 184 void init(int v, int d){ 185 st.push_back(v); 186 if (int(st.size()) - d >= 0) 187 pd[v] = st[st.size() - d]; 188 for (int u : g[v]) 189 init(u, d); 190 st.pop_back(); 191 } 192 193 vector<char> used; 194 195 void dfs(int v){ 196 used[v] = true; 197 for (int u : g[v]) if (!used[u]) 198 dfs(u); 199 } 200 201 int get(int d){ 202 pd.assign(n, -1); 203 init(0, d); 204 205 vector<int> ord, h(n); 206 queue<int> q; 207 q.push(0); 208 while (!q.empty()){ 209 int v = q.front(); 210 q.pop(); 211 ord.push_back(v); 212 for (int u : g[v]){ 213 q.push(u); 214 h[u] = h[v] + 1; 215 } 216 } 217 reverse(ord.begin(), ord.end()); 218 219 used.assign(n, 0); 220 int res = 0; 221 for (int v : ord) if (!used[v] && h[v] > d){ 222 ++res; 223 dfs(pd[v]); 224 } 225 226 return res; 227 } 228 229 int main() { 230 int t; 231 scanf("%d", &t); 232 while (t--){ 233 int k; 234 scanf("%d%d", &n, &k); 235 g.assign(n, vector<int>()); 236 for (int i = 1; i < n; ++i){ 237 int p; 238 scanf("%d", &p); 239 --p; 240 g[p].push_back(i); 241 } 242 int l = 1, r = n - 1; 243 int ans = n; 244 while (l <= r){ 245 int m = (l + r) / 2; 246 if (get(m) <= k){ 247 ans = m; 248 r = m - 1; 249 } 250 else{ 251 l = m + 1; 252 } 253 } 254 printf("%d\n", ans); 255 } 256 return 0; 257 } 258 ``` 259 260 [1739E - Cleaning Robot](/contest/1739/problem/E "Educational Codeforces Round 136 (Rated for Div. 2)") 261 262 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution (awoo)** 269 270 ``` 271 #include <bits/stdc++.h> 272 273 using namespace std; 274 275 #define forn(i, n) for(int i = 0; i < int(n); i++) 276 277 const int INF = 1e9; 278 279 int main(){ 280 int n; 281 cin >> n; 282 vector<string> s(2); 283 forn(i, 2) cin >> s[i]; 284 vector<array<array<int, 2>, 2>> dp(n + 1); 285 forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF; 286 dp[0][0][s[1][0] == '1'] = s[1][0] == '1'; 287 dp[0][0][0] = 0; 288 forn(i, n - 1) forn(j, 2){ 289 int nxtj = s[j][i + 1] == '1'; 290 int nxtj1 = s[j ^ 1][i + 1] == '1'; 291 dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1); 292 dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj); 293 dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj); 294 } 295 cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n'; 296 } 297 ``` 298 299 [1739F - Keyboard Design](/contest/1739/problem/F "Educational Codeforces Round 136 (Rated for Div. 2)") 300 301 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 302 303 **Tutorial** 304 305 Tutorial is loading... 306 307 **Solution (BledDest)** 308 309 ``` 310 #include<bits/stdc++.h> 311 312 using namespace std; 313 314 const int N = 10043; 315 const int K = 12; 316 317 int tsz = 0; 318 int trie[N][K]; 319 int aut[N][K]; 320 int lnk[N]; 321 int p[N]; 322 int pchar[N]; 323 int cost[N]; 324 int ncost[N]; 325 326 int newNode() 327 { 328 lnk[tsz] = -1; 329 ncost[tsz] = -1; 330 cost[tsz] = 0; 331 for(int i = 0; i < K; i++) 332 { 333 trie[tsz][i] = aut[tsz][i] = -1; 334 } 335 return tsz++; 336 } 337 338 int nxt(int x, int y) 339 { 340 if(trie[x][y] == -1) 341 { 342 trie[x][y] = newNode(); 343 pchar[trie[x][y]] = y; 344 p[trie[x][y]] = x; 345 } 346 return trie[x][y]; 347 } 348 349 int go(int x, int y); 350 351 int get_lnk(int x) 352 { 353 if(lnk[x] != -1) return lnk[x]; 354 int& d = lnk[x]; 355 if(x == 0 || p[x] == 0) return d = 0; 356 return d = go(get_lnk(p[x]), pchar[x]); 357 } 358 359 int go(int x, int y) 360 { 361 if(aut[x][y] != -1) return aut[x][y]; 362 int& d = aut[x][y]; 363 if(trie[x][y] != -1) return d = trie[x][y]; 364 if(x == 0) return d = 0; 365 return d = go(get_lnk(x), y); 366 } 367 368 void add(string s, int c) 369 { 370 int cur = 0; 371 for(auto x : s) cur = nxt(cur, x - 'a'); 372 cost[cur] += c; 373 } 374 375 int calc(int x) 376 { 377 if(ncost[x] != -1) return ncost[x]; 378 ncost[x] = cost[x]; 379 int y = get_lnk(x); 380 if(y != x) ncost[x] += calc(y); 381 return ncost[x]; 382 } 383 384 int main() 385 { 386 int root = newNode(); 387 int n; 388 cin >> n; 389 for(int i = 0; i < n; i++) 390 { 391 string s; 392 int x; 393 cin >> x >> s; 394 map<char, set<char>> adj; 395 for(int j = 0; j + 1 < s.size(); j++) 396 { 397 adj[s[j]].insert(s[j + 1]); 398 adj[s[j + 1]].insert(s[j]); 399 } 400 bool bad = false; 401 string res = ""; 402 char c; 403 for(c = 'a'; c <= 'l'; c++) 404 { 405 if(!adj.count(c)) continue; 406 if(adj[c].size() >= 3) 407 bad = true; 408 if(adj[c].size() == 1) 409 break; 410 } 411 if(c == 'm' || bad) continue; 412 res.push_back(c); 413 while(adj[c].size() > 0) 414 { 415 char d = *adj[c].begin(); 416 adj[c].erase(d); 417 adj[d].erase(c); 418 c = d; 419 res.push_back(c); 420 } 421 bad |= adj.size() != res.size(); 422 map<char, int> pos; 423 for(int i = 0; i < res.size(); i++) 424 pos[res[i]] = i; 425 for(int i = 0; i + 1 < s.size(); i++) 426 bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1; 427 if(bad) continue; 428 add(res, x); 429 reverse(res.begin(), res.end()); 430 add(res, x); 431 } 432 int INF = 1e9; 433 int K = 12; 434 vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF)); 435 vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1)); 436 dp[0][0] = 0; 437 for(int i = 0; i < (1 << K); i++) 438 for(int j = 0; j <= tsz; j++) 439 { 440 for(int z = 0; z < K; z++) 441 { 442 if(i & (1 << z)) continue; 443 int nstate = go(j, z); 444 int add = calc(nstate); 445 int nmask = i | (1 << z); 446 if(dp[nmask][nstate] < dp[i][j] + add) 447 { 448 dp[nmask][nstate] = dp[i][j] + add; 449 pdp[nmask][nstate] = {z, j}; 450 } 451 } 452 } 453 string ans = ""; 454 int curmask = (1 << K) - 1; 455 int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin(); 456 while(curmask != 0) 457 { 458 int cc = pdp[curmask][curstate].first; 459 int ns = pdp[curmask][curstate].second; 460 ans.push_back(char('a' + cc)); 461 curmask ^= (1 << cc); 462 curstate = ns; 463 } 464 cout << ans << endl; 465 } 466 ```