codeforces-scrape

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

1156.md (8593B)


      1 Source: https://codeforces.com/blog/entry/66827
      2 
      3 [1156A - Inscribed Figures](/contest/1156/problem/A "Educational Codeforces Round 64 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (PikMike)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 #define forn(i, n) for(int i = 0; i < int(n); i++) 
     15 
     16 using namespace std;
     17 
     18 int main(){
     19 	int n;
     20 	scanf("%d", &n);
     21 	int sum = 0;
     22 	int lst = 1;
     23 	vector<int> figs;
     24 	forn(i, n){
     25 		int x;
     26 		scanf("%d", &x);
     27 		if (lst != 1 && x != 1){
     28 			puts("Infinite");
     29 			return 0;
     30 		}
     31 		if (x != 1){
     32 			figs.push_back(x);
     33 			sum += x + 1;
     34 			if (i != 0 && i != n - 1)
     35 				sum += x + 1;
     36 		}
     37 		lst = x;
     38 	}
     39 	forn(i, int(figs.size()) - 1) if (figs[i] == 3 && figs[i + 1] == 2)
     40 		--sum;
     41 	printf("Finite\n%d\n", sum);
     42 }
     43 ```
     44 
     45 [1156B - Ugly Pairs](/contest/1156/problem/B "Educational Codeforces Round 64 (Rated for Div. 2)")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (PikMike)**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 #define forn(i, n) for (int i = 0; i < int(n); i++)
     57 
     58 using namespace std;
     59 
     60 bool check(string s){
     61 	bool ok = true;
     62 	forn(i, int(s.size()) - 1)
     63 		ok &= (abs(s[i] - s[i + 1]) != 1);
     64 	return ok;
     65 }
     66 
     67 int main() {
     68 	int T;
     69 	scanf("%d", &T);
     70 	static char buf[120];
     71 	forn(_, T){
     72 		scanf("%s", buf);
     73 		string s = buf;
     74 		string odd = "", even = "";
     75 		forn(i, s.size()){
     76 			if (s[i] % 2 == 0)
     77 				odd += s[i];
     78 			else
     79 				even += s[i];
     80 		}
     81 		sort(odd.begin(), odd.end());
     82 		sort(even.begin(), even.end());
     83 		if (check(odd + even))
     84 			printf("%s\n", (odd + even).c_str());
     85 		else if (check(even + odd))
     86 			printf("%s\n", (even + odd).c_str());
     87 		else
     88 			puts("No answer");
     89 	}
     90 	return 0;
     91 }
     92 ```
     93 
     94 [1156C - Match Points](/contest/1156/problem/C "Educational Codeforces Round 64 (Rated for Div. 2)")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution (BledDest)**
    101 
    102 ```
    103 #include<bits/stdc++.h>
    104 
    105 using namespace std;
    106 
    107 const int N = 200043;
    108 
    109 int n, z;
    110 int a[N];
    111 
    112 int main()
    113 {
    114 	scanf("%d", &n);
    115 	scanf("%d", &z);
    116 	for(int i = 0; i < n; i++)
    117 		scanf("%d", &a[i]);
    118 	sort(a, a + n);
    119 	int l = 0;
    120 	int r = n / 2 + 1;
    121 	while(r - l > 1)
    122 	{
    123 		int m = (l + r) / 2;
    124 		bool good = true;
    125 		for(int i = 0; i < m; i++)
    126 			good &= (a[n - m + i] - a[i] >= z);
    127 		if(good)
    128 			l = m;
    129 		else
    130 			r = m;
    131 	}
    132 	cout << l << endl;
    133 }
    134 ```
    135 
    136 [1156D - 0-1-Tree](/contest/1156/problem/D "Educational Codeforces Round 64 (Rated for Div. 2)")
    137 
    138 **Tutorial**
    139 
    140 Tutorial is loading...
    141 
    142 **Solution (BledDest)**
    143 
    144 ```
    145 #include<bits/stdc++.h>
    146 
    147 using namespace std;
    148 
    149 const int N = 200043;
    150 
    151 int p[2][N];
    152 int siz[2][N];
    153 
    154 int get(int x, int c)
    155 {
    156 	if(p[c][x] == x)
    157 		return x;
    158 	return p[c][x] = get(p[c][x], c);
    159 }
    160 
    161 void merge(int x, int y, int c)
    162 {
    163 	x = get(x, c);
    164 	y = get(y, c);
    165 	if(siz[c][x] < siz[c][y])
    166 		swap(x, y);
    167 	p[c][y] = x;
    168 	siz[c][x] += siz[c][y];
    169 }
    170 
    171 int main()
    172 {
    173 	int n;
    174 	scanf("%d", &n);
    175 	for(int i = 0; i < n; i++)
    176 	{
    177 		p[0][i] = p[1][i] = i;
    178 		siz[0][i] = siz[1][i] = 1;
    179 	}
    180 	for(int i = 0; i < n - 1; i++)
    181 	{
    182 		int x, y, c;
    183 		scanf("%d %d %d", &x, &y, &c);
    184 		--x;
    185 		--y;
    186 		merge(x, y, c);
    187 	}
    188 	long long ans = 0;
    189 	for(int i = 0; i < n; i++)
    190 	{
    191 		if(p[0][i] == i)
    192 			ans += siz[0][i] * 1ll * (siz[0][i] - 1);
    193 		if(p[1][i] == i)
    194 			ans += siz[1][i] * 1ll * (siz[1][i] - 1);
    195 		ans += (siz[0][get(i, 0)] - 1) * 1ll * (siz[1][get(i, 1)] - 1);
    196 	}
    197 	cout << ans << endl;
    198 }
    199 ```
    200 
    201 [1156E - Special Segments of Permutation](/contest/1156/problem/E "Educational Codeforces Round 64 (Rated for Div. 2)")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution (BledDest)**
    208 
    209 ```
    210 #include<bits/stdc++.h>
    211 
    212 using namespace std;
    213 
    214 const int N = 200043;
    215 
    216 int lf[N];
    217 int rg[N];
    218 int n;
    219 int ans = 0;
    220 int p[N];
    221 int q[N];
    222 
    223 void update(int l, int r, int l2, int r2, int sum)
    224 {
    225 	for(int i = l; i <= r; i++)
    226 	{
    227 		int o = sum - p[i];
    228 		if(o >= 1 && o <= n && l2 <= q[o] && q[o] <= r2)
    229 			ans++;
    230 	}
    231 }
    232 
    233 int main()
    234 {
    235 	scanf("%d", &n);
    236 	for(int i = 0; i < n; i++)
    237 	{
    238 		scanf("%d", &p[i]);
    239 		q[p[i]] = i;
    240 	}
    241 	stack<pair<int, int> > s;
    242 	s.push(make_pair(n + 1, -1));
    243 	for(int i = 0; i < n; i++)
    244 	{
    245 		while(s.top().first < p[i])
    246 			s.pop();
    247 		lf[i] = s.top().second;
    248 		s.push(make_pair(p[i], i));
    249 	}
    250 	while(!s.empty())
    251 		s.pop();
    252 	s.push(make_pair(n + 1, n));
    253 	for(int i = n - 1; i >= 0; i--)
    254 	{
    255 		while(s.top().first < p[i])
    256 			s.pop();
    257 		rg[i] = s.top().second;
    258 		s.push(make_pair(p[i], i));
    259 	}
    260 	for(int i = 0; i < n; i++)
    261 	{
    262 	//	cerr << i << " " << lf[i] << " " << rg[i] << endl;
    263 		int lenl = i - lf[i] - 1;
    264 		int lenr = rg[i] - i - 1;
    265 		if(lenl == 0 || lenr == 0)
    266 			continue;
    267 		if(lenl < lenr)
    268 			update(lf[i] + 1, i - 1, i + 1, rg[i] - 1, p[i]);
    269 		else
    270 			update(i + 1, rg[i] - 1, lf[i] + 1, i - 1, p[i]);
    271 	}
    272 	cout << ans << endl;
    273 }
    274 ```
    275 
    276 [1156F - Card Bag](/contest/1156/problem/F "Educational Codeforces Round 64 (Rated for Div. 2)")
    277 
    278 **Tutorial**
    279 
    280 Tutorial is loading...
    281 
    282 **Solution (Roms)**
    283 
    284 ```
    285 #include<bits/stdc++.h>
    286 
    287 using namespace std;
    288 
    289 const int MOD = 998244353;
    290 const int N = 5005;
    291 
    292 void upd(int &a, int b){
    293     a += b;
    294     a %= MOD;
    295 }
    296 
    297 int mul(int a, int b){
    298     return (a * 1LL * b) % MOD;
    299 }
    300 
    301 int bp(int a, int n){
    302     int res = 1;
    303     for(; n > 0; n >>= 1){
    304         if(n & 1) res = mul(res, a);
    305         a = mul(a, a);
    306     }
    307     return res;
    308 }
    309 
    310 int getInv(int a){
    311     int ia = bp(a, MOD - 2);
    312     assert(mul(a, ia) == 1);
    313     return ia;
    314 }
    315 
    316 int n;
    317 int cnt[N];
    318 int suf[N];
    319 int dp[N][N];
    320 int sum[N][N];
    321 int inv[N];
    322 
    323 int main(){
    324     for(int i = 1; i < N; ++i)
    325         inv[i] = getInv(i);
    326         
    327     cin >> n;
    328     for(int i = 0; i < n; ++i){
    329         int x;
    330         cin >> x;
    331         ++cnt[x];
    332     }
    333     cnt[0] = 1;
    334     for(int i = N - 2; i >= 0; --i)
    335         suf[i] = suf[i + 1] + cnt[i];
    336         
    337     for(int x = n; x >= 0; --x)
    338         for(int y = n; y >= 0; --y){
    339             if(cnt[x] == 0){
    340                 upd(sum[x][y], sum[x + 1][y]);
    341                 continue;
    342             }
    343             int s = n - y;
    344             if(s <= 0){
    345                 upd(sum[x][y], sum[x + 1][y]);
    346                 continue;
    347             }
    348             
    349             upd(dp[x][y], mul(cnt[x] - 1, inv[s]));
    350             upd(dp[x][y], mul(sum[x + 1][y + 1], inv[s]));
    351             
    352             upd(sum[x][y], sum[x + 1][y]);
    353             upd(sum[x][y], mul(cnt[x], dp[x][y]));
    354         }
    355     
    356     cout << dp[0][0] << endl;
    357 	return 0;
    358 }
    359 ```
    360 
    361 [1156G - Optimizer](/contest/1156/problem/G "Educational Codeforces Round 64 (Rated for Div. 2)")
    362 
    363 **Tutorial**
    364 
    365 Tutorial is loading...
    366 
    367 **Solution (e-maxx)**
    368 
    369 [Solution](https://codeforces.com/contest/1156/submission/53641770) described in a tutorial.
    370 
    371 Jury's solution:
    372 
    373 ```
    374 #include <algorithm>
    375 #include <iostream>
    376 #include <map>
    377 #include <string>
    378 #include <vector>
    379 
    380 using namespace std;
    381 
    382 struct expr {
    383 	string t; // variable name or operation
    384 	expr * l, * r; // only if operation
    385 	long long hash;
    386 	
    387 	expr (string var)
    388 		: t(var), l(0), r(0), hash(0)
    389 		{ }
    390 	expr (char op, expr * l, expr * r)
    391 		: t(1,op), l(l), r(r), hash(0)
    392 		{ }
    393 
    394 	long long calc_hash() {
    395 		if (!hash)
    396 			if (!l) {
    397 				long long pw = 257;
    398 				for (size_t i=0; i<t.length(); ++i,  pw*=97)
    399 					hash += t[i] * pw;
    400 			}
    401 			else
    402 				hash += l->calc_hash() * t[0] + r->calc_hash() * 31;
    403 		return hash;
    404 	}
    405 };
    406 
    407 map<string,expr*> var;
    408 
    409 void inc_var_name (string & cur) {
    410 	for (size_t i=cur.length()-1; ; --i)
    411 		if (cur[i] < 'z') {
    412 			++cur[i];
    413 			break;
    414 		}
    415 		else
    416 			cur[i] = 'a';
    417 }
    418 
    419 string generate_var() {
    420 	static string cur = "aaaa";
    421 	while (var.count(cur))
    422 		inc_var_name (cur);
    423 	string res = cur;
    424 	inc_var_name (cur);
    425 	return res;
    426 }
    427 
    428 vector<string> ans;
    429 map<long long,string> calced;
    430 
    431 string restore (expr * e, string name = "") {
    432 	if (!e->l)  return e->t;
    433 	long long h = e->calc_hash();
    434 	if (calced.count(h))  return calced[h];
    435 	string l = restore (e->l),  r = restore (e->r);
    436 	string my = name.empty() ? generate_var() : name;
    437 	calced[h] = my;
    438 	ans.push_back (my + "=" + l + e->t + r);
    439 	return my;
    440 }
    441 
    442 int main() {
    443 	int n;
    444 	scanf ("%d\n", &n);
    445 	for (int i=0; i<n; ++i) {
    446 		static char buf[100];
    447 		gets (buf);
    448 		string s = buf;
    449 
    450 		size_t pos1 = s.find ('='),  pos2 = s.find_first_of ("&^$#");
    451 		string lname = s.substr (0, pos1);
    452 		string r1name = s.substr (pos1 + 1, pos2 - pos1 - 1);
    453 		if (!var.count(r1name))
    454 			var[r1name] = new expr (r1name);
    455 		if (pos2 != -1) {
    456 			string r2name = s.substr (pos2 + 1);
    457 			if (!var.count(r2name))
    458 				var[r2name] = new expr (r2name);
    459 			var[lname] = new expr (s [ s.find_first_of ("&^$#") ], var[r1name], var[r2name]);
    460 		}
    461 		else
    462 			var[lname] = var[r1name];
    463 	}
    464 
    465 	if (!var.count("res")) {
    466 		cout << 0;
    467 		return 0;
    468 	}
    469 
    470 	string name = restore (var["res"], "res");
    471 	if (name != "res")
    472 		ans.push_back ("res=" + name);
    473 
    474 	cout << ans.size() << endl;
    475 	for (size_t i=0; i<ans.size(); ++i)
    476 		puts (ans[i].c_str());
    477 
    478 }
    479 ```