1737.md (11603B)
1 Source: https://codeforces.com/blog/entry/107567 2 3 > It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today! 4 5 ## [1737A - Ela Sorting Books](/contest/1737/problem/A "Dytechlab Cup 2022") 6 7 Author: [low_](/profile/low_ "Master low_") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution snippet ( low_ C++)** 14 15 ``` 16 ... 17 void execute(int test_number) 18 { 19 cin>>n>>k>>str; 20 vector <int> count_char(26, 0); 21 for (char c: str) count_char[c - 'a']++; 22 string ans = ""; 23 for (int i = 0; i < min(25, n/k); i++) { 24 while (k - ans.size() > count_char[i]) { 25 ans.push_back(i + 'a'); 26 } 27 } 28 29 char c = 'a' + min(n / k, 25); 30 while (k > ans.size()) { 31 ans += c; 32 } 33 reverse(ans.begin(), ans.end()); 34 cout << ans << "\n"; 35 } 36 ... 37 ``` 38 39 ## [1737B - Ela's Fitness and the Luxury Number](/contest/1737/problem/B "Dytechlab Cup 2022") 40 41 Author: [low_](/profile/low_ "Master low_") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution snippet (low_, C++)** 48 49 ``` 50 ... 51 ll l, r; 52 53 ll bs_sqrt(ll x) { 54 ll left = 0, right = 2000000123; 55 while (right > left) { 56 ll mid = (left + right) / 2; 57 58 if (mid * mid > x) right = mid; 59 else left = mid + 1; 60 } 61 return left - 1; 62 } 63 64 // main solution goes here: 65 void execute(int test_number) 66 { 67 cin >> l >> r; 68 ll sql = bs_sqrt(l), sqr = bs_sqrt(r); 69 ll ans; 70 if (sql == sqr) { 71 ans = 0; 72 for (int i = 0; i < 3; i++) { 73 if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++; 74 } 75 } else { 76 ans = (sqr - sql - 1) * 3; 77 for (int i = 0; i < 3; i++) { 78 if (l <= sql * (sql + i) && sql * (sql + i) <= r) ans++; 79 if (l <= sqr * (sqr + i) && sqr * (sqr + i) <= r) ans++; 80 } 81 } 82 cout << ans << "\n"; 83 } 84 ... 85 ``` 86 87 ## [1737C - Ela and Crickets](/contest/1737/problem/C "Dytechlab Cup 2022") 88 89 Author: [low_](/profile/low_ "Master low_") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution snippet (low_, C++)** 96 97 ``` 98 ... 99 int n; 100 int x[3], y[3]; 101 int u, v; 102 103 pii centralSquare() { 104 int a = (x[0] == x[1]) ? x[0] : x[2]; 105 int b = (y[0] == y[1]) ? y[0] : y[2]; 106 return {a, b}; 107 } 108 // main solution goes here: 109 void execute(int test_number) 110 { 111 cin>>n; 112 for (int i=0; i<3; i++) cin>>x[i]>>y[i]; 113 cin>>u>>v; 114 115 int cx = centralSquare().first, cy = centralSquare().second; 116 117 if ((cx == 1 || cx == n) && (cy == 1 || cy == n)) { // "corner" case, literally 118 // the crickets can only reach coordinates within the edges that already contains at least 2 crickets, 119 // which contains the centralSquare of the L 120 cout << ((u == cx || v == cy) ? "YES\n" : "NO\n"); 121 } else { 122 if ((cx + cy) % 2 == (u + v) % 2) { 123 cout << (cx % 2 == u % 2 ? "YES\n" : "NO\n"); 124 } else { // can be prove to always reach, since we have ways to align 2 crickets in the same diagonal as target 125 cout << "YES\n"; 126 } 127 } 128 } 129 ... 130 ``` 131 132 ## [1737D - Ela and the Wiring Wizard](/contest/1737/problem/D "Dytechlab Cup 2022") 133 134 Author: [low_](/profile/low_ "Master low_") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution (magnified, C++)** 141 142 ``` 143 #include <bits/stdc++.h> 144 #define ll long long 145 #define db long double 146 #define ull unsigned long long 147 #define x first 148 #define y second 149 #define mp make_pair 150 #define pb push_back 151 #define all(a) a.begin(), a.end() 152 153 using namespace std; 154 155 #define pper(a) cerr << #a << " = " << a << endl; 156 157 void per() { cerr << endl; } 158 template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); } 159 160 template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; } 161 template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; } 162 163 template<class U, class V> 164 ostream& operator<<(ostream& out, const pair<U, V>& a) { 165 return out << "(" << a.x << ", " << a.y << ")"; 166 } 167 168 template<class U, class V> 169 istream& operator>>(istream& in, pair<U, V>& a) { 170 return in >> a.x >> a.y; 171 } 172 173 template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type> 174 ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; } 175 176 template<class T> 177 void readArr(T from, T to) { 178 for (auto i = from; i != to; ++i) cin >> *i; 179 } 180 181 mt19937 mrand(1337); 182 unsigned int myRand32() { 183 return mrand() & (unsigned int)(-1); 184 } 185 186 unsigned ll myRand64() { 187 return ((ull)myRand32() << 32) ^ myRand32(); 188 } 189 190 const int mod = 1000000007; 191 192 void add(int& a, int b) { 193 a += b; if (a >= mod) a -= mod; 194 } 195 196 void dec(int &a, int b) { 197 a -= b; if (a < 0) a += mod; 198 } 199 200 int mult(int a, int b) { 201 return a * (ll)b % mod; 202 } 203 204 int bp(int a, int b) { 205 int res = 1; 206 while (b > 0) { 207 if (b & 1) res = mult(res, a); 208 a = mult(a, a); 209 b >>= 1; 210 } 211 return res; 212 } 213 214 const int N = 507; 215 216 ll f[N][N]; 217 218 int main(){ 219 #ifdef LOCAL 220 freopen("N_input.txt", "r", stdin); 221 //freopen("N_output.txt", "w", stdout); 222 #endif 223 ios_base::sync_with_stdio(0); 224 cin.tie(0); 225 226 int t; 227 cin >> t; 228 229 for (int a = 0; a < t; ++a) { 230 231 int n, m; 232 cin >> n >> m; 233 234 for (int i = 0; i < n; ++i) { 235 for (int j = 0; j < n; ++j) { 236 f[i][j] = 1e18; 237 } 238 f[i][i] = 0; 239 } 240 241 vector<tuple<int, int, int> > ed; 242 243 for (int i = 0; i < m; ++i) { 244 int u, v, w; 245 cin >> u >> v >> w; 246 ed.pb(make_tuple(u - 1, v - 1, w)); 247 f[u - 1][v - 1] = 1; 248 f[v - 1][u - 1] = 1; 249 } 250 251 for (int k = 0; k < n; ++k) { 252 for (int i = 0; i < n; ++i) { 253 for (int j = 0; j < n; ++j) { 254 f[i][j] = min(f[i][j], f[i][k] + f[k][j]); 255 } 256 } 257 } 258 259 ll ans = 1e18; 260 for (auto x : ed) { 261 int u = get<0>(x); 262 int v = get<1>(x); 263 int w = get<2>(x); 264 265 // per(ans, u, v, w); 266 267 ans = min(ans, (ll) w * (f[0][u] + f[n - 1][v] + 1)); 268 ans = min(ans, (ll) w * (f[0][v] + f[n - 1][u] + 1)); 269 270 // per(ans, u, v, w); 271 272 for (int i = 0; i < n; ++i) { 273 ans = min(ans, (ll) w * (f[v][i] + 1 + f[i][0] + f[i][n-1] + 1)); 274 ans = min(ans, (ll) w * (f[u][i] + 1 + f[i][0] + f[i][n-1] + 1)); 275 } 276 277 } 278 279 cout << ans << '\n'; 280 281 } 282 } 283 ``` 284 285 ## [1737E - Ela Goes Hiking](/contest/1737/problem/E "Dytechlab Cup 2022") 286 287 Author: [ngfam_kongu](/profile/ngfam_kongu "Master ngfam_kongu") 288 289 **Tutorial** 290 291 Tutorial is loading... 292 293 **Solution snippet (low_, C++)** 294 295 ``` 296 ... 297 // data preprocessing: (e.g.: divisor generating, prime sieve) 298 ll POW2[mn]; 299 void preprocess() 300 { 301 POW2[0] = 1; 302 for (int i = 1; i < mn; i++) POW2[i] = POW2[i — 1] * 2 % mod; 303 } 304 305 // global variables: 306 ll n; 307 308 ll POW(ll u, ll v) { 309 if (v == 0) return 1; 310 ll mid = POW(u, v / 2); 311 mid = (mid * mid) % mod; 312 return (v & 1) ? (mid * u % mod) : mid; 313 } 314 // main solution goes here: 315 void execute(int test_number) 316 { 317 cin>>n; 318 319 if (n == 1) { 320 cout << "1\n"; 321 return; 322 } 323 vector <ll> ans(n + 1, 0), sufsum(n + 1, 0); 324 sufsum[n] = ans[n] = POW(POW2[(n — 1) / 2], mod — 2); 325 for (int i = n — 1; i > 1; i--) { 326 ans[i] = POW(POW2[(i + 1) / 2], mod — 2); 327 if (2 * i <= n) ans[i] = ans[i] * (1 — sufsum[i * 2] + mod) % mod; 328 sufsum[i] = (sufsum[i + 1] + ans[i]) % mod; 329 } 330 for (int i = 1; i <= n; i++) cout << ans[i] << "\n"; 331 332 } 333 ... 334 ``` 335 336 ## [1737F - Ela and Prime GCD](/contest/1737/problem/F "Dytechlab Cup 2022") 337 338 Author: [055D](/profile/055D "Master 055D") 339 340 **Tutorial** 341 342 Observation: Assume that x is composite number and divisor of n. Among all the multiples of x, the number of the divisor of n must be less than or equal to m/2. 343 344 First, factorize n. Assume that w is divisor of n. If w is in the form of a^4, a^3b^2, or a^2b^2c^2, it can be proved that there is no answer. Otherwise, there can be two cases. 345 346 If the possible maximum exponent of prime factor is 2, place the divisors like this: 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a. And expand the sequence as follows: 347 348 1. Repeat the current sequence twice — 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a 1 a^2b^2 b a^2b b^2 ab a^2 ab^2 a / 1 a^2 a 1 a^2 a. 349 2. Multiply the odd-indexed elements of first half and the even-indexed elements of second half by the new prime factor. Index 1 is exception — 1 a^2b^2 bc a^2b b^2c ab a^2c ab^2 ac c a^2b^2c b a^2bc b^2 abc a^2 ab^2c a / 1 a^2 ab b a^2b a. 350 3. If more prime factor exists, jump to "Otherwise". 351 352 Otherwise, place the divisors like this: 1 a^3 a a^2 / 1 a. Now the exponents of other prime factors are all 1, and we can expand the sequence as follows: 353 354 1. Repeat the current sequence twice — 1 a^3 a a^2 1 a^3 a a^2 / 1 a 1 a. 355 2. Multiply the even-indexed elements of first half and the odd-indexed elements of second half by the new prime factor — 1 a^3b a a^2b b a^3 ab a^2 / 1 ab b a. 3-1. If the maximum exponent is 3, swap a and b — 1 a^3b b a^2b a a^3 ab a^2 3-2. Otherwise, swap b and ab — 1 b ab a. 356 357 Like this, we can expand the sequence 358 359 **Solution (C++)** 360 361 ``` 362 #import<bits/stdc++.h> 363 #define endl '\n' 364 using namespace std; 365 366 int m, t, b[18], check[18], cnt[5]; 367 vector<int>v; 368 vector<vector<int>>a; 369 370 void initialize(int m) 371 { 372 fill(b, b + m + 1, 0); 373 fill(check, check + m + 1, 0); 374 fill(cnt, cnt + 5, 0); 375 v.clear(); 376 a.clear(); 377 } 378 void insert1(int p1, int c1) 379 { 380 v[p1] = c1; 381 a.push_back(v); 382 } 383 void insert2(int p1, int p2, int c1, int c2) 384 { 385 v[p1] = c1; 386 v[p2] = c2; 387 a.push_back(v); 388 } 389 390 void f1(int x) 391 { 392 int n = a.size(); 393 for(int i = 0; i < n; i++)a.push_back(a[i]); 394 for(int i = 0; i < n; i += 2) 395 { 396 a[i + 1][x] = 1; 397 a[i + n][x] = 1; 398 } 399 swap(a[n / 2], a[n]); 400 } 401 void f2(int x) 402 { 403 int n = a.size(); 404 for(int i = 0; i < n; i++)a.push_back(a[i]); 405 for(int i = 1; i < n; i += 2) 406 { 407 a[i + 1][x] = 1; 408 a[i + n][x] = 1; 409 } 410 a[n][x] = 1; 411 } 412 void f3(int x) 413 { 414 int n = a.size(); 415 for(int i = 0; i < n; i++)a.push_back(a[i]); 416 for(int i = 0; i < n; i += 2) 417 { 418 a[i + 1][x] = 1; 419 a[i + n][x] = 1; 420 } 421 swap(a[n], a[2 * n — 1]); 422 } 423 424 int main() 425 { 426 ios::sync_with_stdio(0); 427 cin.tie(0); 428 for(cin >> t; t--;) 429 { 430 cin >> m; 431 for(int i = 1; i <= m; i++) 432 { 433 cin >> b[i]; 434 cnt[min(b[i], 4)]++; 435 } 436 if(cnt[4] || cnt[3] >= 2 || cnt[3] && cnt[2] || cnt[2] >= 3) 437 { 438 cout << -1 << endl; 439 initialize(m); 440 continue; 441 } 442 443 for(int i = 1; i <= m; i++)v.push_back(0); 444 a.push_back(v); 445 446 if(cnt[2]) 447 { 448 int p1 = -1, p2 = -1; 449 for(int i = 1; i <= m; i++) 450 { 451 if(b[i] == 2) 452 { 453 if(~p1)p2 = i - 1; 454 else p1 = i - 1; 455 } 456 } 457 if(~p2) 458 { 459 insert2(p1, p2, 2, 2); 460 insert2(p1, p2, 0, 1); 461 insert2(p1, p2, 2, 1); 462 insert2(p1, p2, 0, 2); 463 insert2(p1, p2, 1, 1); 464 insert2(p1, p2, 2, 0); 465 insert2(p1, p2, 1, 2); 466 insert2(p1, p2, 1, 0); 467 check[p1 + 1] = check[p2 + 1] = 1; 468 } 469 else 470 { 471 insert1(p1, 2); 472 insert1(p1, 1); 473 check[p1 + 1] = 1; 474 } 475 for(int i = 1; i <= m; i++) 476 { 477 if(check[i])continue; 478 if(a.size() % 2)f2(i - 1); 479 else f3(i - 1); 480 } 481 } 482 else 483 { 484 if(cnt[3]) 485 { 486 int p = 0; 487 for(int i = 1; i <= m; i++) 488 { 489 if(b[i] == 3)p = i - 1; 490 } 491 insert1(p, 3); 492 insert1(p, 1); 493 insert1(p, 2); 494 check[p + 1] = 1; 495 } 496 else 497 { 498 insert1(0, 1); 499 check[1] = 1; 500 } 501 for(int i = 1; i <= m; i++) 502 { 503 if(!check[i])f1(i - 1); 504 } 505 } 506 507 for(auto &v: a) 508 { 509 if(*max_element(v.begin(), v.end())) 510 { 511 for(auto &p: v)cout << p << ' '; 512 cout << endl; 513 } 514 } 515 initialize(m); 516 } 517 } 518 ``` 519 520 ## [1737G - Ela Takes Dancing Class](/contest/1737/problem/G "Dytechlab Cup 2022") 521 522 Author: [magnified](/profile/magnified "Master magnified") 523 524 **Tutorial** 525 526 Tutorial is loading... 527 528 **Solution (C++)** 529 530 [175061586](/contest/1737/submission/175061586 "Submission 175061586 by magnified")