codeforces-scrape

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

2225.md (13860B)


      1 Source: https://codeforces.com/blog/entry/153154
      2 
      3 [2225A - A Number Between Two Others](/contest/2225/problem/A "Educational Codeforces Round 189 (Rated for Div. 2)")
      4 
      5 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     x, y = map(int, input().split())
     17     good = False
     18     for z in range(x * 2, y, x):
     19         if y % z != 0:
     20             good = True
     21             break
     22     if good:
     23         print('YES')
     24     else:
     25         print('NO')
     26 ```
     27 
     28 **Solution 2 (BledDest)**
     29 
     30 ```
     31 t = int(input())
     32 for i in range(t):
     33     x, y = map(int, input().split())
     34     print('YES' if y > 2 * x else 'NO')
     35 ```
     36 
     37 [2225B - Alternating String](/contest/2225/problem/B "Educational Codeforces Round 189 (Rated for Div. 2)")
     38 
     39 Author: [FelixArg](/profile/FelixArg "Master FelixArg")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (FelixArg)**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49  
     50 using namespace std;
     51  
     52 #define int long long
     53  
     54 void solve() {
     55 	string s;
     56 	cin >> s;
     57 	int ans = 0;
     58 	for (int i = 0; i < (int)s.size() - 1; i++){
     59 		ans += (s[i] == s[i + 1]);
     60 	}
     61 	cout << (ans <= 2 ? "YES\n" : "NO\n");
     62 }
     63  
     64 signed main()
     65 {
     66 #ifdef FELIX
     67 	auto _clock_start = chrono::high_resolution_clock::now();
     68 #endif
     69 	ios_base::sync_with_stdio(false);
     70 	cin.tie(0);
     71 	cout.tie(0);
     72  
     73 	int tests = 1;
     74 	cin >> tests;
     75 	while(tests--){
     76 		solve();
     77 	}
     78  
     79 #ifdef FELIX
     80 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
     81 		chrono::high_resolution_clock::now()
     82 			- _clock_start).count() << "ms." << endl;
     83 #endif
     84 	return 0;
     85 }
     86 ```
     87 
     88 [2225C - Red-Black Pairs](/contest/2225/problem/C "Educational Codeforces Round 189 (Rated for Div. 2)")
     89 
     90 Author: [FelixArg](/profile/FelixArg "Master FelixArg")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution (FelixArg)**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100  
    101 using namespace std;
    102 
    103 #define int long long
    104 
    105 const int INF = 1'000'000'007;
    106 
    107 void solve(){
    108   int n;
    109   cin >> n;
    110   vector<string> d(2);
    111   cin >> d[0] >> d[1];
    112 
    113   vector<int> dp(n + 1, INF);
    114   dp[0] = 0;
    115   for (int i = 0; i < n; i++){
    116     dp[i + 1] = min(dp[i + 1], dp[i] + (d[0][i] != d[1][i]));
    117     if (i + 1 < n){
    118       dp[i + 2] = min(dp[i + 2], dp[i] + (d[0][i] != d[0][i + 1]) + (d[1][i] != d[1][i + 1]));
    119     }
    120   }
    121 
    122   cout << dp[n] << '\n';
    123 }
    124  
    125 signed main()
    126 {
    127 #ifdef FELIX
    128 	auto _clock_start = chrono::high_resolution_clock::now();
    129 #endif
    130 	ios_base::sync_with_stdio(false);
    131 	cin.tie(0);
    132 	cout.tie(0);
    133  
    134 	int t = 1;
    135 	cin >> t;
    136 	while(t--){
    137 		solve();
    138 	}
    139  
    140 #ifdef FELIX
    141 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    142 		chrono::high_resolution_clock::now()
    143 			- _clock_start).count() << "ms." << endl;
    144 #endif
    145 	return 0;
    146 }
    147 ```
    148 
    149 [2225D - Exceptional Segments](/contest/2225/problem/D "Educational Codeforces Round 189 (Rated for Div. 2)")
    150 
    151 Author: [FelixArg](/profile/FelixArg "Master FelixArg")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution (FelixArg)**
    158 
    159 ```
    160 #include<bits/stdc++.h>
    161 
    162 using namespace std;
    163 
    164 #define int long long
    165 
    166 const int MOD = 998'244'353;
    167 
    168 int get0(int x){
    169     return 1ll + (x >= 3 ? (x - 3) / 4 + 1 : 0);
    170 }
    171 
    172 int get1(int x){
    173     return (x >= 1 ? (x - 1) / 4 + 1 : 0);
    174 }
    175 
    176 void solve(){
    177 	int n, x;
    178 	cin >> n >> x;
    179 
    180     int l0 = get0(x - 1) % MOD;
    181     int r0 = (get0(n) - l0) % MOD;
    182 	int ans = l0 * r0;
    183 
    184     int l1 = get1(x - 1) % MOD;
    185     int r1 = (get1(n) - l1) % MOD;
    186 	ans += l1 * r1;
    187     ans %= MOD;
    188 
    189     cout << ans << '\n';
    190 }
    191 
    192 signed main()
    193 {
    194 #ifdef FELIX
    195 	auto _clock_start = chrono::high_resolution_clock::now();
    196 #endif
    197 	ios_base::sync_with_stdio(false);
    198 	cin.tie(0);
    199 	cout.tie(0);
    200 
    201 	int tests = 1;
    202 	cin >> tests;
    203 	while(tests--){
    204 		solve();
    205 	}
    206 
    207 #ifdef FELIX
    208 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    209 		chrono::high_resolution_clock::now()
    210 			- _clock_start).count() << "ms." << endl;
    211 #endif
    212 	return 0;
    213 }
    214 ```
    215 
    216 [2225E - Covering Points with Circles](/contest/2225/problem/E "Educational Codeforces Round 189 (Rated for Div. 2)")
    217 
    218 Author: [basalov_yurij](/profile/basalov_yurij "Expert basalov_yurij")
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution (FelixArg)**
    225 
    226 ```
    227 #include <bits/stdc++.h>
    228  
    229 using namespace std;
    230 
    231 #define int long long
    232 
    233 mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
    234  
    235 void solve() {
    236 	int n, r;
    237 	cin >> n >> r;
    238 	vector<pair<int, int>> p(n);
    239 	for (int i = 0; i < n; i++){
    240 		cin >> p[i].first >> p[i].second;
    241 	}
    242 
    243 	int w = 2 * r, h = ceil(sqrt(3) * r);
    244 
    245 	auto is_in_circle = [&](int x, int y, int ox, int oy, int r){
    246 		return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
    247 	};
    248 
    249 	int cov;
    250 	vector<pair<int, int>> ans;
    251 
    252 	do{
    253 		ans.clear();
    254 		cov = 0;
    255 		
    256 		int x0 = rng() % 100'000, y0 = rng() % 100'000;
    257 		auto check_point = [&](int x, int y){
    258 			int nearest_row = (y - y0) / h;
    259 			for (int row = nearest_row - 2; row <= nearest_row + 2; row++){
    260 				int nearest_col = (x - (x0 + (row % 2) * r)) / w;
    261 				for (int col = nearest_col - 2; col <= nearest_col + 2; col++){
    262 					int x_lat = x0 + col * w + (row % 2) * r;
    263 					int y_lat = y0 + row * h;
    264 					if (is_in_circle(x, y, x_lat, y_lat, r)){
    265 						ans.emplace_back(x_lat, y_lat);
    266 						cov++;
    267 						return;
    268 					}
    269 				}
    270 			}
    271 		};
    272 
    273 		for (int i = 0; i < n; i++){
    274 			check_point(p[i].first, p[i].second);
    275 		}
    276 	} while(cov * 100 < 89 * n);
    277 
    278 	sort(ans.begin(), ans.end());
    279 	ans.erase(unique(ans.begin(), ans.end()), ans.end());
    280 
    281 	cout << ans.size() << '\n';
    282 	for (auto [x, y] : ans){
    283 		cout << x << ' ' << y << '\n';
    284 	}
    285 }
    286  
    287 signed main()
    288 {
    289 #ifdef FELIX
    290 	auto _clock_start = chrono::high_resolution_clock::now();
    291 #endif
    292 	ios_base::sync_with_stdio(false);
    293 	cin.tie(0);
    294 	cout.tie(0);
    295  
    296 	int tests = 1;
    297 	//cin >> tests;
    298 	while(tests--){
    299 		solve();
    300 	}
    301  
    302 #ifdef FELIX
    303 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    304 		chrono::high_resolution_clock::now()
    305 			- _clock_start).count() << "ms." << endl;
    306 #endif
    307 	return 0;
    308 }
    309 ```
    310 
    311 [2225F - String Cutting](/contest/2225/problem/F "Educational Codeforces Round 189 (Rated for Div. 2)")
    312 
    313 Author: [FelixArg](/profile/FelixArg "Master FelixArg")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution 1 (FelixArg)**
    320 
    321 ```
    322 #include<bits/stdc++.h>
    323  
    324 using namespace std;
    325  
    326 #define int long long
    327 
    328 const int MODS[] = {some hidden number 1, some hidden number 2};
    329 const int P = some hidden number 3;
    330 
    331 int powP[2][1'000'007];
    332 int inv_powP[2][1'000'007];
    333 
    334 int bpow(int x, int p, int mod){
    335 	int res = 1;
    336 	while(p){
    337 		if (p % 2 == 1){
    338 			res = (res * x) % mod;
    339 		}
    340 		p >>= 1;
    341 		x = (x * x) % mod;
    342 	}
    343 	return res;
    344 }
    345  
    346 void solve(){
    347 	int n, l, k;
    348 	cin >> n >> l >> k;
    349 	string s;
    350 	cin >> s;
    351  
    352 	if (l * k > n){
    353 		cout << "NO\n";
    354 		return;
    355 	}
    356  
    357 	if (k == 1){
    358 		cout << "YES\n";
    359 		cout << s << '\n';
    360 		return;
    361 	}
    362 
    363 	vector<vector<int>> h(2, vector<int>(n + 1));
    364 	for (int i = 0; i < 2; i++){
    365 		for (int j = 0; j < n; j++){
    366 			h[i][j + 1] = (h[i][j] + (s[j] - 'a' + 1) * powP[i][j]) % MODS[i];
    367 		}
    368 	}
    369 
    370 	function<pair<int, int>(int, int)> get_h = [&](int l, int r){
    371 		return make_pair((h[0][r + 1] - h[0][l] + MODS[0]) * inv_powP[0][l] % MODS[0],
    372 		(h[1][r + 1] - h[1][l] + MODS[1]) * inv_powP[1][l] % MODS[1]);
    373 	};
    374  
    375 	function<int(int, int, int, int)> cmp_substring = [&](int l1, int r1, int l2, int r2){
    376 		int len1 = r1 - l1 + 1;
    377 		int len2 = r2 - l2 + 1;
    378 
    379 		int l = 0, r = min(len1, len2) - 1;
    380 		while(l <= r){
    381 			int m = l + (r - l) / 2;
    382 			if (get_h(l1, l1 + m) != get_h(l2, l2 + m)){
    383 				r = m - 1;
    384 			}
    385 			else{
    386 				l = m + 1;
    387 			}
    388 		}
    389 
    390 		char ch1 = (l < len1 ? s[l1 + l] : 'a' - 1);
    391 		char ch2 = (l < len2 ? s[l2 + l] : 'a' - 1);
    392  
    393 		if (ch1 < ch2){
    394 			return -1;
    395 		}
    396 		if (ch1 > ch2){
    397 			return 1;
    398 		}
    399 		return 0;
    400 	};
    401  
    402 	int la = 0, ra = l - 1;
    403  
    404 	for (int i = 0; i < n; i++){
    405 		int cnt = i / l;
    406 		if (i > 0 && cnt == 0){
    407 			continue;
    408 		}
    409 		int len = i + max(0ll, (k - 1) - cnt) * l;
    410 		if (n - len >= l){
    411 			if (cmp_substring(i, i + n - len - 1, la, ra) == 1){
    412 				la = i;
    413 				ra = i + n - len - 1;
    414 			}
    415 		}
    416 	}
    417  
    418 	cout << "YES\n";
    419 	cout << s.substr(la, ra - la + 1) << '\n';
    420 }
    421  
    422 signed main()
    423 {
    424 #ifdef FELIX
    425 	auto _clock_start = chrono::high_resolution_clock::now();
    426 #endif
    427 	ios_base::sync_with_stdio(false);
    428 	cin.tie(0);
    429 	cout.tie(0);
    430 
    431 	powP[0][0] = powP[1][0] = 1;
    432 	inv_powP[0][0] = inv_powP[1][0] = 1;
    433 	int inv_p[] = {bpow(P, MODS[0] - 2, MODS[0]), bpow(P, MODS[1] - 2, MODS[1])};
    434 
    435 	for (int i = 1; i < 1'000'001; i++){
    436 		for (int j = 0; j < 2; j++){
    437 			powP[j][i] = powP[j][i - 1] * P % MODS[j];
    438 			inv_powP[j][i] = inv_powP[j][i - 1] * inv_p[j] % MODS[j];
    439 		}
    440 	}
    441 
    442  
    443 	int tests = 1;
    444 	cin >> tests;
    445 	while(tests--){
    446 		solve();
    447 	}
    448  
    449 #ifdef FELIX
    450 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    451 		chrono::high_resolution_clock::now()
    452 			- _clock_start).count() << "ms." << endl;
    453 #endif
    454 	return 0;
    455 }
    456 ```
    457 
    458 **Solution 2 (BledDest)**
    459 
    460 ```
    461 #include <bits/stdc++.h>
    462  
    463 using namespace std;
    464  
    465 int n, l, k;
    466 string s;
    467 string cur;
    468 int zf[2000043];
    469 mt19937 rnd(421337);
    470  
    471 void z_function(const string& s) 
    472 {
    473     int n = s.size();
    474     for(int i = 0; i < n; i++) zf[i] = 0;
    475     for (int i = 1, l = 0, r = 0; i < n; i++) 
    476     {
    477         if (i <= r)
    478             zf[i] = min(r - i, zf[i - l]);
    479         while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]])
    480             zf[i]++;
    481         if (i + zf[i] > r) 
    482         {
    483             l = i;
    484             r = i + zf[i];
    485         }
    486     }        
    487 }
    488  
    489 bool read()
    490 {
    491     if (!(cin >> n >> l >> k))
    492         return false;
    493     cin >> s;
    494     return true;
    495 }    
    496  
    497 string find_best(vector<pair<int, int>> cand)
    498 {
    499     while(true)
    500     {
    501         if(cand.size() == 1)
    502             return s.substr(cand[0].first, cand[0].second);
    503         int lf = cand[0].first;
    504         int rg = cand[0].first + cand[0].second;
    505         for(int i = 1; i < cand.size(); i++)
    506         {
    507             lf = min(lf, cand[i].first);
    508             rg = max(rg, cand[i].first + cand[i].second);
    509         }
    510         auto p = cand[0];
    511         cur = s.substr(p.first, p.second) + "?" + s.substr(lf, rg - lf);
    512         z_function(cur);
    513         vector<pair<int, int>> better;
    514         int len = p.second;
    515         for(int i = 0; i < cand.size(); i++)
    516         {
    517             if(cand[i] == p) continue;
    518             int L = cand[i].first - lf;
    519             int cur_len = cand[i].second;
    520             int lcp = zf[len + 1 + L];
    521             lcp = min(lcp, cur_len);
    522             if(lcp == cur_len || (len > lcp && cur[L + len + 1 + lcp] <= cur[lcp]))
    523                 continue;
    524             better.push_back(cand[i]); 
    525         }
    526         if(better.empty())
    527             return s.substr(p.first, p.second);
    528         else
    529             cand = better;
    530     }
    531     return "";
    532 }
    533  
    534 void solve()
    535 {
    536     if(k * 1ll * l > n)
    537     {
    538         cout << "NO\n";
    539         return;
    540     }
    541     if(k == 1)
    542     {
    543         cout << "YES\n" << s << "\n";
    544         return;
    545     }
    546     vector<pair<int, int>> cand;
    547     for(int i = 0; i < n; i++)
    548     {
    549         if(i > 0 && i < l) continue;
    550         int lf = i / l;
    551         int rg = (n - i) / l;
    552         if(lf + rg < k) continue;
    553         int need_rg = max(0, k - lf - 1);
    554         int len = (n - need_rg * l) - i;
    555         if(len >= l)
    556             cand.push_back(make_pair(i, len));    
    557     }
    558     shuffle(cand.begin(), cand.end(), rnd);
    559     if(cand.empty())
    560     {
    561         cout << "NO\n";
    562     }
    563     else
    564     {
    565         cout << "YES\n" << find_best(cand) << "\n";
    566     }
    567 }
    568  
    569 int main()
    570 {
    571     cin.tie(0);
    572     ios::sync_with_stdio(false);
    573     
    574     int tc = 1;
    575     cin >> tc;
    576     while (tc--)
    577     {
    578         read();
    579         solve();
    580     }
    581 }
    582 ```
    583 
    584 [2225G - Simple Problem](/contest/2225/problem/G "Educational Codeforces Round 189 (Rated for Div. 2)")
    585 
    586 Author: [basalov_yurij](/profile/basalov_yurij "Expert basalov_yurij")
    587 
    588 **Tutorial**
    589 
    590 Tutorial is loading...
    591 
    592 **Solution (BledDest)**
    593 
    594 ```
    595 #include<bits/stdc++.h>
    596 
    597 using namespace std;
    598 
    599 int n, m;
    600 vector<int> k;
    601 vector<int> g;
    602 
    603 bool read()
    604 {
    605     if(!(cin >> n >> m)) return false;
    606     k.resize(m);
    607     for(int i = 0; i < m; i++) cin >> k[i];
    608     return true;
    609 }
    610 
    611 pair<vector<int>, vector<int>> get_chain(int start, int rank)
    612 {
    613     if(rank == 0)
    614         return make_pair(vector<int>({start}), vector<int>());
    615     pair<vector<int>, vector<int>> p = get_chain(start, rank - 1);
    616     int cnt = g[rank - 1] / g[rank];
    617     for(int i = 1; i < cnt; i++)
    618     {
    619         p.second.push_back(k[rank]);
    620         int next_start = (p.first.back() + k[rank]) % k[0];
    621         pair<vector<int>, vector<int>> q = get_chain(next_start, rank - 1);
    622         for(auto x : q.first) p.first.push_back(x);
    623         for(auto x : q.second) p.second.push_back(x);
    624     }
    625     return p;
    626 }
    627 
    628 void solve()
    629 {
    630     g = k;
    631     for(int i = 1; i < m; i++)
    632         g[i] = gcd(g[i - 1], k[i]);
    633     if(g.back() != 1)
    634     {
    635         cout << -1 << "\n";
    636         return;
    637     }   
    638     if(k[0] == 1)
    639     {
    640         for(int i = 0; i < n; i++)
    641         {
    642             if(i) cout << " ";
    643             cout << i;
    644         }
    645         cout << "\n";
    646         return;
    647     }
    648     pair<vector<int>, vector<int>> chain = get_chain(0, m - 1);
    649     vector<int> classes = chain.first;
    650     vector<int> add = chain.second;
    651     vector<int> ans;
    652     int new_begin = 0;
    653     for(int i = 0; i < classes.size(); i++)
    654     {
    655         int new_end = -1;
    656         for(int j = classes[i]; j < n; j += k[0])
    657             if(j != new_begin)
    658             {
    659                 new_end = j;
    660                 break;
    661             }
    662         ans.push_back(new_begin);
    663         for(int j = classes[i]; j < n; j += k[0])                                                   
    664             if(j != new_begin && j != new_end)
    665                 ans.push_back(j);
    666         ans.push_back(new_end);
    667         if(i + 1 < classes.size())
    668             new_begin = new_end + add[i];
    669     }
    670     for(int i = 0; i < n; i++)
    671     {
    672         if(i) cout << " ";
    673         cout << ans[i];
    674     }
    675     cout << "\n";
    676 }
    677 
    678 int main()
    679 {
    680     ios_base::sync_with_stdio(0);
    681     cin.tie(0);
    682     int t;
    683     cin >> t;
    684     while(t--)
    685     {
    686         read();
    687         solve();
    688     }
    689     return 0;
    690 }
    691 ```