codeforces-scrape

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

2203.md (11418B)


      1 Source: https://codeforces.com/blog/entry/151612
      2 
      3 [2203A - Towers of Boxes](/contest/2203/problem/A "Educational Codeforces Round 187 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n, m, d = map(int, input().split())
     17     k = 1 + d // m
     18     print((n + k - 1) // k)
     19 ```
     20 
     21 [2203B - Beautiful Numbers](/contest/2203/problem/B "Educational Codeforces Round 187 (Rated for Div. 2)")
     22 
     23 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     24 
     25 **Tutorial**
     26 
     27 Tutorial is loading...
     28 
     29 **Solution (Neon)**
     30 
     31 ```
     32 #include <bits/stdc++.h>
     33  
     34 using namespace std;
     35  
     36 int main() {
     37 	int t;
     38 	cin >> t;
     39 	while (t--) {
     40 		string s;
     41 		cin >> s;
     42 		int sum = 0;
     43 		vector<int> a;
     44 		for (int i = 0; i < int(s.size()); ++i) {
     45 			int x = s[i] - '0';
     46 			sum += x;
     47 			a.push_back(x - (i == 0));
     48 		}
     49 		sort(a.begin(), a.end());
     50 		int ans = 0;
     51 		while (sum > 9) {
     52 			sum -= a.back();
     53 			a.pop_back();
     54 			++ans;
     55 		}
     56 		cout << ans << '\n';
     57 	}
     58 }
     59 ```
     60 
     61 [2203C - Test Generator](/contest/2203/problem/C "Educational Codeforces Round 187 (Rated for Div. 2)")
     62 
     63 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (FelixArg)**
     70 
     71 ```
     72 #include<bits/stdc++.h>
     73 #define int long long
     74 using namespace std;
     75  
     76 bool get(int x, int a, int lim){
     77 	int f = 0;
     78 	for (int i = 59; i >= 0; i--){
     79 		f <<= 1;
     80 		if (((x >> i) & 1) == 1){
     81 			f++;
     82 		} 
     83 		if (((a >> i) & 1) == 1){
     84 			f -= min(lim, f);
     85 		}
     86 	}
     87 	return (f == 0);
     88 }
     89  
     90 void solve(){
     91 	int x, a;
     92 	cin >> x >> a;
     93  
     94 	if (!get(x, a, 1ll << 60)){
     95 		cout << -1 << '\n';
     96 		return;
     97 	}
     98  
     99 	int l = 0, r = (1ll << 60);
    100 	while(l <= r){
    101 		int m = l + (r - l) / 2;
    102 		if (get(x, a, m)){
    103 			r = m - 1;
    104 		}
    105 		else{
    106 			l = m + 1;
    107 		}
    108 	}
    109  
    110 	cout << l << '\n';
    111 }
    112  
    113 signed main()
    114 {
    115 #ifdef FELIX
    116 	auto _clock_start = chrono::high_resolution_clock::now();
    117 #endif
    118 	ios_base::sync_with_stdio(false);
    119 	cin.tie(0);
    120 	cout.tie(0);
    121  
    122 	int tests = 1;
    123 	cin >> tests;
    124 	for (int test = 0; test < tests; test++){
    125 		solve();
    126 	}
    127 #ifdef FELIX
    128 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    129 		chrono::high_resolution_clock::now()
    130 			- _clock_start).count() << "ms." << endl;
    131 #endif
    132 	return 0;
    133 }
    134 ```
    135 
    136 [2203D - Divisibility Game](/contest/2203/problem/D "Educational Codeforces Round 187 (Rated for Div. 2)")
    137 
    138 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    139 
    140 **Tutorial**
    141 
    142 Tutorial is loading...
    143 
    144 **Solution (FelixArg)**
    145 
    146 ```
    147 #include <bits/stdc++.h>
    148  
    149 using namespace std;
    150  
    151 int main() {
    152 	ios_base::sync_with_stdio(0);
    153 	cin.tie(0);
    154 	cout.tie(0);
    155 	
    156 	int t;
    157 	cin >> t;
    158 	
    159 	for (int test = 0; test < t; test++){
    160     	int n, m;
    161     	cin >> n >> m;
    162     
    163     	vector<int> a(n), b(m);
    164     	for (int i = 0; i < n; i++){
    165     		cin >> a[i];
    166     	}
    167     	for (int i = 0; i < m; i++){
    168     		cin >> b[i];
    169     	}
    170     
    171     	int max_a = n + m + 1;
    172     
    173     	vector<int> cnt_b(max_a, 0), cnt_a(max_a, 0);
    174     
    175     	for (int i = 0; i < n; i++){
    176     		cnt_a[a[i]]++;
    177     	}
    178     
    179     	for (int i = 0; i < m; i++){
    180     		cnt_b[b[i]]++;
    181     	}
    182     
    183     	vector<int> cnt_del(max_a, 0);
    184     
    185     	int f = 0, s = 0, com = 0;
    186     
    187     	for (int i = 1; i < max_a; i++){
    188     		for (int j = i; j < max_a; j += i){
    189     			cnt_del[j] += cnt_a[i];
    190     		}
    191     	}
    192     
    193     	for (int i = 1; i < max_a; i++){
    194     		if (cnt_b[i] == 0){
    195     			continue;
    196     		}
    197     
    198     		if (cnt_del[i] == 0){
    199     			s += cnt_b[i];
    200     		}
    201     		else if (cnt_del[i] == n){
    202     			f += cnt_b[i];
    203     		}
    204     	}
    205     
    206     	com = m - f - s;
    207     
    208     	bool turn = 0;
    209     	string win = "";
    210     
    211     	while(1){
    212     		if (turn == 0){
    213     			if (com > 0){
    214     				com--;
    215     			}
    216     			else if (f > 0){
    217     				f--;
    218     			}
    219     			else{
    220     				win = "Bob";
    221     				break;
    222     			}
    223     		}
    224     		else{
    225     			if (com > 0){
    226     				com--;
    227     			}
    228     			else if (s > 0){
    229     				s--;
    230     			}
    231     			else{
    232     				win = "Alice";
    233     				break;
    234     			}
    235     		}
    236     		turn = !turn;
    237     	}
    238     
    239     	cout << win << '\n';
    240 	}
    241  
    242     return 0; 
    243 }
    244 ```
    245 
    246 [2203E - Probabilistic Card Game](/contest/2203/problem/E "Educational Codeforces Round 187 (Rated for Div. 2)")
    247 
    248 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    249 
    250 **Tutorial**
    251 
    252 Tutorial is loading...
    253 
    254 **Solution 1 (awoo)**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258 #include "ext/pb_ds/assoc_container.hpp"
    259 using namespace __gnu_pbds;
    260  
    261 #define forn(i, n) for (int i = 0; i < int(n); i++)
    262  
    263 using namespace std;
    264  
    265 const int MOD = 998244353;
    266  
    267 int mul(int a, int b){
    268 	return a * 1ll * b % MOD;
    269 }
    270  
    271 int binpow(int a, int b){
    272 	int res = 1;
    273 	while (b){
    274 		if (b & 1)
    275 			res = mul(res, a);
    276 		a = mul(a, a);
    277 		b >>= 1;
    278 	}
    279 	return res;
    280 }
    281  
    282 template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    283  
    284 int main() {
    285 	cin.tie(0);
    286 	ios::sync_with_stdio(false);
    287 	int m;
    288 	cin >> m;
    289 	vector<long long> a(m);
    290 	forn(i, m) cin >> a[i];
    291 	auto xs = a;
    292 	sort(xs.begin(), xs.end());
    293 	for (auto& x : a) x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    294  
    295 	vector<long long> f(m);
    296  
    297 	auto upd = [&](int x, long long val){
    298 		for (int i = x; i < int(f.size()); i |= i + 1)
    299 			f[i] += val;
    300 	};
    301 	auto get = [&](int x){
    302 		long long sum = 0;
    303 		for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    304 			sum += f[i];
    305 		return sum;
    306 	};
    307  
    308 	long long sum = 0;
    309 	ordered_set<int> cur;
    310 	for (int x : a){
    311 		cur.insert(x);
    312 		int n = cur.size();
    313 		sum += xs[x];
    314 		upd(x, xs[x]);
    315  
    316 		if (n < 3) continue;
    317  
    318 		auto getL = [&](int pos, auto it){
    319 			if (it == cur.begin()) return 0ll;
    320 			return xs[*prev(it)] * 1ll * pos - get(*it - 1);
    321 		};
    322  
    323 		auto getR = [&](int pos, auto it){
    324 			if (next(it) == cur.end()) return 0ll;
    325 			return (sum - get(*it)) - xs[*next(it)] * 1ll * (n - pos - 1);
    326 		};
    327  
    328 		int l = 0, r = n - 1;
    329 		int pos = n;
    330 		while (l <= r){
    331 			int m = (l + r) / 2;
    332 			auto it = cur.find_by_order(m);
    333 			if (getL(m, it) >= getR(m, it)){
    334 				pos = m;
    335 				r = m - 1;
    336 			}
    337 			else{
    338 				l = m + 1;
    339 			}
    340 		}
    341  
    342 		long long ans = 1e18;
    343 		forn(_, 2){
    344 			if (0 <= pos && pos < n){
    345 				auto it = cur.find_by_order(pos);
    346 				ans = min(ans, max(getL(pos, it), getR(pos, it)));
    347 			}
    348 			--pos;
    349 		}
    350  
    351 		cout << mul(ans % MOD, binpow(n - 2, MOD - 2)) << '\n';
    352 	}
    353 	return 0;
    354 }
    355 ```
    356 
    357 **Solution 2 (awoo)**
    358 
    359 ```
    360 #include <bits/stdc++.h>
    361  
    362 #define forn(i, n) for (int i = 0; i < int(n); i++)
    363  
    364 using namespace std;
    365  
    366 const long long INF64 = 1e18;
    367 const int MOD = 998244353;
    368  
    369 int mul(int a, int b){
    370 	return a * 1ll * b % MOD;
    371 }
    372  
    373 int binpow(int a, int b){
    374 	int res = 1;
    375 	while (b){
    376 		if (b & 1)
    377 			res = mul(res, a);
    378 		a = mul(a, a);
    379 		b >>= 1;
    380 	}
    381 	return res;
    382 }
    383  
    384 int main() {
    385 	cin.tie(0);
    386 	ios::sync_with_stdio(false);
    387 	int m;
    388 	cin >> m;
    389 	vector<long long> a(m);
    390 	int n = m + 2;
    391 	forn(i, m) cin >> a[i];
    392  
    393 	int p = sqrt(n) + 3;
    394 	auto xs = a;
    395 	xs.push_back(0);
    396 	sort(xs.begin(), xs.end());
    397 	xs.push_back(xs.back() + 1);
    398 	vector<int> cntbl(n), rgh(n, -1);
    399 	rgh[0] = 0;
    400 	rgh[(n - 1) / p] = n - 1;
    401 	vector<long long> sumbl(n);
    402 	vector<int> cll(n, 0), clr(n, n - 1);
    403  
    404 	set<int> on({0, n - 1});
    405 	int cnt = 0;
    406 	long long sum = 0;
    407 	forn(i, m){
    408 		int x = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    409 		int bl = x / p;
    410  
    411 		++cntbl[bl];
    412 		sumbl[bl] += xs[x];
    413 		rgh[bl] = max(rgh[bl], x);
    414 		sum += xs[x];
    415 		++cnt;
    416  
    417 		auto it = on.lower_bound(x);
    418 		clr[x] = *it;
    419 		cll[x] = *prev(it);
    420 		clr[*prev(it)] = cll[*it] = x;
    421 		on.insert(x);
    422  
    423 		if (cnt < 3) continue;
    424  
    425 		int lst = clr[0];
    426 		int cntl = 0;
    427 		long long suml = 0;
    428  
    429 		auto getL = [&](int x){ return xs[cll[x]] * 1ll * cntl - suml; };
    430 		auto getR = [&](int x){ return (sum - suml - xs[x]) - xs[clr[x]] * 1ll * (cnt - cntl - 1); };
    431 		auto check = [&](int x){
    432 			if (x == 0) return true;
    433 			if (x == n - 1) return false;
    434 			return getL(x) < getR(x);
    435 		};
    436  
    437 		while (lst < n - 1){
    438 			int bl = lst / p;
    439 			assert(rgh[bl] != -1);
    440 			if (!check(rgh[bl])) break;
    441 			cntl += cntbl[bl];
    442 			suml += sumbl[bl];
    443 			lst = clr[rgh[bl]];
    444 		}
    445  
    446 		while (lst < n - 1){
    447 			if (!check(lst)) break;
    448 			++cntl;
    449 			suml += xs[lst];
    450 			lst = clr[lst];
    451 		}
    452  
    453 		x = lst;
    454 		long long ans = 1e18;
    455 		if (x != n - 1)
    456 			ans = min(ans, max(getL(x), getR(x)));
    457 		assert(x != 0);
    458 		x = cll[x];
    459 		if (x != 0){
    460 			--cntl;
    461 			suml -= xs[x];
    462 			ans = min(ans, max(getL(x), getR(x)));
    463 		}
    464  
    465 		cout << mul(ans % MOD, binpow(cnt - 2, MOD - 2)) << '\n';
    466 	}
    467 	return 0;
    468 }
    469 ```
    470 
    471 [2203F - Binary Search with One Swap](/contest/2203/problem/F "Educational Codeforces Round 187 (Rated for Div. 2)")
    472 
    473 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    474 
    475 **Tutorial**
    476 
    477 Tutorial is loading...
    478 
    479 **Solution (BledDest)**
    480 
    481 ```
    482 #include<bits/stdc++.h>
    483  
    484 using namespace std;
    485  
    486 vector<long long> ans;
    487 int n;
    488 vector<int> cnt;
    489  
    490 void prepare_aux(int l, int r, vector<int>& a)
    491 {
    492     if(l > r) return;
    493     int m = (l + r) / 2;
    494     a[m] = r - l + 1;
    495     if(l < m) prepare_aux(l, m - 1, a);
    496     if(m < r) prepare_aux(m + 1, r, a);
    497 }
    498  
    499 vector<int> prepare(int len)
    500 {
    501     vector<int> a(len);
    502     prepare_aux(0, len - 1, a);
    503     return a;    
    504 }
    505  
    506 int get_left(int len)
    507 {
    508     int m = (len - 1) / 2;
    509     return m;
    510 }
    511  
    512 int get_right(int len)
    513 {
    514     int m = (len - 1) / 2;
    515     return len - m - 1;
    516 }
    517  
    518 vector<long long> get(int x)
    519 {
    520     vector<long long> res(x + 1);
    521     int m = (x - 1) / 2;
    522     int left = m;
    523     int right = x - m - 1;
    524     vector<int> prepared = prepare(x);
    525     //cout << x << endl;
    526     // swap m with something to the left
    527     {
    528         for(int i = 0; i < m; i++)
    529         {
    530             int lost = abs(m - i);
    531             //cout << i << " " << m << " " << lost << endl;
    532             res[lost]++;  
    533         }
    534     }
    535     // swap m with something to the right
    536     {
    537         for(int i = 0; i < right; i++)
    538         {
    539             int lost = i + 1;
    540             //cout << m << " " << i + m + 1 << " " << lost << endl;
    541             res[lost]++;
    542         }
    543     }
    544     // swap something to the left with something to the right
    545     {
    546         map<int, int> lost_left;
    547         map<int, int> lost_right;
    548         for(int i = 0; i < x; i++)
    549         {
    550             if(i == m) continue;
    551             if(i < m)
    552             {
    553                 int lost = get_right(prepared[i]) + 1;
    554                 lost_left[lost]++; 
    555             }
    556             else
    557             {
    558                 int lost = get_left(prepared[i]) + 1;
    559                 lost_right[lost]++;
    560             }
    561         }
    562         for(auto p : lost_left)
    563             for(auto p2 : lost_right)
    564             {
    565                 //cerr << p.first << " " << p.second << endl;
    566                 //cerr << p2.first << " " << p2.second << endl;
    567                 res[p.first + p2.first] += p.second * 1ll * p2.second;
    568             }
    569     }
    570     //cout << x << ":";
    571     //for(auto y : dp[x]) cout << " " << y;
    572     //cout << endl;
    573     return res;
    574 }                    
    575  
    576 void calc(int l, int r)
    577 {
    578     if(l > r) return;
    579     int m = (l + r) / 2;
    580     if(l < m) calc(l, m - 1);
    581     if(m < r) calc(m + 1, r);
    582     int len = r - l + 1;
    583     cnt[len]++;            
    584 }
    585  
    586 int main()
    587 {
    588     ios_base::sync_with_stdio(0);
    589     cin.tie(0);
    590     cin >> n;         
    591     ans.resize(n + 1);
    592     cnt.resize(n + 1);
    593     calc(0, n - 1);
    594     for(int i = 1; i <= n; i++)
    595         if(cnt[i] != 0)
    596         {
    597             auto g = get(i);
    598             for(int j = 0; j <= i; j++)
    599                 ans[n - j] += cnt[i] * g[j];
    600         }
    601     for(auto x : ans) cout << x << " ";
    602     cout << "\n";
    603     return 0;
    604 }
    605 ```