codeforces-scrape

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

2209.md (10132B)


      1 Source: https://codeforces.com/blog/entry/152272
      2 
      3 We hope you enjoyed the problems!
      4 
      5 **Rate the contest!**
      6 
      7 **Quality**
      8 
      9 * Excellent contest
     10 * Good contest
     11 * Average contest
     12 * Bad contest
     13 * Horrible contest
     14 
     15 **Difficulty**
     16 
     17 * Trivial contest
     18 * Easy contest
     19 * Average contest
     20 * Hard contest
     21 * Impossible contest
     22 
     23 [2209A - Flip Flops](/contest/2209/problem/A "Codeforces Round 1087 (Div. 2)")
     24 
     25 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ")
     26 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ")
     27 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ")
     28 
     29 **Solution**
     30 
     31 Tutorial is loading...
     32 
     33 **Code (C++)**
     34 
     35 ```
     36 #include<bits/stdc++.h>
     37 using namespace std;
     38 int n,a[109],k;
     39 long long C;
     40 int main(){
     41 	int t;
     42 	scanf("%d",&t);
     43 	while(t--){
     44 		scanf("%d %lld %d",&n,&C,&k);
     45 		for(int i = 1; i <= n; i ++){
     46 			scanf("%d",&a[i]);
     47 		}
     48 		sort(a + 1,a + n + 1);
     49 		for(int i = 1; i <= n; i ++){
     50 			if(a[i] > C)
     51 				break;
     52 			int o = min(1ll * k,C - a[i]);
     53 			k -= o;
     54 			C += a[i] + o;
     55 		}
     56 		printf("%lld\n",C);
     57 	}
     58 }
     59 ```
     60 
     61 **Rate the problem!**
     62 
     63 **Quality**
     64 
     65 * Excellent problem
     66 * Good problem
     67 * Average problem
     68 * Bad problem
     69 * Horrible problem
     70 
     71 **Difficulty**
     72 
     73 * Trivial problem
     74 * Easy problem
     75 * Average problem
     76 * Hard problem
     77 * Impossible problem
     78 
     79 [2209B - Array](/contest/2209/problem/B "Codeforces Round 1087 (Div. 2)")
     80 
     81 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ")
     82 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ")
     83 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ")
     84 
     85 **Solution**
     86 
     87 Tutorial is loading...
     88 
     89 **Code (Python)**
     90 
     91 ```
     92 for _ in range(int(input())):
     93     n = int(input())
     94     a = list(map(int, input().split()))
     95     print(*[max(sum(a[j] < a[i] for j in range(i + 1, n)), sum(a[j] > a[i] for j in range(i + 1, n))) for i in range(n)])
     96 ```
     97 
     98 **Code (C++)** 
     99 
    100 ```
    101 #include<bits/stdc++.h>
    102 using namespace std;
    103 int n,a[5009],bcnt,f1[5009],f2[5009];
    104 int main(){
    105 	int t;
    106 	scanf("%d",&t);
    107 	while(t--){
    108 		scanf("%d",&n);
    109 		for(int i = 1; i <= n; i ++){
    110 			scanf("%d",&a[i]);
    111 		}
    112 		for(int i = n; i >= 1; i --){
    113 		    f1[i] = f2[i] = 0;
    114 			for(int j = i + 1; j <= n; j ++)
    115 			    f1[i] += (a[i] > a[j]),f2[i] += (a[i] < a[j]);
    116 			f1[i] = max(f1[i],f2[i]);
    117 		}
    118 		for(int i = 1; i < n; i ++)
    119 		    printf("%d ",f1[i]);
    120 		printf("%d\n",f1[n]);
    121 	}
    122 }
    123 ```
    124 
    125 **Rate the problem!**
    126 
    127 **Quality**
    128 
    129 * Excellent problem
    130 * Good problem
    131 * Average problem
    132 * Bad problem
    133 * Horrible problem
    134 
    135 **Difficulty**
    136 
    137 * Trivial problem
    138 * Easy problem
    139 * Average problem
    140 * Hard problem
    141 * Impossible problem
    142 
    143 [2209C - Find the Zero](/contest/2209/problem/C "Codeforces Round 1087 (Div. 2)")
    144 
    145 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    146 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    147 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    148 
    149 **Solution**
    150 
    151 Tutorial is loading...
    152 
    153 **Code (Python)**
    154 
    155 ```
    156 for _ in range(int(input())):
    157     n = int(input())
    158     ans = -1
    159     for i in range(1, n):
    160         print("?", 2 * i + 1, 2 * i + 2, flush=True)
    161         if int(input()):
    162             ans = 2 * i + 1 
    163             break
    164     else:
    165         print("?", 1, 3, flush=True)
    166         if int(input()):
    167             ans = 1
    168         else:
    169             print("?", 1, 4, flush=True)
    170             if int(input()):
    171                 ans = 1
    172             else:
    173                 ans = 2
    174     print("!", ans, flush=True)
    175 ```
    176 
    177 **Rate the problem!**
    178 
    179 **Quality**
    180 
    181 * Excellent problem
    182 * Good problem
    183 * Average problem
    184 * Bad problem
    185 * Horrible problem
    186 
    187 **Difficulty**
    188 
    189 * Trivial problem
    190 * Easy problem
    191 * Average problem
    192 * Hard problem
    193 * Impossible problem
    194 
    195 [2209D - Ghostfires](/contest/2209/problem/D "Codeforces Round 1087 (Div. 2)")
    196 
    197 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ")
    198 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ")
    199 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ")
    200 
    201 **Solution**
    202 
    203 Tutorial is loading...
    204 
    205 **Code (C++)**
    206 
    207 ```
    208 #include<bits/stdc++.h>
    209 using namespace std;
    210 int t,r,g,b,rb,gb,rg;
    211 int main(){
    212 	scanf("%d",&t);
    213 	while(t--){
    214 		scanf("%d %d %d",&r,&g,&b);
    215 		while(((r > 0) + (g > 0) + (b > 0)) >> 1){
    216 			if(r <= g && r <= b)
    217 				gb ++,g --,b --;
    218 			else if(g <= r && g <= b)
    219 				rb ++,r --,b --;
    220 			else if(b <= r && b <= g)
    221 				rg ++,r --,g --;
    222 		}
    223 		if(g > 0){
    224 		    putchar('G');
    225 		    while(rg > 0)
    226 		   		putchar('R'),putchar('G'),rg --;
    227 		   	bool flg = false;
    228 		   	while(gb > 0)
    229 		   		putchar('B'),putchar('G'),gb --,flg = true;
    230 		    	if(flg){
    231 		   		while(rb > 0)
    232 		    			putchar('B'),putchar('R'),rb --;
    233 		    	}
    234 		    	else{
    235 		    		while(rb > 0)
    236 	    				putchar('R'),putchar('B'),rb --;
    237 		    	}
    238 		}
    239 		else if(r > 0){
    240 			putchar('R');
    241 			while(rg > 0)
    242 				putchar('G'),putchar('R'),rg --;
    243 			bool flg = false;
    244 			while(rb > 0)
    245 				putchar('B'),putchar('R'),rb --,flg = true;
    246 			if(flg){
    247 				while(gb > 0)
    248 					putchar('B'),putchar('G'),gb --;
    249 			}
    250 			else{
    251 				while(gb > 0)
    252 					putchar('G'),putchar('B'),gb --;
    253 			}
    254 		}
    255 		else{
    256 			if(b > 0)
    257 				putchar('B');
    258 			while(gb > 0)
    259 				putchar('G'),putchar('B'),gb --;
    260 			bool flg = false;
    261 			while(rb > 0)
    262 				putchar('R'),putchar('B'),rb --,flg = true;
    263 			if(flg){
    264 				while(rg > 0)
    265 					putchar('R'),putchar('G'),rg --;
    266 			}
    267 			else{
    268 				while(rg > 0)
    269 					putchar('G'),putchar('R'),rg --;
    270 			}
    271 		}
    272 		puts("");
    273 	}
    274 }
    275 ```
    276 
    277 **Rate the problem!**
    278 
    279 **Quality**
    280 
    281 * Excellent problem
    282 * Good problem
    283 * Average problem
    284 * Bad problem
    285 * Horrible problem
    286 
    287 **Difficulty**
    288 
    289 * Trivial problem
    290 * Easy problem
    291 * Average problem
    292 * Hard problem
    293 * Impossible problem
    294 
    295 [2209E - A Trivial String Problem](/contest/2209/problem/E "Codeforces Round 1087 (Div. 2)")
    296 
    297 * Idea: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    298 * Solution: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    299 * Editorial: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    300 
    301 **Solution**
    302 
    303 Tutorial is loading...
    304 
    305 **Code (Python)**
    306 
    307 ```
    308 import sys
    309 input = lambda: sys.stdin.readline().strip()
    310 def work(s):
    311     n = len(s)
    312     p = [0] * n
    313     b = [0] * n
    314     for i in range(1, n):
    315         j = p[i - 1]
    316         while j and s[i] != s[j]:
    317             j = p[j - 1]
    318         if s[i] == s[j]:
    319             j += 1
    320         p[i] = j
    321         if j == 0:
    322             b[i] = 0
    323         elif p[j - 1] == 0:
    324             b[i] = j
    325         else:
    326             b[i] = b[j - 1]
    327     ans = 0
    328     for i in range(n):
    329         p[i] = 0
    330         p[i] = p[i - b[i]] + 1
    331         ans += p[i]
    332     return ans
    333 
    334 for _ in range(int(input())):
    335     n, q = map(int, input().split())
    336     s = input()
    337     for _ in range(q):
    338         l, r = map(int, input().split())
    339         print(work(s[l - 1:r]))
    340 ```
    341 
    342 **Rate the problem!**
    343 
    344 **Quality**
    345 
    346 * Excellent problem
    347 * Good problem
    348 * Average problem
    349 * Bad problem
    350 * Horrible problem
    351 
    352 **Difficulty**
    353 
    354 * Trivial problem
    355 * Easy problem
    356 * Average problem
    357 * Hard problem
    358 * Impossible problem
    359 
    360 [2209F - Dynamic Values And Maximum Sum](/contest/2209/problem/F "Codeforces Round 1087 (Div. 2)")
    361 
    362 * Idea: [OtterZ](/profile/OtterZ "Master OtterZ")
    363 * Solution: [OtterZ](/profile/OtterZ "Master OtterZ")
    364 * Editorial: [OtterZ](/profile/OtterZ "Master OtterZ")
    365 
    366 **Solution**
    367 
    368 Tutorial is loading...
    369 
    370 **Code (C++)**
    371 
    372 ```
    373 #include<bits/stdc++.h>
    374 using namespace std;
    375 const int N = 300009;
    376 int n,k,t,a[N],tt[N];
    377 long long b[N],ans[N],sum,mxa;
    378 struct FLONG{
    379 	long long val;
    380 	int nd;
    381 	FLONG(long long v = 0,int d = 0):
    382 		val(v),nd(d)
    383 	{}
    384 	bool operator<(const FLONG &b)const{
    385 		return val > b.val || (val == b.val && nd < b.nd);
    386 	}
    387 };
    388 set<FLONG>s;
    389 set<FLONG> :: iterator o;
    390 struct pir{
    391 	int to,len;
    392 	pir(int t = 0,int l = 0):
    393 		to(t),len(l)
    394 	{}
    395 	bool operator<(const pir &b)const{
    396 		return len > b.len || (len == b.len && to < b.to);
    397 	}
    398 }mn[N],se[N],lf[N];
    399 vector<int>e[N];
    400 void srh(int v,int fa){
    401 	mn[v] = pir(v,0);
    402 	se[v] = pir(0,~0x3f3f3f3f);
    403 	lf[v] = pir(0,~0x3f3f3f3f);
    404 	for(unsigned i = 0; i < e[v].size(); i ++){
    405 		if(e[v][i] != fa){
    406 			srh(e[v][i],v);
    407 			pir th = mn[e[v][i]];
    408 			th.len ++;
    409 			if(th < se[v])
    410 				swap(th,se[v]);
    411 			if(se[v] < mn[v])
    412 				swap(se[v],mn[v]);
    413 		}
    414 	}
    415 }
    416 void gt1(){
    417 	sum = ans[1] = 0;
    418 	ans[1] += a[1];
    419 	for(int i = 2; i <= n; i ++){
    420 		b[mn[i].to] += a[i];
    421 		tt[i] = mn[i].to;
    422 		//printf("%d %d\n",i,tt[i]);
    423 	}
    424 	s.clear();
    425 	for(int i = 2; i <= n; i ++){
    426 		s.insert(FLONG(b[i],i));
    427 	}
    428 	o = s.begin();
    429 	ans[1] += o -> val;
    430 	sum += o -> val;
    431 	for(int i = 1; i < k - 1; i ++){
    432 		o ++;
    433 		ans[1] += o -> val;
    434 		sum += o -> val;
    435 	}
    436 	s.insert(FLONG(-1ll,0));
    437 	s.insert(FLONG(-2ll,0));
    438 }
    439 void era(int x){
    440 	FLONG u = FLONG(b[x],x);
    441 	if(!(*o < u)){
    442 		o ++;
    443 		sum += o -> val;
    444 		sum -= b[x];
    445 	}
    446 	s.erase(u);
    447 	//printf("%d %lld\n",x,sum);
    448 }
    449 void ins(int x){
    450 	FLONG u = FLONG(b[x],x);
    451 	s.insert(u);
    452 	if(!(*o < u)){
    453 		sum -= o -> val;
    454 		sum += b[x];
    455 		o --;
    456 	}
    457 	//printf("%d %lld\n",x,sum);
    458 }
    459 void stp(int x){
    460 	era(tt[x]);
    461 	b[tt[x]] -= a[x];
    462 	ins(tt[x]);
    463 	tt[x] = 0; 
    464 }
    465 void sett(int x,int ttp){
    466 	tt[x] = ttp;
    467 	era(tt[x]);
    468 	b[tt[x]] += a[x];
    469 	ins(tt[x]);
    470 }
    471 void srho(int v,int fa){
    472 	//printf(" %d %d\n",v,fa);
    473 	if(fa != 0){
    474 		stp(v);
    475 		era(v);
    476 		ins(fa);
    477 		sett(fa,lf[fa].to);
    478 		ans[v] = sum + a[v];
    479 	}
    480 	for(unsigned i = 0; i < e[v].size(); i ++){
    481 		if(e[v][i] != fa){
    482 			pir u = lf[fa];
    483 			u.len ++;
    484 			if(mn[v].to == mn[e[v][i]].to)
    485 				lf[v] = min(u,se[v]);
    486 			else
    487 				lf[v] = min(u,mn[v]);
    488 			srho(e[v][i],v);
    489 		}
    490 	}
    491 	if(fa != 0){
    492 		ins(v);
    493 		sett(v,mn[v].to);
    494 		stp(fa);
    495 		era(fa);
    496 	}
    497 }
    498 int main(){
    499 	scanf("%d",&t);
    500 	while(t--){
    501 		scanf("%d %d",&n,&k);
    502 		mxa = 0;
    503 		for(int i = 1; i <= n; i ++){
    504 			scanf("%d",&a[i]);
    505 			mxa = max(mxa,1ll * a[i]);
    506 			e[i].clear();
    507 			b[i] = 0;
    508 		}
    509 		for(int i = 1; i < n; i ++){
    510 			int u,v;
    511 			scanf("%d %d",&u,&v);
    512 			e[u].emplace_back(v);
    513 			e[v].emplace_back(u);
    514 		}
    515 		if(k == 1){
    516 			printf("%lld\n",mxa);
    517 			continue;
    518 		}
    519 		lf[0].len = ~0x3f3f3f3f;
    520 		srh(1,0);
    521 		gt1();
    522 		srho(1,0);
    523 		for(int i = 1; i <= n; i ++){
    524 			mxa = max(mxa,ans[i]);
    525 			//printf("%lld\n",ans[i]);
    526 		}
    527 		printf("%lld\n",mxa);
    528 	}
    529 }
    530 ```
    531 
    532 **Rate the problem!**
    533 
    534 **Quality**
    535 
    536 * Excellent problem
    537 * Good problem
    538 * Average problem
    539 * Bad problem
    540 * Horrible problem
    541 
    542 **Difficulty**
    543 
    544 * Trivial problem
    545 * Easy problem
    546 * Average problem
    547 * Hard problem
    548 * Impossible problem