codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2233.md (16900B)


      1 Source: https://codeforces.com/blog/entry/154371
      2 
      3 Thank you for participating! I hope you enjoyed the problems.
      4 
      5 [2233A - AI Project Development](/contest/2233/problem/A "Educational Codeforces Round 191 (Rated for Div. 2)")
      6 
      7 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution (FelixArg)**
     14 
     15 ```
     16 #include<bits/stdc++.h>
     17  
     18 using namespace std;
     19  
     20 #define int long long
     21  
     22 int int_ceil(int x, int d){
     23 	return (x + d - 1) / d;
     24 }
     25  
     26 void solve(){
     27 	int n, x, y, t;
     28 	cin >> n >> x >> y >> t;
     29 	int ans = int_ceil(n, x + y);
     30 	if (t * x <= n){
     31 		ans = min(ans, int_ceil(n - t * x, x + 10 * y) + t);
     32 	}
     33 	cout << ans << '\n';
     34 }
     35  
     36 signed main()
     37 {
     38 #ifdef FELIX
     39 	auto _clock_start = chrono::high_resolution_clock::now();
     40 #endif
     41 	ios_base::sync_with_stdio(false);
     42 	cin.tie(0);
     43 	cout.tie(0);
     44  
     45 	int tests = 1;
     46 	cin >> tests;
     47 	while(tests--){
     48 		solve();
     49 	}
     50  
     51 #ifdef FELIX
     52 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
     53 		chrono::high_resolution_clock::now()
     54 			- _clock_start).count() << "ms." << endl;
     55 #endif
     56 	return 0;
     57 }
     58 ```
     59 
     60 **Rate the problem**
     61 
     62 Amazing
     63 
     64 Good
     65 
     66 Ok
     67 
     68 Bad
     69 
     70 Terrible
     71 
     72 [2233B - Different Distances](/contest/2233/problem/B "Educational Codeforces Round 191 (Rated for Div. 2)")
     73 
     74 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution 1 (FelixArg)**
     81 
     82 ```
     83 #include<bits/stdc++.h>
     84  
     85 using namespace std;
     86  
     87 #define int long long
     88  
     89 void solve(){
     90 	int n;
     91 	cin >> n;
     92 	if (n % 2 == 0){
     93 		for (int i = 0; i < n; i += 2){
     94 			cout << (i + 2) << ' ' << (i + 1) << ' ' << (i + 1) << ' ' << (i + 2) << ' ';
     95 			cout << (i + 1) << ' ' << (i + 2) << ' ' << (i + 2) << ' ' << (i + 1) << ' ';
     96 		}
     97 	}
     98 	else{
     99 		cout << "3 3 2 1 1 2 1 2 2 3 1 3 ";
    100 		for (int i = 3; i < n; i += 2){
    101 			cout << (i + 2) << ' ' << (i + 1) << ' ' << (i + 1) << ' ' << (i + 2) << ' ';
    102 			cout << (i + 1) << ' ' << (i + 2) << ' ' << (i + 2) << ' ' << (i + 1) << ' ';
    103 		}
    104 	}
    105 	cout << '\n';
    106 }
    107  
    108 signed main()
    109 {
    110 #ifdef FELIX
    111 	auto _clock_start = chrono::high_resolution_clock::now();
    112 #endif
    113 	ios_base::sync_with_stdio(false);
    114 	cin.tie(0);
    115 	cout.tie(0);
    116  
    117 	int tests = 1;
    118 	cin >> tests;
    119 	while(tests--){
    120 		solve();
    121 	}
    122  
    123 #ifdef FELIX
    124 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    125 		chrono::high_resolution_clock::now()
    126 			- _clock_start).count() << "ms." << endl;
    127 #endif
    128 	return 0;
    129 }
    130 ```
    131 
    132 **Solution 2 (FelixArg)**
    133 
    134 ```
    135 #include<bits/stdc++.h>
    136  
    137 using namespace std;
    138 
    139 mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
    140  
    141 #define int long long
    142 
    143 bool check(vector<int> &a){
    144 	int n = a.size() / 4;
    145 	vector<vector<int>> p(n);
    146    
    147 	for (int i = 0; i < 4 * n; i++){
    148 	  p[a[i]].push_back(i);
    149 	}
    150 	for (int i = 0; i < n; i++){
    151 	  if (p[i].size() != 4){
    152 		return false;
    153 	  }
    154 	  if (p[i][1] - p[i][0] == p[i][2] - p[i][1] || 
    155 		  p[i][3] - p[i][2] == p[i][2] - p[i][1] || 
    156 		  p[i][3] - p[i][2] == p[i][1] - p[i][0]){
    157 		return false;
    158 	  }
    159 	}
    160 	return true;
    161   }
    162  
    163 void solve(){
    164 	int n;
    165 	cin >> n;
    166 	vector<int> a;
    167 	for (int i = 0; i < n; i++){
    168 		for (int j = 0; j < 4; j++){
    169 			a.push_back(i);
    170 		}
    171 	}
    172 	while(!check(a)){
    173 		shuffle(a.begin(), a.end(), rng);
    174 	}
    175 	for (int x : a){
    176 		cout << x + 1 << ' ';
    177 	}
    178 	cout << '\n';
    179 }
    180  
    181 signed main()
    182 {
    183 #ifdef FELIX
    184 	auto _clock_start = chrono::high_resolution_clock::now();
    185 #endif
    186 	ios_base::sync_with_stdio(false);
    187 	cin.tie(0);
    188 	cout.tie(0);
    189  
    190 	int tests = 1;
    191 	cin >> tests;
    192 	while(tests--){
    193 		solve();
    194 	}
    195  
    196 #ifdef FELIX
    197 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    198 		chrono::high_resolution_clock::now()
    199 			- _clock_start).count() << "ms." << endl;
    200 #endif
    201 	return 0;
    202 }
    203 ```
    204 
    205 **Rate the problem**
    206 
    207 Amazing
    208 
    209 Good
    210 
    211 Ok
    212 
    213 Bad
    214 
    215 Terrible
    216 
    217 [2233C - Cost of a Bracket Sequence](/contest/2233/problem/C "Educational Codeforces Round 191 (Rated for Div. 2)")
    218 
    219 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    220 
    221 **Tutorial**
    222 
    223 Tutorial is loading...
    224 
    225 **Solution 1 (FelixArg)**
    226 
    227 ```
    228 #include<bits/stdc++.h>
    229  
    230 using namespace std;
    231  
    232 #define int long long
    233  
    234 const int INF = 1000000007;
    235  
    236 void solve(){
    237 	int n, k;
    238 	cin >> n >> k;
    239 	string s;
    240 	cin >> s;
    241  
    242 	int val_ans = INF;
    243 	string ans(n, '0');
    244  
    245 	for (int i = 0; i <= n; i++){
    246 		string t = s;
    247 		string cur_ans(n, '0');
    248 		int cur_k = k;
    249  
    250 		for (int j = 0; j < i; j++){
    251 			if (t[j] == '(' && cur_k > 0){
    252 				cur_ans[j] = '1';
    253 				t[j] = ')';
    254 				cur_k--;
    255 			}
    256 		}
    257 		for (int j = n - 1; j > i; j--){
    258 			if (t[j] == ')' && cur_k > 0){
    259 				cur_ans[j] = '1';
    260 				t[j] = '(';
    261 				cur_k--;
    262 			}
    263 		}
    264 		int val_cur = 0;
    265 		int bal = 0;
    266 		for (int j = 0; j < n; j++){
    267 			if (bal > 0 && t[j] == ')'){
    268 				val_cur += 2;
    269 				bal--;
    270 			}
    271 			else if (t[j] == '('){
    272 				bal++;
    273 			}
    274 		}
    275 		if (val_ans > val_cur){
    276 			val_ans = val_cur;
    277 			ans = cur_ans;
    278 		}
    279 	}
    280  
    281 	cout << ans << '\n';
    282 }
    283  
    284 signed main()
    285 {
    286 #ifdef FELIX
    287 	auto _clock_start = chrono::high_resolution_clock::now();
    288 #endif
    289 	ios_base::sync_with_stdio(false);
    290 	cin.tie(0);
    291 	cout.tie(0);
    292  
    293 	int tests = 1;
    294 	cin >> tests;
    295 	while(tests--){
    296 		solve();
    297 	}
    298  
    299 #ifdef FELIX
    300 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    301 		chrono::high_resolution_clock::now()
    302 			- _clock_start).count() << "ms." << endl;
    303 #endif
    304 	return 0;
    305 }
    306 ```
    307 
    308 **Solution 2 (FelixArg)**
    309 
    310 ```
    311 #include<bits/stdc++.h>
    312  
    313 using namespace std;
    314  
    315 #define int long long
    316  
    317 const int INF = 1000000007;
    318  
    319 void solve(){
    320 	int n, k;
    321 	cin >> n >> k;
    322 	string s;
    323 	cin >> s;
    324  
    325 	vector<int> pref_open(n + 1);
    326 	vector<int> pref_close(n + 1);
    327  
    328 	for (int i = 0; i < n; i++){
    329 		pref_open[i + 1] = pref_open[i] + (s[i] == '(');
    330 		pref_close[i + 1] = pref_close[i] + (s[i] == ')');
    331 	}
    332  
    333 	int total_close = pref_close[n];
    334  
    335 	int pos = n;
    336 	for (int i = 0; i < n; i++){
    337 		if (pref_open[i] + total_close - pref_close[i] <
    338 			pref_open[pos] + total_close - pref_close[pos]){
    339 				pos = i;
    340 		}
    341 	}
    342  
    343 	string ans(n, '0');
    344 	for (int i = 0; i < pos; i++){
    345 		if (k > 0 && s[i] == '('){
    346 			ans[i] = '1';
    347 			k--;
    348 		}
    349 	}
    350 	for (int i = pos; i < n; i++){
    351 		if (k > 0 && s[i] == ')'){
    352 			ans[i] = '1';
    353 			k--;
    354 		}
    355 	}
    356  
    357 	cout << ans << '\n';
    358 }
    359  
    360 signed main()
    361 {
    362 #ifdef FELIX
    363 	auto _clock_start = chrono::high_resolution_clock::now();
    364 #endif
    365 	ios_base::sync_with_stdio(false);
    366 	cin.tie(0);
    367 	cout.tie(0);
    368  
    369 	int tests = 1;
    370 	cin >> tests;
    371 	while(tests--){
    372 		solve();
    373 	}
    374  
    375 #ifdef FELIX
    376 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    377 		chrono::high_resolution_clock::now()
    378 			- _clock_start).count() << "ms." << endl;
    379 #endif
    380 	return 0;
    381 }
    382 ```
    383 
    384 **Rate the problem**
    385 
    386 Amazing
    387 
    388 Good
    389 
    390 Ok
    391 
    392 Bad
    393 
    394 Terrible
    395 
    396 [2233D - Goods on the Shelf](/contest/2233/problem/D "Educational Codeforces Round 191 (Rated for Div. 2)")
    397 
    398 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    399 
    400 **Tutorial**
    401 
    402 Tutorial is loading...
    403 
    404 **Solution (FelixArg)**
    405 
    406 ```
    407 #include<bits/stdc++.h>
    408  
    409 using namespace std;
    410  
    411 #define int long long
    412  
    413 void solve(){
    414 	int n;
    415 	cin >> n;
    416 	vector<int> a(n);
    417 	for (int i = 0; i < n; i++){
    418 		cin >> a[i];
    419 	}
    420  
    421 	auto b = a;
    422 	sort(b.begin(), b.end());
    423 	b.erase(unique(b.begin(), b.end()), b.end());
    424 	for (int i = 0; i < n; i++){
    425 		a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    426 	}
    427  
    428 	vector<vector<int>> blocks(n);
    429 	vector<int> cntb(n);
    430  
    431 	for (int i = 0; i < n; ){
    432 		int j = i;
    433 		while(i < n && a[i] == a[j]){
    434 			i++;
    435 		}
    436 		blocks[a[j]].push_back(i);
    437 		blocks[a[j]].push_back(i - 1);
    438  
    439 		blocks[a[j]].push_back(j);
    440 		blocks[a[j]].push_back(j - 1);
    441 		cntb[a[j]]++;
    442 	}
    443  
    444 	auto check = [&](int x, int y) {
    445 		if (x < 0 || x >= n || y < 0 || y >= n){
    446 			return 0;
    447 		}
    448 		swap(a[x], a[y]);
    449 		vector<int> cnt(n);
    450 		for (int i = 0; i < n;){
    451 			int j = i;
    452 			while(i < n && a[i] == a[j]){
    453 				i++;
    454 			}
    455 			cnt[a[j]]++;
    456 		}
    457 		swap(a[x], a[y]);
    458 		for (int i = 0; i < n; i++){
    459 			if (cnt[i] > 1){
    460 				return 0;
    461 			}
    462 		}
    463 		return 1;
    464 	};
    465  
    466 	for (int i = 0; i < n; i++){
    467 		if (cntb[i] > 1){
    468 			if (cntb[i] > 3){
    469 				cout << "NO\n";
    470 				return;
    471 			}
    472 			bool ok = 0;
    473 			sort(blocks[i].begin(), blocks[i].end());
    474 			blocks[i].erase(unique(blocks[i].begin(), blocks[i].end()), blocks[i].end());
    475 			for (int x : blocks[i]){
    476 				for (int y : blocks[i]){
    477 				    if (x < y){
    478 					    ok |= check(x, y);
    479 				    }
    480 				}
    481 			}
    482 			if (!ok){
    483 				cout << "NO\n";
    484 				return;
    485 			}
    486 			break;
    487 		}
    488 	}
    489  
    490 	cout << "YES\n";
    491 }
    492  
    493 signed main()
    494 {
    495 #ifdef FELIX
    496 	auto _clock_start = chrono::high_resolution_clock::now();
    497 #endif
    498 	ios_base::sync_with_stdio(false);
    499 	cin.tie(0);
    500 	cout.tie(0);
    501  
    502 	int tests = 1;
    503 	cin >> tests;
    504 	while(tests--){
    505 		solve();
    506 	}
    507  
    508 #ifdef FELIX
    509 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    510 		chrono::high_resolution_clock::now()
    511 			- _clock_start).count() << "ms." << endl;
    512 #endif
    513 	return 0;
    514 }
    515 ```
    516 
    517 **Rate the problem**
    518 
    519 Amazing
    520 
    521 Good
    522 
    523 Ok
    524 
    525 Bad
    526 
    527 Terrible
    528 
    529 [2233E1 - Permutation Transmission (Easy Version)](/contest/2233/problem/E1 "Educational Codeforces Round 191 (Rated for Div. 2)")
    530 
    531 [2233E2 - Permutation Transmission (Difficult Version)](/contest/2233/problem/E2 "Educational Codeforces Round 191 (Rated for Div. 2)")
    532 
    533 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    534 
    535 **Tutorial**
    536 
    537 Tutorial is loading...
    538 
    539 **Solution E1 (FairyWinx)**
    540 
    541 ```
    542 #include <bits/stdc++.h>
    543 
    544 #define all(a) a.begin(), a.end()
    545 #define rall(a) a.rbegin(), a.rend()
    546 #define len(a) (int)(a.size())
    547 
    548 #ifdef LOCAL
    549 #define __lg(n) log2(n)
    550 #endif
    551 
    552 using namespace std;
    553 
    554 using ll = long long;
    555 using ull = unsigned long long;
    556 using ld = long double;
    557 using int128 = __int128;
    558 
    559 template<typename T>
    560 using PQ = priority_queue<T, vector<T>, greater<>>;
    561 
    562 const int N = (1 << 18);
    563 
    564 void solve() {
    565     int n;
    566     cin >> n;
    567     vector<int> p(n);
    568     iota(all(p), 1);
    569     int k = 0;
    570     while ((1 << (k)) <= n) ++k;
    571     vector<string> s(n);
    572     for (int i = 0; i < k; ++i) cin >> s[i];
    573     map<string, int> used;
    574     int pp = 1;
    575     for (int i = 0; i < k; ++i) pp *= 3;
    576     for (int i = 0; i < n; ++i) {
    577         string z;
    578         for (int j = 0; j < k; ++j) z += s[j][i];
    579         if (*max_element(all(z)) == '0') {
    580             cout << 0 << '\n';
    581             return;
    582         }
    583         if (used[z]) {
    584             cout << 0 << '\n';
    585             return;
    586         }
    587         used[z] = 1;
    588     }
    589     vector<bitset<N>> cum(k);
    590     for (int i = 0; i < k; ++i) {
    591         for (int j = 0; j < n; ++j) {
    592             cum[i][j] = bool(s[i][j] - '0');
    593         }
    594     }
    595     vector<bitset<N>> ed((1 << k));
    596     ed[0].set();
    597     for (int mask = 0; mask < (1 << k); ++mask) {
    598         for (int i = 0; i < k; ++i) {
    599             if ((1 << i) & mask) {
    600                 ed[mask] = ed[mask - (1 << i)] & cum[i];
    601                 break;
    602             }
    603         }
    604     }
    605 
    606     auto get_mask = [&](int mask1, int mask2) -> int {
    607         int res = 0;
    608         int pw = 1;
    609         for (int i = 0; i < k; ++i) {
    610             if (mask2 & (1 << i)) {
    611                 res += 2 * pw;
    612             } else if (mask1 & (1 << i)) {
    613                 res += pw;
    614             }
    615             pw *= 3;
    616         }
    617         return res;
    618     };
    619 
    620     auto from_mask = [&](int val) -> pair<int, int> {
    621         int pw = 1;
    622         for (int i = 0; i < k - 1; ++i) {
    623             pw *= 3;
    624         }
    625         int mask1 = 0, mask2 = 0;
    626         for (int i = k - 1; i >= 0; --i) {
    627             int ost = val % pw;
    628             int tmp = val / pw;
    629             val = ost;
    630             if (tmp == 2) {
    631                 mask1 += (1 << i), mask2 += (1 << i);
    632             } else if (tmp == 1) {
    633                 mask1 += (1 << i);
    634             }
    635             pw /= 3;
    636         }
    637         return {mask1, mask2};
    638     };
    639 
    640     vector<ll> dp(pp, 0);
    641     dp[0] = 1;
    642     ll ans = 0;
    643     for (int mask = 0; mask < pp; ++mask) {
    644         if (dp[mask] == 0) continue;
    645         auto gd = from_mask(mask);
    646         int mask1 = gd.first, mask2 = gd.second;
    647         int cnt = 0;
    648         for (int i = 0; i < k; ++i) {
    649             if (mask1 & (1 << i)) {
    650                 ++cnt;
    651             }
    652         }
    653         if (cnt == k) {
    654             ans += dp[mask];
    655             continue;
    656         }
    657         int deg = k - 1 - cnt;
    658         if (n & (1 << deg)) {
    659             for (int i = 0; i < k; ++i) {
    660                 if ((1 << i) & mask1) continue;
    661                 auto mask_res = get_mask(mask1 + (1 << i), mask2 + (1 << i));
    662                 dp[mask_res] += dp[mask];
    663             }
    664         } else {
    665             for (int i = 0; i < k; ++i) {
    666                 if ((1 << i) & mask1) continue;
    667                 auto tmp_bit = ed[mask2] & cum[i];
    668                 if (dp[mask] != 0 && tmp_bit.none()) {
    669                     dp[get_mask(mask1 + (1 << i), mask2)] += dp[mask];
    670                 }
    671             }
    672         }
    673     }
    674     cout << ans << '\n';
    675 }
    676 
    677 signed main() {
    678     ios_base::sync_with_stdio(0);
    679     cin.tie(0);
    680 
    681     int t = 1;
    682     cin >> t;
    683     while (t--) solve();
    684 }
    685 ```
    686 
    687 **Solution E2 (FelixArg)**
    688 
    689 ```
    690 #include<bits/stdc++.h>
    691  
    692 using namespace std;
    693  
    694 #define int long long
    695  
    696 void solve(){
    697 	int n;
    698 	cin >> n;
    699  
    700 	int k = 1;
    701 	while((1 << k) <= n){
    702 		k++;
    703 	}
    704  
    705 	vector<string> s(k);
    706 	for (int i = 0; i < k; i++){
    707 		cin >> s[i];
    708 	}
    709 	vector<pair<int, int>> ord(k, {0ll, 0ll});
    710 	for (int i = 0; i < k; i++){
    711 		auto& [x, ind] = ord[i];
    712 		ind = i;
    713 		for (int j = 0; j < n; j++){
    714 			x += (s[i][j] == '1');
    715 		}
    716 	}
    717 	sort(ord.rbegin(), ord.rend());
    718  
    719 	vector<int> fact(k + 1);
    720 	fact[0] = 1;
    721 	for (int i = 1; i <= k; i++){
    722 		fact[i] = fact[i - 1] * i;
    723 	}
    724  
    725 	vector<int> p(n);
    726 	for (int i = 0; i < n; i++){
    727 		for (int j = 0; j < k; j++){
    728 			int bit = s[ord[j].second][i] - '0';
    729 			p[i] ^= (bit << j);
    730 		}
    731 	}
    732 	sort(p.begin(), p.end());
    733 	if (p[0] != 1){
    734 		cout << 0 << '\n';
    735 		return;
    736 	}
    737 	for (int i = 1; i < n; i++){
    738 		if (p[i] != p[i - 1] + 1){
    739 			cout << 0 << '\n';
    740 			return;
    741 		}
    742 	}
    743  
    744 	vector<int> cnt(n + 1);
    745 	for (auto [x, ind] : ord){
    746 		cnt[x]++;
    747 	}
    748  
    749 	int ans = 1;
    750 	for (int i = 0; i <= n; i++){
    751 		ans *= fact[cnt[i]];
    752 	}
    753 	cout << ans << '\n';
    754 }
    755  
    756 signed main()
    757 {
    758 #ifdef FELIX
    759 	auto _clock_start = chrono::high_resolution_clock::now();
    760 #endif
    761 	ios_base::sync_with_stdio(false);
    762 	cin.tie(0);
    763 	cout.tie(0);
    764  
    765 	int tests = 1;
    766 	cin >> tests;
    767 	while(tests--){
    768 		solve();
    769 	}
    770  
    771 #ifdef FELIX
    772 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    773 		chrono::high_resolution_clock::now()
    774 			- _clock_start).count() << "ms." << endl;
    775 #endif
    776 	return 0;
    777 }
    778 ```
    779 
    780 **Rate the problem**
    781 
    782 Amazing
    783 
    784 Good
    785 
    786 Ok
    787 
    788 Bad
    789 
    790 Terrible
    791 
    792 [2233F - Shortest GCD Paths](/contest/2233/problem/F "Educational Codeforces Round 191 (Rated for Div. 2)")
    793 
    794 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    795 
    796 **Tutorial**
    797 
    798 Tutorial is loading...
    799 
    800 **Solution (FelixArg)**
    801 
    802 ```
    803 #include<bits/stdc++.h>
    804  
    805 using namespace std;
    806  
    807 //#define int long long
    808  
    809 const int INF = 1000000007;
    810  
    811 void solve(){
    812 	int n, a, b;
    813 	cin >> n >> a >> b;
    814  
    815 	int g = gcd(a, b);
    816 	a /= g;
    817 	b /= g;
    818  
    819 	vector<int> d1, d2;
    820 	for (int i = 1; i * i <= a; i++){
    821 		if (a % i == 0){
    822 			d1.push_back(i);
    823 			if (i * i != a){
    824 				d1.push_back(a / i);
    825 			}
    826 		}
    827 	}
    828  
    829 	for (int i = 1; i * i <= b; i++){
    830 		if (b % i == 0){
    831 			d2.push_back(i);
    832 			if (i * i != b){
    833 				d2.push_back(b / i);
    834 			}
    835 		}
    836 	}
    837  
    838 	sort(d1.begin(), d1.end());
    839 	sort(d2.begin(), d2.end());
    840  
    841 	int sz1 = d1.size();
    842 	int sz2 = d2.size();
    843  
    844 	vector<vector<int>> to_d1(sz1, vector<int> (sz1, -1));
    845 	for (int i = 0; i < sz1; i++){
    846 		int u = 0;
    847 		for (int j = i; j >= 0; j--){
    848 			while(u < i && d1[i] > d1[u] * d1[j]){
    849 				u++;
    850 			}
    851 			if (d1[i] % d1[j] == 0 && d1[i] / d1[j] == d1[u]){
    852 				to_d1[i][j] = u;
    853 			}
    854 		}
    855 	}
    856  
    857 	vector<vector<int>> to_d2(sz2, vector<int> (sz2, -1));
    858 	for (int i = 0; i < sz2; i++){
    859 		int u = 0;
    860 		for (int j = i; j >= 0; j--){
    861 			while(u < i && d2[i] > d2[u] * d2[j]){
    862 				u++;
    863 			}
    864 			if (d2[i] % d2[j] == 0 && d2[i] / d2[j] == d2[u]){
    865 				to_d2[i][j] = u;
    866 			}
    867 		}
    868 	}
    869  
    870 	vector<vector<int>> dels_d1(sz1);
    871 	for (int i = 0; i < sz1; i++){
    872 		for (int j = 0; j <= i; j++){
    873 			if (d1[i] % d1[j] == 0){
    874 				dels_d1[i].emplace_back(j);
    875 			}
    876 		}
    877 	}
    878  
    879 	vector<vector<int>> dels_d2(sz2);
    880 	for (int i = 0; i < sz2; i++){
    881 		for (int j = 0; j <= i; j++){
    882 			if (d2[i] % d2[j] == 0){
    883 				dels_d2[i].emplace_back(j);
    884 			}
    885 		}
    886 	}
    887  
    888 	vector<vector<int>> dp(sz1, vector<int> (sz2, -1));
    889  
    890 	auto go = [&](auto&& self, int x, int y) -> int{
    891 		if (dp[x][y] != -1){
    892 			return dp[x][y];
    893 		}
    894 		if (x == 0 && y == 0){
    895 			return 0;
    896 		}
    897 		dp[x][y] = INF;
    898  
    899 		for (int dx : dels_d1[x]){
    900 			for (int dy : dels_d2[y]){
    901 				if (dx == 0 && dy == 0){
    902 					continue;
    903 				}
    904 				dp[x][y] = min(dp[x][y], max(d1[dx], d2[dy]) + self(self, to_d1[x][dx], to_d2[y][dy]));
    905 			}
    906 		}
    907 		return dp[x][y];
    908 	};
    909  
    910 	cout << go(go, sz1 - 1, sz2 - 1) << '\n';
    911 }
    912  
    913 signed main()
    914 {
    915 #ifdef FELIX
    916 	auto _clock_start = chrono::high_resolution_clock::now();
    917 #endif
    918 	ios_base::sync_with_stdio(false);
    919 	cin.tie(0);
    920 	cout.tie(0);
    921  
    922 	int tests = 1;
    923 	//cin >> tests;
    924 	while(tests--){
    925 		solve();
    926 	}
    927  
    928 #ifdef FELIX
    929 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    930 		chrono::high_resolution_clock::now()
    931 			- _clock_start).count() << "ms." << endl;
    932 #endif
    933 	return 0;
    934 }
    935 ```
    936 
    937 **Rate the problem**
    938 
    939 Amazing
    940 
    941 Good
    942 
    943 Ok
    944 
    945 Bad
    946 
    947 Terrible