codeforces-scrape

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

2086.md (13535B)


      1 Source: https://codeforces.com/blog/entry/141425
      2 
      3 Thank you for participating! I hope you enjoyed the problems.
      4 
      5 [2086A - Cloudberry Jam](/contest/2086/problem/A "Educational Codeforces Round 177 (Rated for Div. 2)")
      6 
      7 Idea: [Galina_Basalova](/profile/Galina_Basalova "Newbie Galina_Basalova")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution (Galina_Basalova)**
     14 
     15 ```
     16 #include<bits/stdc++.h>
     17 using namespace std;
     18  
     19 int main(){
     20     int t;
     21     cin >> t;
     22     while (t--) {
     23         int n;
     24         cin >> n;
     25         cout << n * 2 << "\n";
     26     }
     27     return 0;
     28 }
     29 ```
     30 
     31 [2086B - Large Array and Segments](/contest/2086/problem/B "Educational Codeforces Round 177 (Rated for Div. 2)")
     32 
     33 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (FelixArg)**
     40 
     41 ```
     42 #include<bits/stdc++.h>
     43 using namespace std;
     44 #define int long long
     45 
     46 void solve(){
     47     int n, k, x;
     48     cin >> n >> k >> x;
     49     vector<int> a(n);
     50     for (int i = 0; i < n; i++){
     51         cin >> a[i];
     52     }
     53 
     54     if (accumulate(a.begin(), a.end(), 0ll) * k < x){
     55         cout << 0 << '\n';
     56         return;
     57     }
     58 
     59     int l = 1, r = n * k;
     60     while(l <= r){
     61         int m = l + (r - l) / 2;
     62         int cnt_a = (n * k - m + 1) / n;
     63         int suff = (n * k - m + 1) % n;
     64         int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll);
     65         for (int i = n - suff; i < n; i++){
     66             sum += a[i];
     67         }
     68         if (sum < x){
     69             r = m - 1;
     70         }
     71         else{
     72             l = m + 1;
     73         }
     74     }
     75 
     76     cout << r << '\n';
     77 }
     78  
     79 signed main()
     80 {
     81 	ios_base::sync_with_stdio(false);
     82 	cin.tie(0);
     83 	cout.tie(0);
     84 	
     85 	int t;
     86 	cin >> t;
     87 	while(t--){
     88 	    solve();
     89 	}
     90 }
     91 ```
     92 
     93 [2086C - Disappearing Permutation](/contest/2086/problem/C "Educational Codeforces Round 177 (Rated for Div. 2)")
     94 
     95 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
     96 
     97 **Tutorial**
     98 
     99 Tutorial is loading...
    100 
    101 **Solution (FelixArg)**
    102 
    103 ```
    104 #include<bits/stdc++.h>
    105 using namespace std;
    106 #define int long long
    107 
    108 void solve(){
    109     int n;
    110     cin >> n;
    111     vector<int> p(n);
    112     for (int i = 0; i < n; i++){
    113         cin >> p[i];
    114         p[i]--;
    115     }
    116 
    117     set<int> X;
    118     for (int i = 0; i < n; i++){
    119         int d;
    120         cin >> d;
    121         d--;
    122         while(!X.contains(d)){
    123             X.insert(d);
    124             d = p[d];
    125         }
    126         cout << X.size() << ' ';
    127     } 
    128     cout << endl;
    129 }
    130  
    131 signed main()
    132 {
    133 	ios_base::sync_with_stdio(false);
    134 	cin.tie(0);
    135 	cout.tie(0);
    136 
    137 	int t;
    138 	cin >> t;
    139 	while(t--){
    140 	    solve();
    141 	}
    142 }
    143 ```
    144 
    145 [2086D - Even String](/contest/2086/problem/D "Educational Codeforces Round 177 (Rated for Div. 2)")
    146 
    147 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution (FelixArg)**
    154 
    155 ```
    156 #include<bits/stdc++.h>
    157 using namespace std;
    158 #define int long long
    159  
    160 const int MOD = 998'244'353;
    161  
    162 int bpow(int x, int p){
    163 	int res = 1;
    164 	while(p){
    165 		if (p % 2){
    166 			res = (res * x) % MOD;
    167 		}
    168 		p >>= 1;
    169 		x = (x * x) % MOD;
    170 	}
    171 	return res;
    172 }
    173  
    174 int fact(int x){
    175 	int res = 1;
    176 	for (int i = 1; i <= x; i++){
    177 		res = (res * i) % MOD;
    178 	}
    179 	return res;
    180 }
    181  
    182 void solve(){
    183 	vector<int> c(26);
    184 	for (int i = 0; i < 26; i++){
    185 		cin >> c[i];
    186 	}
    187  
    188 	int s = accumulate(c.begin(), c.end(), 0ll);
    189 	
    190 	vector<int> dp(s + 1);
    191 	dp[0] = 1;
    192  
    193 	for (int i = 0; i < 26; i++){
    194 		if (c[i] == 0){
    195 			continue;
    196 		}
    197 		for (int j = s; j >= 0; j--){
    198 			if (j + c[i] <= s){
    199 				dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD;
    200 			}
    201 		}
    202 	}
    203  
    204 	int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD;
    205 	for (int i = 0; i < 26; i++){
    206 		ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD;
    207 	}
    208  
    209 	cout << ans << '\n';
    210 }
    211  
    212 signed main(){
    213     ios_base::sync_with_stdio(false);
    214     cin.tie(0);
    215     cout.tie(0);
    216  
    217     int t;
    218     cin >> t;
    219     while(t--){
    220         solve();
    221     }
    222 }
    223 ```
    224 
    225 [2086E - Zebra-like Numbers](/contest/2086/problem/E "Educational Codeforces Round 177 (Rated for Div. 2)")
    226 
    227 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    228 
    229 **Tutorial**
    230 
    231 Tutorial is loading...
    232 
    233 **Solution (FelixArg)**
    234 
    235 ```
    236 #include<bits/stdc++.h>
    237 using namespace std;
    238  
    239 long long dp[40][120][2][2];
    240  
    241 void count(vector<int>& num){
    242 	int m = num.size();
    243 	memset(dp, 0, sizeof(dp));
    244  
    245 	dp[0][0][1][0] = 1;
    246 	for (int i = 0; i < m; i++){
    247 		for (int j = 0; j < 3 * m + 2; j++){
    248 			for (int k = 0; k < 4; k++){
    249 				if (j + k >= 3 * m + 2){
    250 					break;
    251 				}
    252 				if (num[i] == k){
    253 					dp[i + 1][j + k][1][0] += dp[i][j][1][0];
    254 					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
    255 					if (k == 0){
    256 						dp[i + 1][j + k][1][1] += dp[i][j][1][1];
    257 						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
    258 					}
    259 				}
    260 				else if (num[i] > k){
    261 					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
    262 					dp[i + 1][j + k][0][0] += dp[i][j][1][0];
    263 					if (k == 0){
    264 						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
    265 						dp[i + 1][j + k][0][1] += dp[i][j][1][1];
    266 					}
    267 				}
    268 				else{
    269 					dp[i + 1][j + k][0][0] += dp[i][j][0][0];
    270 					if (k == 0){
    271 						dp[i + 1][j + k][0][1] += dp[i][j][0][1];
    272 					}
    273 				}
    274 			}
    275 			if (j + 4 < 3 * m + 2){
    276 				if (num[i] == 4){
    277 					dp[i + 1][j + 4][1][1] += dp[i][j][1][0];
    278 					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];				
    279 				}
    280 				else{
    281 					dp[i + 1][j + 4][0][1] += dp[i][j][0][0];					
    282 				}
    283 			}
    284 		}
    285 	}
    286 }
    287  
    288 void solve(){
    289 	long long l, r, k;
    290 	cin >> l >> r >> k;
    291 	l--;
    292 	if (k >= 90){
    293 		cout << 0 << '\n';
    294 		return;
    295 	}
    296  
    297 	vector<long long> zeb;
    298 	long long cur = 0;
    299 	for (int i = 0; i < 60; i += 2){
    300 		cur ^= (1ll << i);
    301 		zeb.emplace_back(cur);
    302 	}
    303 	int m = zeb.size();
    304  
    305 	vector<int> num_l;
    306 	for (int i = m - 1; i >= 0; i--){
    307 		int cnt = 0;
    308 		while(l >= zeb[i]){
    309 			cnt++;
    310 			l -= zeb[i];
    311 		}
    312 		num_l.emplace_back(cnt);
    313 	}
    314  
    315 	vector<int> num_r;
    316 	for (int i = m - 1; i >= 0; i--){
    317 		int cnt = 0;
    318 		while(r >= zeb[i]){
    319 			cnt++;
    320 			r -= zeb[i];
    321 		}
    322 		num_r.emplace_back(cnt);
    323 	}
    324  
    325 	count(num_r);
    326 	long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
    327 	count(num_l);
    328 	ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];
    329 	cout << ans << '\n';
    330 }
    331  
    332 signed main()
    333 {
    334 	ios_base::sync_with_stdio(false);
    335 	cin.tie(0);
    336 	cout.tie(0);
    337 	
    338 	int t;
    339 	cin >> t;
    340 	while(t--){
    341 	    solve();
    342 	}
    343 }
    344 ```
    345 
    346 **Solution (BledDest)**
    347 
    348 ```
    349 #include <bits/stdc++.h>
    350 using namespace std;
    351  
    352 vector<long long> z;
    353  
    354 void precalc()
    355 {
    356     z = {1ll};
    357     while(z.back() < 1e18)
    358         z.push_back(4 * z.back() + 1);
    359 }
    360  
    361 map<pair<long long, long long>, long long> dp;
    362  
    363 long long get(long long r, long long x)
    364 {
    365     if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)];
    366     long long& d = dp[make_pair(r, x)];
    367     if(x > 4 * z.size()) return d = 0;
    368     if(x < 0) return d = 0;
    369     if(r == 0) return d = 0;
    370     if(r == 1)
    371     {
    372         if(x == 0) return d = 1;
    373         return d = 0;
    374     }
    375     auto it = lower_bound(z.begin(), z.end(), r);
    376     --it;
    377     long long y = *it;
    378     return d = get(y, x) + get(r - y, x - 1);
    379 }
    380  
    381 int main() 
    382 {
    383     precalc();
    384     int t;
    385     cin >> t;
    386     for(int i = 0; i < t; i++)
    387     {
    388         long long l, r, x;
    389         cin >> l >> r >> x;
    390         cout << get(r + 1, x) - get(l, x) << endl;
    391     }
    392 }
    393 ```
    394 
    395 [2086F - Online Palindrome](/contest/2086/problem/F "Educational Codeforces Round 177 (Rated for Div. 2)")
    396 
    397 Idea: [Valentin_E](/profile/Valentin_E "Master Valentin_E")
    398 
    399 **Tutorial**
    400 
    401 Tutorial is loading...
    402 
    403 **Solution (FelixArg)**
    404 
    405 ```
    406 #include<bits/stdc++.h>
    407 using namespace std;
    408 #define int long long
    409  
    410 bool is_palindrom(const string& s){
    411     int n = s.size();
    412     for (int i = 0; i < n / 2; i++){
    413         if (s[i] != s[n - i - 1]){
    414             return false;
    415         }
    416     }
    417     return true;
    418 }
    419  
    420 bool check_pattern(const string& s){
    421     int n = s.size();
    422     char a = 'a', b = 'b';
    423     int cnt_a = 0, cnt_b = 0;
    424     for (int i = 0; i < n; i++){
    425         if (s[i] == a){
    426             cnt_a++;
    427         }
    428         else{
    429             cnt_b++;
    430         }
    431     }
    432     if (cnt_a % 2 == 1){
    433         swap(cnt_a, cnt_b);
    434         swap(a, b);
    435     }
    436     if (s[n / 2] != b){
    437         return false;
    438     }
    439     if (!is_palindrom(s)){
    440         return false;
    441     }
    442  
    443     cnt_b--;
    444     cnt_a /= 2;
    445     cnt_b /= 2;
    446  
    447     if (cnt_a > cnt_b){
    448         swap(cnt_a, cnt_b);
    449         swap(a, b);
    450     }
    451  
    452     if (s[0] == a){
    453         cnt_a--;
    454     }
    455     else{
    456         cnt_b--;
    457     }
    458  
    459     for (int i = 1; i < n / 2; i++){
    460         if (s[i] == s[i - 1]){
    461             if (cnt_a == 0){
    462                 return true;
    463             }
    464             return false;
    465         }
    466         if (s[i] == a){
    467             cnt_a--;
    468         }
    469         else{
    470             cnt_b--;
    471         }
    472     }
    473  
    474     return true;
    475 }
    476  
    477 pair<int, int> find_valid_move_odd(string s){
    478     int n = s.size();
    479     for (int i = 0; i < n; i++){
    480         for (int j = i; j < n; j++){
    481             swap(s[i], s[j]);
    482             if (check_pattern(s)){
    483                 return {i, j};
    484             }
    485             swap(s[i], s[j]);
    486         }
    487     }
    488     return {-1, -1};
    489 }
    490  
    491 pair<int, int> find_valid_move_even(string s){
    492     int n = s.size();
    493     for (int i = n - 1; i >= 0; i--){
    494         for (int j = 0; j <= i; j++){
    495             if (s[i] == s[j] && i != j){
    496                 continue;
    497             }
    498             if (i == j && i != n - 1){
    499                 continue;
    500             }
    501             swap(s[i], s[j]);
    502             int cnt = 0;
    503             s += 'a';
    504             for (int k = n; k >= 0; k--){
    505                 for (int l = 0; l <= k; l++){
    506                     if (s[k] == s[l] && k != l){
    507                         continue;
    508                     }
    509                     if (k == l && k != n){
    510                         continue;
    511                     }                
    512                     swap(s[k], s[l]);
    513                     if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
    514                         cnt++;
    515                         swap(s[k], s[l]);
    516                         break;
    517                     }
    518                     swap(s[k], s[l]);
    519                 }
    520                 if (cnt == 1){
    521                     break;
    522                 }
    523             }
    524             s.pop_back();
    525             if (cnt == 1){
    526                 s += 'b';
    527                 for (int k = n; k >= 0; k--){
    528                     for (int l = 0; l <= k; l++){
    529                         if (s[k] == s[l] && k != l){
    530                             continue;
    531                         }
    532                         if (k == l && k != n){
    533                             continue;
    534                         }   
    535                         swap(s[k], s[l]);
    536                         if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){
    537                             return {i, j};
    538                         }
    539                         swap(s[k], s[l]);
    540                     }
    541                 }
    542                 s.pop_back();
    543             }
    544             swap(s[i], s[j]);
    545         }
    546     }
    547     return {-1, -1};
    548 }
    549  
    550 void solve(){
    551     string t = "";
    552     while(1){
    553         char ch;
    554         cin >> ch;
    555         if (ch == '0'){
    556             break;
    557         }
    558  
    559         t += ch;
    560  
    561         if (t.size() % 2 == 1){
    562             auto [l, r] = find_valid_move_odd(t);
    563             swap(t[l], t[r]);
    564             cout << l + 1 << ' ' << r + 1 << endl;
    565         }
    566         else{
    567             auto [l, r] = find_valid_move_even(t);
    568             swap(t[l], t[r]);
    569             cout << l + 1 << ' ' << r + 1 << endl;
    570         }
    571     }
    572 }
    573  
    574 signed main()
    575 {
    576 	ios_base::sync_with_stdio(false);
    577 	cin.tie(0);
    578 	cout.tie(0);
    579 	solve();
    580 }
    581 ```
    582 
    583 **Solution (awoo)**
    584 
    585 ```
    586 #include <bits/stdc++.h>
    587 using namespace std;
    588 
    589 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    590 const int N = 100;
    591  
    592 bool dp[N][N];
    593 pair<int, int> nxt[N][N][2];
    594 bitset<N> cur;
    595 bitset<N> form[N][N];
    596  
    597 int main(){
    598 	forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2;
    599 	for (int len = 1; len < N; len += 2){
    600 		forn(x, len + 1){
    601 			int y = len - x;
    602 			int nx = x, ny = y;
    603 			int i = 0;
    604 			while (nx > 1 || ny > 1){
    605 				if (nx > 1){
    606 					nx -= 2;
    607 					++i;
    608 				}
    609 				if (ny > 1){
    610 					form[x][y][i] = form[x][y][len - i - 1] = 1;
    611 					ny -= 2;
    612 					++i;
    613 				}
    614 			}
    615 			if (ny > 0){
    616 				form[x][y][i] = 1;
    617 			}
    618 		}
    619 	}
    620 	for (int len = N - 3; len >= 1; len -= 2){
    621 		forn(x, len + 1){
    622 			int y = len - x;
    623 			cur = form[x][y];
    624 			forn(c, 2){
    625 				cur[len] = c;
    626 				bool found = false;
    627 				forn(l, len + 1){
    628 					forn(r, l + 1){
    629 						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
    630 						bool ok = true;
    631 						forn(d, 2){
    632 							cur[len + 1] = d;
    633 							int nx = x + (c == 0) + (d == 0);
    634 							int ny = y + (c == 1) + (d == 1);
    635 							if ((cur ^ form[nx][ny]).count() > 2){
    636 								ok = false;
    637 								break;
    638 							}
    639 						}
    640 						if (ok){
    641 							found = true;
    642 							nxt[x][y][c] = {l, r};
    643 						}
    644 						if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
    645 						if (found) break;
    646 					}
    647 					if (found) break;
    648 				}
    649 				if (!found){
    650 					dp[x][y] = false;
    651 					break;
    652 				}
    653 			}
    654 		}
    655 	}
    656 	string s;
    657 	cur.reset();
    658 	for (int i = 0;; ++i){
    659 		cin >> s;
    660 		if (s == "0") break;
    661 		int c = s[0] - 'a';
    662 		int py = cur.count(), px = i - py;
    663 		cur[i] = c;
    664 		int nx = px + (c == 0), ny = py + (c == 1);
    665 		int l = -1, r = -1;
    666 		if (i % 2 == 1){
    667 			auto res = nxt[px][py][c];
    668 			if (res.first != res.second){
    669 				l = res.first;
    670 				r = res.second;
    671 			}
    672 		}
    673 		else{
    674 			assert(dp[nx][ny]);
    675 			bitset<N> dif = cur ^ form[nx][ny];
    676 			assert(dif.count() <= 2);
    677 			if (dif.count() == 2){
    678 				l = dif._Find_first();
    679 				r = dif._Find_next(l);
    680 			}
    681 		}
    682 		if (l == -1){
    683 			cout << 0 << " " << 0 << endl;
    684 		}
    685 		else{
    686 			cout << l + 1 << " " << r + 1 << endl;
    687 			if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();
    688 		}
    689 	}
    690 }
    691 ```