codeforces-scrape

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

1251.md (8925B)


      1 Source: https://codeforces.com/blog/entry/70860
      2 
      3 [1251A - Broken Keyboard](/contest/1251/problem/A "Educational Codeforces Round 75 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Ne0n25)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 bool ans[26];
     19 
     20 void solve() {
     21 	string s;
     22 	cin >> s;
     23 	
     24 	memset(ans, 0, sizeof(ans));
     25 	
     26 	for (int i = 0; i < s.size(); i++) {
     27 		int j = i;
     28 		while (j + 1 < s.size() && s[j + 1] == s[i])
     29 			j++;
     30 		if ((j - i) % 2 == 0)
     31 			ans[s[i] - 'a'] = true;
     32 		i = j;
     33 	}
     34 	
     35 	for (int i = 0; i < 26; i++) if (ans[i])
     36 		cout << char('a' + i);
     37 	cout << endl;
     38 }
     39 
     40 int main() {
     41 	int q;
     42 	cin >> q;
     43 	while (q--) solve();
     44 }
     45 ```
     46 
     47 [1251B - Binary Palindromes](/contest/1251/problem/B "Educational Codeforces Round 75 (Rated for Div. 2)")
     48 
     49 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     50 
     51 **Tutorial**
     52 
     53 Tutorial is loading...
     54 
     55 **Solution (adedalic)**
     56 
     57 ```
     58 fun main() {
     59     val q = readLine()!!.toInt()
     60     for (ct in 1..q) {
     61         val n = readLine()!!.toInt()
     62         var (odd, evenGood, evenBad) = listOf(0, 0, 0)
     63         for (i in 1..n) {
     64             val s = readLine()!!
     65             when {
     66                 s.length % 2 == 1 -> odd++
     67                 s.count { it == '0' } % 2 == 0 -> evenGood++
     68                 else -> evenBad++
     69             }
     70         }
     71         println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0)
     72     }
     73 }
     74 ```
     75 
     76 [1251C - Minimize The Integer](/contest/1251/problem/C "Educational Codeforces Round 75 (Rated for Div. 2)")
     77 
     78 Idea: [Roms](/profile/Roms "Master Roms")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution (Roms)**
     85 
     86 ```
     87 #include <bits/stdc++.h>
     88 
     89 using namespace std;
     90 
     91 int t;
     92 string a;
     93 
     94 int main() {	
     95 	cin >> t;
     96 	for(int tc = 0; tc < t; ++tc){
     97 		cin >> a;
     98 		string s[2];
     99 		for(auto x : a)
    100 			s[int(x - '0') & 1] += x;
    101 		
    102 		reverse(s[0].begin(), s[0].end());
    103 		reverse(s[1].begin(), s[1].end());
    104 
    105 		string res = "";
    106 		while(!(s[0].empty() && s[1].empty())){
    107 			if(s[0].empty()){
    108 				res += s[1].back();
    109 				s[1].pop_back();
    110 				continue;
    111 			}
    112 			if(s[1].empty()){
    113 				res += s[0].back();
    114 				s[0].pop_back();
    115 				continue;
    116 			}
    117 
    118 			if(s[0].back() < s[1].back()){
    119 				res += s[0].back();
    120 				s[0].pop_back();
    121 			}
    122 			else{
    123 				res += s[1].back();
    124 				s[1].pop_back();
    125 			}
    126 		}
    127 
    128 		cout << res << endl;
    129 	}	
    130 	return 0;
    131 }
    132 ```
    133 
    134 [1251D - Salary Changing](/contest/1251/problem/D "Educational Codeforces Round 75 (Rated for Div. 2)")
    135 
    136 Idea: [Roms](/profile/Roms "Master Roms")
    137 
    138 **Tutorial**
    139 
    140 Tutorial is loading...
    141 
    142 **Solution (Roms)**
    143 
    144 ```
    145 #include <bits/stdc++.h>
    146 
    147 using namespace std;
    148 
    149 const int N = int(2e5) + 99;
    150 const int INF = int(1e9) + 100;
    151 
    152 int t;
    153 int n;
    154 long long s;
    155 pair<int, int> p[N];
    156 
    157 bool ok(int mid){
    158 	long long sum = 0;
    159 	int cnt = 0;
    160 	vector <int> v;
    161 	for(int i = 0; i < n; ++i){
    162 		if(p[i].second < mid)
    163 			sum += p[i].first;
    164 		else if(p[i].first >= mid){
    165 			sum += p[i].first;
    166 			++cnt;
    167 		}
    168 		else
    169 			v.push_back(p[i].first);
    170 	}
    171 
    172 	assert(is_sorted(v.begin(), v.end()));
    173 	
    174 	int need = max(0, (n + 1) / 2 - cnt);
    175 	if(need > v.size()) return false;
    176 	for(int i = 0; i < v.size(); ++i){
    177 		if(i < v.size() - need)
    178 			sum += v[i];
    179 		else
    180 			sum += mid;
    181 	}
    182 
    183 	return sum <= s;
    184 }
    185 
    186 int main() {	
    187 	scanf("%d", &t);
    188 	for(int tc = 0; tc < t; ++tc){
    189 		scanf("%d %lld", &n, &s);
    190 		for(int i = 0; i < n; ++i)
    191 			scanf("%d %d", &p[i].first, &p[i].second);
    192 		
    193 		sort(p, p + n);
    194 		int lf = 1, rg = INF; ///WA -> 10^9
    195 		while(rg - lf > 1){
    196 			int mid = (lf + rg) / 2;
    197 			if(ok(mid)) lf = mid;
    198 			else rg = mid;
    199 		}
    200 		
    201 		printf("%d\n", lf);
    202 	}
    203 	return 0;
    204 }                             	
    205 ```
    206 
    207 [1251E1 - Voting (Easy Version)](/contest/1251/problem/E1 "Educational Codeforces Round 75 (Rated for Div. 2)")
    208 
    209 [1251E2 - Voting (Hard Version)](/contest/1251/problem/E2 "Educational Codeforces Round 75 (Rated for Div. 2)")
    210 
    211 Idea: [Roms](/profile/Roms "Master Roms")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution (Roms)**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 
    222 using namespace std;
    223 
    224 const int N = int(3e5) + 99;
    225 
    226 int t, n;
    227 vector <int> v[N];
    228 
    229 int main() {	
    230 	int t;
    231 	scanf("%d", &t);
    232 	for(int tc = 0; tc < t; ++tc){
    233 		scanf("%d", &n);
    234 		for(int i = 0; i < n; ++i)
    235 			v[i].clear();
    236 		for(int i = 0; i < n; ++i){
    237 			int x, s;
    238 			scanf("%d %d", &x, &s);
    239 			v[x].push_back(s);
    240 		}		
    241 		
    242 		multiset <int > q;
    243 		long long res = 0;
    244 		int pref = n;
    245 		int cnt = 0;
    246 		for(int i = n - 1; i >= 0; --i){
    247 			pref -= v[i].size();
    248 			int need = i - pref;
    249 			for(auto x : v[i]) q.insert(x);
    250 
    251 			while(cnt < need){
    252 				++cnt;
    253 				res += *q.begin();				
    254 				q.erase(q.begin());
    255 			}
    256 		}		
    257 
    258         	printf("%lld\n", res);
    259         }
    260 	return 0;
    261 }                             	
    262 ```
    263 
    264 [1251F - Red-White Fence](/contest/1251/problem/F "Educational Codeforces Round 75 (Rated for Div. 2)")
    265 
    266 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [BledDest](/profile/BledDest "International Grandmaster BledDest")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution (BledDest)**
    273 
    274 ```
    275 #include<bits/stdc++.h>
    276 
    277 using namespace std;
    278 
    279 const int LOGN = 20;
    280 const int N = (1 << LOGN);
    281 const int MOD = 998244353;
    282 const int g = 3;
    283 
    284 #define forn(i, n) for(int i = 0; i < int(n); i++)
    285 
    286 inline int mul(int a, int b)
    287 {
    288 	return (a * 1ll * b) % MOD;
    289 }
    290 
    291 inline int norm(int a) 
    292 {
    293 	while(a >= MOD)
    294 		a -= MOD;
    295 	while(a < 0)
    296 		a += MOD;
    297 	return a;
    298 }
    299 
    300 inline int binPow(int a, int k) 
    301 {
    302 	int ans = 1;
    303 	while(k > 0) 
    304 	{
    305 		if(k & 1)
    306 			ans = mul(ans, a);
    307 		a = mul(a, a);
    308 		k >>= 1;
    309 	}
    310 	return ans;
    311 }
    312 
    313 inline int inv(int a) 
    314 {
    315 	return binPow(a, MOD - 2);
    316 }
    317 
    318 vector<int> w[LOGN];
    319 vector<int> iw[LOGN];
    320 vector<int> rv[LOGN];
    321 
    322 void precalc() 
    323 {
    324 	int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    325 	
    326 	for(int st = 0; st < LOGN; st++) 
    327 	{
    328 		w[st].assign(1 << st, 1);
    329 		iw[st].assign(1 << st, 1);
    330 		
    331 		int bw = binPow(wb, 1 << (LOGN - st - 1));
    332 		int ibw = inv(bw);
    333 		
    334 		int cw = 1;
    335 		int icw = 1;
    336 		
    337 		for(int k = 0; k < (1 << st); k++) 
    338 		{
    339 			w[st][k] = cw;
    340 			iw[st][k] = icw;
    341 			
    342 			cw = mul(cw, bw);
    343 			icw = mul(icw, ibw);
    344 		}
    345 		
    346 		rv[st].assign(1 << st, 0);
    347 		
    348 		if(st == 0) 
    349 		{
    350 			rv[st][0] = 0;
    351 			continue;
    352 		}
    353 		int h = (1 << (st - 1));
    354 		for(int k = 0; k < (1 << st); k++)
    355 			rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    356 	}
    357 }
    358 
    359 inline void fft(int a[N], int n, int ln, bool inverse) 
    360 {	
    361 	for(int i = 0; i < n; i++) 
    362 	{
    363 		int ni = rv[ln][i];
    364 		if(i < ni)
    365 			swap(a[i], a[ni]);
    366 	}
    367 	
    368 	for(int st = 0; (1 << st) < n; st++) 
    369 	{
    370 		int len = (1 << st);
    371 		for(int k = 0; k < n; k += (len << 1)) 
    372 		{
    373 			for(int pos = k; pos < k + len; pos++) 
    374 			{
    375 				int l = a[pos];
    376 				int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
    377 				
    378 				a[pos] = norm(l + r);
    379 				a[pos + len] = norm(l - r);
    380 			}
    381 		}
    382 	}
    383 	
    384 	if(inverse) 
    385 	{
    386 		int in = inv(n);
    387 		for(int i = 0; i < n; i++)
    388 			a[i] = mul(a[i], in);
    389 	}
    390 }
    391 
    392 int aa[N], bb[N], cc[N];
    393 
    394 inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 
    395 {
    396 	int n = 1, ln = 0;
    397 	while(n < (sza + szb))
    398 		n <<= 1, ln++;
    399 	for(int i = 0; i < n; i++)
    400 		aa[i] = (i < sza ? a[i] : 0);
    401 	for(int i = 0; i < n; i++)
    402 		bb[i] = (i < szb ? b[i] : 0);
    403 		
    404 	fft(aa, n, ln, false);
    405 	fft(bb, n, ln, false);
    406 	
    407 	for(int i = 0; i < n; i++)
    408 		cc[i] = mul(aa[i], bb[i]);
    409 		
    410 	fft(cc, n, ln, true);
    411 	
    412 	szc = n;
    413 	for(int i = 0; i < n; i++)
    414 		c[i] = cc[i];
    415 }
    416 
    417 vector<int> T[N];
    418 
    419 int a[N];
    420 int b[N];
    421 int n, k;
    422 int ans[N];
    423 int Q[N];
    424 int fact[N];
    425 int rfact[N];
    426 
    427 int auxa[N];
    428 int auxb[N];
    429 int auxc[N];
    430 
    431 int C(int n, int k)
    432 {
    433 	if(n < 0 || k < 0 || k > n) return 0;
    434 	return mul(fact[n], mul(rfact[k], rfact[n - k]));
    435 }
    436 
    437 vector<int> newtonExp(int a, int b, int p)
    438 {
    439 	vector<int> res(p + 1);
    440 	for(int i = 0; i <= p; i++)
    441 		res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i)));
    442 	return res;
    443 }
    444 
    445 int main()
    446 {
    447 	precalc();
    448 	fact[0] = 1;
    449 	for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
    450 	for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]);
    451 	
    452 	scanf("%d %d", &n, &k);
    453 	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    454 	for(int i = 0; i < k; i++) scanf("%d", &b[i]);
    455 	int q;
    456 	scanf("%d", &q);
    457 	for(int i = 0; i < q; i++) scanf("%d", &Q[i]);
    458 	
    459 	map<int, int> cnt;
    460 	for(int i = 0; i < n; i++)
    461 		cnt[a[i]]++;
    462 	
    463 	for(int i = 0; i < k; i++)
    464 	{
    465 		int redL = b[i];
    466 		int cnt1 = 0;
    467 		int cnt2 = 0;
    468 		for(auto x : cnt)
    469 		{
    470 			if(x.first >= redL) 
    471 				break;
    472 			if(x.second == 1)
    473 				cnt1++;
    474 			else
    475 				cnt2++;
    476 		}
    477 		memset(auxa, 0, sizeof auxa);
    478 		memset(auxb, 0, sizeof auxb);
    479 		memset(auxc, 0, sizeof auxc);
    480 		vector<int> p1 = newtonExp(2, 1, cnt1);
    481 		vector<int> p2 = newtonExp(1, 1, cnt2 * 2);
    482 		int sa = p1.size();
    483 		int sb = p2.size();
    484 		int sc;
    485 		for(int j = 0; j < sa; j++)
    486 			auxa[j] = p1[j];
    487 		for(int j = 0; j < sb; j++)
    488 			auxb[j] = p2[j];
    489 		multiply(auxa, sa, auxb, sb, auxc, sc);
    490 		for(int j = 0; j < q; j++)
    491 		{
    492 			int cntW = Q[j] / 2 - redL - 1;
    493 			if(cntW >= 0 && cntW < sc)
    494 				ans[j] = norm(ans[j] + auxc[cntW]);
    495 		}
    496 	}
    497 	
    498 	for(int i = 0; i < q; i++)
    499 		printf("%d\n", ans[i]);
    500 }
    501 ```