1994.md (8643B)
1 Source: https://codeforces.com/blog/entry/131666 2 3 Thanks for participation! 4 5 [1994A - Diverse Game](/contest/1994/problem/A) 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 cin.tie(nullptr)->sync_with_stdio(false); 19 20 int tests; 21 cin >> tests; 22 while (tests--) { 23 int n, m; 24 cin >> n >> m; 25 vector<vector<int>> a(n, vector<int>(m)); 26 for (auto &i: a) { 27 for (auto &j: i) cin >> j; 28 } 29 if (n * m == 1) cout << "-1\n"; 30 else { 31 for (int i = 0; i < n; ++i) { 32 for (int j = 0; j < m; ++j) { 33 cout << a[(i + 1) % n][(j + 1) % m] << ' '; 34 } 35 cout << '\n'; 36 } 37 } 38 } 39 } 40 ``` 41 42 [1994B - Fun Game](/contest/1994/problem/B) 43 44 **Editorial** 45 46 Tutorial is loading... 47 48 **Code** 49 50 ``` 51 #include<bits/stdc++.h> 52 using namespace std; 53 54 void solve() { 55 int n; 56 cin >> n; 57 string s, t; 58 cin >> s >> t; 59 for (int i = 0; i < s.size() && s[i] == '0'; ++i) { 60 if (t[i] != '0') { 61 cout << "NO\n"; 62 return; 63 } 64 } 65 cout << "YES\n"; 66 } 67 68 int main() { 69 int t; 70 cin >> t; 71 while (t--) solve(); 72 } 73 ``` 74 75 [1994C - Hungry Games](/contest/1994/problem/C) 76 77 **Editorial** 78 79 Tutorial is loading... 80 81 **Code** 82 83 ``` 84 #include<bits/stdc++.h> 85 using namespace std; 86 87 using ll = long long; 88 89 int main() { 90 cin.tie(nullptr)->sync_with_stdio(false); 91 92 int tests; 93 cin >> tests; 94 while (tests--) { 95 int n; 96 ll x; 97 cin >> n >> x; 98 vector<ll> a(n + 1); 99 for (int i = 1; i <= n; ++i) cin >> a[i]; 100 partial_sum(a.begin() + 1, a.end(), a.begin() + 1); 101 vector<int> dp(n + 2); 102 for (int i = n - 1; i >= 0; --i) { 103 int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin(); 104 dp[i] = dp[q] + q - i - 1; 105 } 106 cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n'; 107 } 108 } 109 ``` 110 111 [1994D - Funny Game](/contest/1994/problem/D) 112 113 **Hint** 114 115 Pigeonhole principle 116 117 **Editorial** 118 119 Tutorial is loading... 120 121 **Code** 122 123 ``` 124 #include<bits/stdc++.h> 125 using namespace std; 126 127 int main() { 128 int tests; 129 cin >> tests; 130 while (tests--) { 131 int n; 132 cin >> n; 133 vector<int> a(n); 134 for (auto& i : a) cin >> i; 135 vector<int> pos(n); 136 iota(pos.begin(), pos.end(), 0); 137 vector<pair<int, int>> ans; 138 for (int i = n - 1; i; --i) { 139 vector<int> occ(i, -1); 140 for (auto j : pos) { 141 if (occ[a[j] % i] != -1) { 142 ans.emplace_back(j, occ[a[j] % i]); 143 pos.erase(find(pos.begin(), pos.end(), j)); 144 break; 145 } 146 occ[a[j] % i] = j; 147 } 148 } 149 reverse(ans.begin(), ans.end()); 150 cout << "YES\n"; 151 for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n'; 152 } 153 } 154 ``` 155 156 [1994E - Wooden Game](/contest/1994/problem/E) 157 158 **Hint** 159 160 Solve for one tree 161 162 **Hint.answer** 163 164 Answer is size of tree 165 166 **Hint.proof** 167 168 Let sizes of deleted subtrees be $a_1, a_2, \ldots a_m$. We know that $a_1 + a_2 + \ldots + a_m = n$. Then we know that $a_1 | a_2 \ldots a_m \leq n$. To proof that lets see bits separately. It will add $1$ to result, if one of bits is $1$, $0$ otherwise, but this is not more than their sum. 169 170 **Editorial** 171 172 Tutorial is loading... 173 174 **Code** 175 176 ``` 177 #include<bits/stdc++.h> 178 using namespace std; 179 180 void solve() { 181 int k; 182 cin >> k; 183 vector<int> a(k); 184 for (int i = 0; i < k; ++i) { 185 cin >> a[i]; 186 for (int j = 0; j < a[i] - 1; ++j) { 187 int trash; 188 cin >> trash; 189 } 190 } 191 sort(a.begin(), a.end(), greater<>()); 192 int ans = 0; 193 for (auto x : a) { 194 for (int h = 23; h >= 0; --h) { 195 int ca = ans >> h & 1, cx = x >> h & 1; 196 if (cx == 0) continue; 197 if (ca == 0) ans |= 1 << h; 198 else { 199 ans |= (1 << h) - 1; 200 break; 201 } 202 } 203 } 204 cout << ans << '\n'; 205 } 206 207 int main() { 208 int t; 209 cin >> t; 210 while (t--) solve(); 211 } 212 ``` 213 214 [1994F - Stardew Valley](/contest/1994/problem/F) 215 216 **Editorial** 217 218 Tutorial is loading... 219 220 **Code** 221 222 ``` 223 #include<bits/stdc++.h> 224 using namespace std; 225 226 int main() { 227 cin.tie(nullptr)->sync_with_stdio(false); 228 229 int tests; 230 cin >> tests; 231 while (tests--) { 232 int n, m; 233 cin >> n >> m; 234 vector<vector<int>> black(n); 235 vector<int> edg(m); 236 vector<vector<int>> g(n); 237 for (int i = 0; i < m; ++i) { 238 int x, y, c; 239 cin >> x >> y >> c; 240 --x, --y; 241 edg[i] = x ^ y; 242 g[x].push_back(i); 243 g[y].push_back(i); 244 if (c == 0) { 245 black[x].push_back(i); 246 black[y].push_back(i); 247 } 248 } 249 vector<int> deg(n); 250 for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1; 251 vector<bool> del(m, false), used(n, false); 252 auto dfs = [&](auto dfs, int u) -> void { 253 used[u] = true; 254 for (auto id : black[u]) { 255 int to = edg[id] ^ u; 256 if (used[to]) continue; 257 dfs(dfs, to); 258 if (deg[to]) { 259 del[id] = true; 260 deg[to] ^= 1; 261 deg[u] ^= 1; 262 } 263 } 264 }; 265 bool ok = true; 266 for (int i = 0; i < n; ++i) { 267 if (used[i]) continue; 268 dfs(dfs, i); 269 ok &= !deg[i]; 270 } 271 if (!ok) { 272 cout << "NO\n"; 273 continue; 274 } 275 auto euler = [&](auto euler, int u) -> void { 276 while (!g[u].empty()) { 277 int id = g[u].back(); 278 g[u].pop_back(); 279 int to = edg[id] ^ u; 280 if (del[id]) continue; 281 del[id] = true; 282 euler(euler, to); 283 } 284 cout << u + 1 << ' '; 285 }; 286 cout << "YES\n"; 287 cout << m - accumulate(del.begin(), del.end(), 0) << '\n'; 288 euler(euler, 0); 289 cout << '\n'; 290 } 291 } 292 ``` 293 294 [1994G - Minecraft](/contest/1994/problem/G) 295 296 **Hint 1** 297 298 Think of the most stupid solution you can do 299 300 **Hint 2** 301 302 Do memorization and some cuts 303 304 **Hint 3** 305 306 Done! 307 308 **Editorial** 309 310 Tutorial is loading... 311 312 **Code** 313 314 ``` 315 #include <bits/stdc++.h> 316 317 using namespace std; 318 319 int n, k; 320 vector<vector<bool>> memo; 321 string res; 322 vector<int> cnt; 323 string s; 324 325 bool rec(int i, int cur) { 326 if (i == k) { 327 if (cur == 0) { 328 return true; 329 } 330 return false; 331 } 332 if (memo[i][cur]) return false; 333 memo[i][cur] = true; 334 for (int c = 0; c < 2; ++c) { 335 int q = cur; 336 if (c == 0) q += cnt[i]; 337 else q += n - cnt[i]; 338 if ((q & 1) == s[i] - '0') { 339 if (rec(i + 1, q / 2)) { 340 res += char(c + '0'); 341 return true; 342 } 343 } 344 } 345 return false; 346 } 347 348 int main() { 349 cin.tie(nullptr)->sync_with_stdio(false); 350 351 int tests; 352 cin >> tests; 353 while (tests--) { 354 cin >> n >> k; 355 cin >> s; 356 reverse(s.begin(), s.end()); 357 cnt = vector<int>(k); 358 for (int i = 0; i < n; ++i) { 359 string t; 360 cin >> t; 361 reverse(t.begin(), t.end()); 362 for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0'; 363 } 364 memo = vector<vector<bool>>(k, vector<bool>(n, false)); 365 res = ""; 366 rec(0, 0); 367 if (res.empty()) cout << "-1\n"; 368 else cout << res << '\n'; 369 } 370 } 371 ``` 372 373 [1994H - Fortnite](/contest/1994/problem/H) 374 375 **Editorial** 376 377 Tutorial is loading... 378 379 **Code** 380 381 ``` 382 #include <bits/stdc++.h> 383 using namespace std; 384 385 using ll = long long; 386 387 void solve() { 388 cout << "? aa" << endl; 389 int p, v[10]; 390 cin >> p; p--; 391 cout << "? zzzzzzzzzz" << endl; 392 int hsh, hsho; 393 ll nom = 0, cnt = 1; 394 cin >> hsh; 395 hsho = hsh; 396 hsh++; 397 for (int i = 0; i < 10; i++) { 398 nom += 26 * cnt; 399 cnt *= p; 400 v[i] = 26 - (hsh % p); 401 hsh /= p; 402 } 403 string s; 404 cnt = 1; 405 ll ch = 0; 406 for (int i = 0; i < 10; i++) { 407 if (v[i] < 1) { 408 v[i] = 26; 409 v[i + 1]--; 410 } 411 ch += cnt * v[i]; 412 cnt *= p; 413 s += 'a' + (v[i] - 1); 414 } 415 cout << "? " << s << endl; 416 int ans; 417 cin >> ans; 418 cout << "! " << p << ' ' << ans + nom - ch - hsho << endl; 419 } 420 421 int32_t main() { 422 int t; 423 cin >> t; 424 while (t--) { 425 solve(); 426 } 427 } 428 ```