1657.md (7055B)
1 Source: https://codeforces.com/blog/entry/101161 2 3 [1657A - Integer Moves](/contest/1657/problem/A "Educational Codeforces Round 125 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int x, y; 23 cin >> x >> y; 24 int d = x * x + y * y; 25 int r = 0; 26 while (r * r < d) ++r; 27 int ans = 2; 28 if (r * r == d) ans = 1; 29 if (x == 0 && y == 0) ans = 0; 30 cout << ans << '\n'; 31 } 32 } 33 ``` 34 35 [1657B - XY Sequence](/contest/1657/problem/B "Educational Codeforces Round 125 (Rated for Div. 2)") 36 37 Idea: [adedalic](/profile/adedalic "International Master adedalic") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (adedalic)** 44 45 ``` 46 fun main() { 47 repeat(readLine()!!.toInt()) { 48 val (n, B, x, y) = readLine()!!.split(' ').map { it.toInt() } 49 var cur = 0L 50 var ans = 0L 51 for (i in 1..n) { 52 cur += if (cur + x <= B) x else -y 53 ans += cur 54 } 55 println(ans) 56 } 57 } 58 ``` 59 60 [1657C - Bracket Sequence Deletion](/contest/1657/problem/C "Educational Codeforces Round 125 (Rated for Div. 2)") 61 62 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (vovuh)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 using namespace std; 74 75 int main() { 76 #ifdef _DEBUG 77 freopen("input.txt", "r", stdin); 78 // freopen("output.txt", "w", stdout); 79 #endif 80 81 int t; 82 cin >> t; 83 while (t--) { 84 int n; 85 string s; 86 cin >> n >> s; 87 int l = 0; 88 int cnt = 0; 89 while (l + 1 < n) { 90 if (s[l] == '(' || (s[l] == ')' && s[l + 1] == ')')) { 91 l += 2; 92 } else { 93 int r = l + 1; 94 while (r < n && s[r] != ')') { 95 ++r; 96 } 97 if (r == n) { 98 break; 99 } 100 l = r + 1; 101 } 102 ++cnt; 103 } 104 cout << cnt << ' ' << n - l << '\n'; 105 } 106 107 return 0; 108 } 109 ``` 110 111 [1657D - For Gamers. By Gamers.](/contest/1657/problem/D "Educational Codeforces Round 125 (Rated for Div. 2)") 112 113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution (awoo)** 120 121 ``` 122 #include <bits/stdc++.h> 123 124 using namespace std; 125 126 #define forn(i, n) for (int i = 0; i < int(n); ++i) 127 128 int main(){ 129 int n, C; 130 scanf("%d%d", &n, &C); 131 vector<long long> bst(C + 1); 132 forn(i, n){ 133 int c, d, h; 134 scanf("%d%d%d", &c, &d, &h); 135 bst[c] = max(bst[c], d * 1ll * h); 136 } 137 for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c) 138 bst[xc] = max(bst[xc], bst[c] * (xc / c)); 139 forn(c, C) 140 bst[c + 1] = max(bst[c + 1], bst[c]); 141 int m; 142 scanf("%d", &m); 143 forn(j, m){ 144 int D; 145 long long H; 146 scanf("%d%lld", &D, &H); 147 int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin(); 148 if (mn > C) mn = -1; 149 printf("%d ", mn); 150 } 151 puts(""); 152 } 153 ``` 154 155 [1657E - Star MST](/contest/1657/problem/E "Educational Codeforces Round 125 (Rated for Div. 2)") 156 157 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 158 159 **Tutorial** 160 161 Tutorial is loading... 162 163 **Solution (awoo)** 164 165 ``` 166 #include <bits/stdc++.h> 167 168 using namespace std; 169 170 #define forn(i, n) for (int i = 0; i < int(n); ++i) 171 172 const int MOD = 998244353; 173 174 int add(int a, int b){ 175 a += b; 176 if (a >= MOD) 177 a -= MOD; 178 return a; 179 } 180 181 int mul(int a, int b){ 182 return a * 1ll * b % MOD; 183 } 184 185 int binpow(int a, int b){ 186 int res = 1; 187 while (b){ 188 if (b & 1) 189 res = mul(res, a); 190 a = mul(a, a); 191 b >>= 1; 192 } 193 return res; 194 } 195 196 int main(){ 197 int n, k; 198 scanf("%d%d", &n, &k); 199 --n; 200 vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0)); 201 vector<vector<int>> C(n + 1); 202 forn(i, n + 1){ 203 C[i].resize(i + 1); 204 C[i][0] = C[i][i] = 1; 205 for (int j = 1; j < i; ++j) 206 C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); 207 } 208 dp[0][0] = 1; 209 forn(i, k) forn(t, n + 1) { 210 int pw = binpow(k - i, t * (t - 1) / 2); 211 int step = binpow(k - i, t); 212 forn(j, n - t + 1){ 213 dp[i + 1][j + t] = add(dp[i + 1][j + t], mul(dp[i][j], mul(C[n - j][t], pw))); 214 pw = mul(pw, step); 215 } 216 } 217 printf("%d\n", dp[k][n]); 218 } 219 ``` 220 221 [1657F - Words on Tree](/contest/1657/problem/F "Educational Codeforces Round 125 (Rated for Div. 2)") 222 223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 224 225 **Tutorial** 226 227 Tutorial is loading... 228 229 **Solution (awoo)** 230 231 ``` 232 #include <bits/stdc++.h> 233 234 using namespace std; 235 236 #define forn(i, n) for (int i = 0; i < int(n); ++i) 237 238 vector<vector<int>> t; 239 vector<int> p, h; 240 241 void init(int v){ 242 for (int u : t[v]) if (u != p[v]){ 243 p[u] = v; 244 h[u] = h[v] + 1; 245 init(u); 246 } 247 } 248 249 vector<int> get_path(int v, int u){ 250 vector<int> l, r; 251 while (v != u){ 252 if (h[v] > h[u]){ 253 l.push_back(v); 254 v = p[v]; 255 } 256 else{ 257 r.push_back(u); 258 u = p[u]; 259 } 260 } 261 l.push_back(v); 262 while (!r.empty()){ 263 l.push_back(r.back()); 264 r.pop_back(); 265 } 266 return l; 267 } 268 269 vector<vector<int>> g, tg; 270 271 void add_edge(int v, bool vx, int u, bool vy){ 272 // (val[v] == vx) -> (val[u] == vy) 273 g[v * 2 + vx].push_back(u * 2 + vy); 274 tg[u * 2 + vy].push_back(v * 2 + vx); 275 g[u * 2 + !vy].push_back(v * 2 + !vx); 276 tg[v * 2 + !vx].push_back(u * 2 + !vy); 277 } 278 279 vector<int> ord; 280 vector<char> used; 281 282 void ts(int v){ 283 used[v] = true; 284 for (int u : g[v]) if (!used[u]) 285 ts(u); 286 ord.push_back(v); 287 } 288 289 vector<int> clr; 290 int k; 291 292 void dfs(int v){ 293 clr[v] = k; 294 for (int u : tg[v]) if (clr[u] == -1) 295 dfs(u); 296 } 297 298 int main(){ 299 cin.tie(0); 300 iostream::sync_with_stdio(false); 301 302 int n, m; 303 cin >> n >> m; 304 t.resize(n); 305 p.resize(n); 306 h.resize(n); 307 p[0] = -1; 308 forn(i, n - 1){ 309 int v, u; 310 cin >> v >> u; 311 --v, --u; 312 t[v].push_back(u); 313 t[u].push_back(v); 314 } 315 init(0); 316 317 vector<vector<int>> paths(m); 318 vector<string> s(m); 319 320 vector<pair<char, char>> opts(n, make_pair(-1, -1)); 321 forn(i, m){ 322 int v, u; 323 cin >> v >> u >> s[i]; 324 --v, --u; 325 paths[i] = get_path(v, u); 326 int k = s[i].size(); 327 assert(int(paths[i].size()) == k); 328 forn(j, k) opts[paths[i][j]] = {s[i][j], s[i][k - j - 1]}; 329 } 330 331 int nm = (n + m) * 2; 332 g.resize(nm); 333 tg.resize(nm); 334 forn(i, m){ 335 int k = s[i].size(); 336 forn(j, k){ 337 int v = paths[i][j]; 338 char c = s[i][j], rc = s[i][k - j - 1]; 339 char d = opts[v].first, rd = opts[v].second; 340 if (d != c) add_edge(v, false, n + i, true); 341 if (d != rc) add_edge(v, false, n + i, false); 342 if (rd != c) add_edge(v, true, n + i, true); 343 if (rd != rc) add_edge(v, true, n + i, false); 344 } 345 } 346 347 used.resize(nm); 348 forn(i, nm) if (!used[i]) ts(i); 349 clr.resize(nm, -1); 350 reverse(ord.begin(), ord.end()); 351 for (int v : ord) if (clr[v] == -1){ 352 dfs(v); 353 ++k; 354 } 355 forn(i, nm) if (clr[i] == clr[i ^ 1]){ 356 cout << "NO\n"; 357 return 0; 358 } 359 360 cout << "YES\n"; 361 for (int i = 0; i < 2 * n; i += 2){ 362 if (opts[i / 2].first == -1) 363 cout << 'a'; 364 else if (clr[i] > clr[i ^ 1]) 365 cout << opts[i / 2].first; 366 else 367 cout << opts[i / 2].second; 368 } 369 cout << "\n"; 370 } 371 ```