codeforces-scrape

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

1082.md (8933B)


      1 Source: https://codeforces.com/blog/entry/63544
      2 
      3 [1082A - Vasya and Book](/contest/1082/problem/A "Educational Codeforces Round 55 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Ajosteen)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 const int INF = int(2e9) + 99;
     17 
     18 int n, x, y, d;
     19 
     20 int dist(int x, int y){
     21 	return (abs(x - y) + (d - 1)) / d;
     22 }
     23 
     24 int main() {
     25 	
     26 	int t;
     27 	cin >> t;
     28 	for(int i = 0; i < t; ++i){
     29     	cin >> n >> x >> y >> d;
     30     	
     31     	int len = abs(x - y);
     32     	int res = INF;
     33     	
     34     	if(len % d == 0) 
     35     		res = min(res, dist(x, y));
     36     	
     37     	len = y - 1;
     38     	if(len % d == 0)
     39     		res = min(res, dist(x, 1) + dist(1, y));
     40     	
     41     	len = n - y;
     42     	if(len % d == 0)
     43     		res = min(res, dist(x, n) + dist(n, y));
     44     		
     45     	if(res == INF)
     46     		res = -1;
     47     	
     48     	cout << res << endl;
     49 	}
     50 	
     51 	return 0;
     52 }
     53 ```
     54 
     55 [1082B - Vova and Trophies](/contest/1082/problem/B "Educational Codeforces Round 55 (Rated for Div. 2)")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (Ajosteen)**
     62 
     63 ```
     64 #include <bits/stdc++.h>
     65 
     66 using namespace std;
     67 
     68 int n;
     69 string s;
     70 
     71 int main() {
     72 	
     73 	cin >> n >> s;
     74 	
     75 	vector <int> l(n), r(n);
     76 	for(int i = 0; i < n; ++i){
     77 		if(s[i] == 'G'){
     78 			l[i] = 1;
     79 			if(i > 0) l[i] += l[i - 1];
     80 		}
     81 	}
     82 	for(int i = n - 1; i >= 0; --i){
     83 		if(s[i] == 'G'){
     84 			r[i] = 1;
     85 			if(i + 1 < n) r[i] += r[i + 1];
     86 		}
     87 	}
     88 	
     89 	
     90 	int res = 0;
     91 	int cntG = 0;
     92 	for(int i = 0; i < n; ++i)
     93 			cntG += s[i] == 'G';
     94 			
     95 	for(int i = 0; i < n; ++i){
     96 		if(s[i] == 'G') continue;
     97 		int nres = 1;
     98 		if(i > 0) nres += l[i - 1];
     99 		if(i + 1 < n) nres += r[i + 1];
    100 		res = max(res, nres);
    101 	}
    102 	
    103 	res = min(res, cntG);
    104 	if(cntG == n) res = cntG;
    105 	cout << res << endl;
    106 	return 0;
    107 }
    108 ```
    109 
    110 [1082C - Multi-Subject Competition](/contest/1082/problem/C "Educational Codeforces Round 55 (Rated for Div. 2)")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Solution (adedalic)**
    117 
    118 ```
    119 #include<bits/stdc++.h>
    120 using namespace std;
    121 
    122 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    123 #define sz(a) int((a).size())
    124 
    125 int n, m;
    126 vector<int> s, r;
    127 
    128 inline bool read() {
    129 	if(!(cin >> n >> m))
    130 		return false;
    131 	s.assign(n, 0);
    132 	r.assign(n, 0);
    133 	
    134 	fore(i, 0, n) {
    135 		assert(cin >> s[i] >> r[i]);
    136 		s[i]--;
    137 	}
    138 	return true;
    139 }
    140 
    141 vector< vector<int> > subs;
    142 
    143 inline void solve() {
    144 	subs.assign(m + 1, vector<int>());
    145 	
    146 	fore(i, 0, n)
    147 		subs[s[i]].push_back(r[i]);
    148 		
    149 	fore(id, 0, sz(subs)) {
    150 		sort(subs[id].begin(), subs[id].end());
    151 		reverse(subs[id].begin(), subs[id].end());
    152 	}
    153 	
    154 	vector<int> mx(n + 5, 0);
    155 	fore(id, 0, sz(subs)) {
    156 		int curSum = 0;
    157 		fore(i, 0, sz(subs[id])) {
    158 			curSum += subs[id][i];
    159 			if(curSum < 0)
    160 				break;
    161 				
    162 			mx[i + 1] += curSum;
    163 		}
    164 	}
    165 	
    166 	cout << *max_element(mx.begin(), mx.end()) << endl;
    167 }
    168 
    169 int main() {
    170 #ifdef _DEBUG
    171 	freopen("input.txt", "r", stdin);
    172 	int tt = clock();
    173 #endif
    174 	cout << fixed << setprecision(15);
    175 	
    176 	if(read()) {
    177 		solve();
    178 		
    179 #ifdef _DEBUG
    180 		cerr << "TIME = " << clock() - tt << endl;
    181 		tt = clock();
    182 #endif
    183 	}
    184 	return 0;
    185 }
    186 ```
    187 
    188 [1082D - Maximum Diameter Graph](/contest/1082/problem/D "Educational Codeforces Round 55 (Rated for Div. 2)")
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Solution (PikMike)**
    195 
    196 ```
    197 #include <bits/stdc++.h>
    198 
    199 #define forn(i, n) for (int i = 0; i < int(n); i++)
    200 
    201 using namespace std;
    202 
    203 const int N = 1000 + 7;
    204 
    205 int n;
    206 int a[N];
    207 
    208 int main() {
    209 	scanf("%d", &n);
    210 	forn(i, n)
    211 		scanf("%d", &a[i]);
    212 	
    213 	int sum = 0;
    214 	forn(i, n)
    215 		sum += a[i];
    216 	
    217 	if (sum < 2 * n - 2){
    218 		puts("NO");
    219 		return 0;
    220 	}
    221 	
    222 	vector<int> ones;
    223 	forn(i, n) if (a[i] == 1){
    224 		a[i] = 0;
    225 		ones.push_back(i);
    226 	}
    227 	
    228 	int t = ones.size();
    229 	int dm = (n - t) - 1 + min(2, t);
    230 	printf("YES %d\n%d\n", dm, n - 1);
    231 	
    232 	int lst = -1;
    233 	if (!ones.empty()){
    234 		lst = ones.back();
    235 		ones.pop_back();
    236 	}
    237 	
    238 	forn(i, n){
    239 		if (a[i] > 1){
    240 			if (lst != -1){
    241 				--a[lst];
    242 				--a[i];
    243 				printf("%d %d\n", lst + 1, i + 1);
    244 			}
    245 			lst = i;
    246 		}
    247 	}
    248 	
    249 	for (int i = n - 1; i >= 0; --i){
    250 		while (!ones.empty() && a[i] > 0){
    251 			--a[i];
    252 			printf("%d %d\n", i + 1, ones.back() + 1);
    253 			ones.pop_back();
    254 		}
    255 	}
    256 	return 0;
    257 }
    258 ```
    259 
    260 [1082E - Increasing Frequency](/contest/1082/problem/E "Educational Codeforces Round 55 (Rated for Div. 2)")
    261 
    262 **Tutorial**
    263 
    264 Tutorial is loading...
    265 
    266 **Solution (adedalic)**
    267 
    268 ```
    269 #include<bits/stdc++.h>
    270 using namespace std;
    271 
    272 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    273 #define sz(a) int((a).size())
    274 
    275 const int INF = int(1e9);
    276 
    277 int n, c;
    278 vector<int> a;
    279 
    280 inline bool read() {
    281 	if(!(cin >> n >> c))
    282 		return false;
    283 	a.assign(n, 0);
    284 	fore(i, 0, n)
    285 		assert(scanf("%d", &a[i]) == 1);
    286 	return true;
    287 }
    288 
    289 vector<int> cntC;
    290 
    291 int getCnt(int l, int r) {
    292 	return cntC[r] - cntC[l];
    293 }
    294 
    295 vector< vector<int> > segs;
    296 vector<int> lst;
    297 
    298 int maxSegment(const vector<int> &s) {
    299 	int mx = -INF;
    300 	
    301 	int bal = 0;
    302 	fore(i, 0, sz(s)) {
    303 		bal = max(0, bal + s[i]);
    304 		mx = max(mx, bal);
    305 	}
    306 	return mx;
    307 }
    308 
    309 inline void solve() {
    310 	cntC.assign(n + 1, 0);
    311 	fore(i, 0, n)
    312 		cntC[i + 1] = cntC[i] + (a[i] == c);
    313 	
    314 	int cntDif = *max_element(a.begin(), a.end()) + 1;
    315 	segs.assign(cntDif, vector<int>());
    316 	lst.assign(cntDif, -1);
    317 	
    318 	fore(i, 0, n) {
    319 		segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
    320 		lst[a[i]] = i;
    321 		segs[a[i]].push_back(1);
    322 	}
    323 	fore(v, 0, cntDif)
    324 		segs[v].push_back(-getCnt(lst[v] + 1, n));
    325 		
    326 	int ans = 0;
    327 	fore(v, 0, cntDif) {
    328 		if(v == c) continue;
    329 		ans = max(ans, maxSegment(segs[v]));
    330 	}
    331 	
    332 	cout << getCnt(0, n) + ans << endl;
    333 }
    334 
    335 int main() {
    336 #ifdef _DEBUG
    337 	freopen("input.txt", "r", stdin);
    338 	int tt = clock();
    339 #endif
    340 	cout << fixed << setprecision(15);
    341 	
    342 	if(read()) {
    343 		solve();
    344 		
    345 #ifdef _DEBUG
    346 		cerr << "TIME = " << clock() - tt << endl;
    347 		tt = clock();
    348 #endif
    349 	}
    350 	return 0;
    351 }
    352 ```
    353 
    354 [1082F - Speed Dial](/contest/1082/problem/F "Educational Codeforces Round 55 (Rated for Div. 2)")
    355 
    356 **Tutorial**
    357 
    358 Tutorial is loading...
    359 
    360 **Solution (PikMike)**
    361 
    362 ```
    363 #include <bits/stdc++.h>
    364 
    365 #define forn(i, n) for (int i = 0; i < int(n); i++)
    366 
    367 using namespace std;
    368 
    369 const int N = 500 + 7;
    370 const int M = 11;
    371 const int INF = 1e9;
    372 
    373 struct node{
    374 	int nxt[10];
    375 	int cnt;
    376 	node(){
    377 		memset(nxt, -1, sizeof(nxt));
    378 		cnt = 0;
    379 	}
    380 };
    381 
    382 node trie[N];
    383 int cnt;
    384 int h[N];
    385 
    386 void add(string s, int m){
    387 	int cur = 0;
    388 	forn(i, s.size()){
    389 		int c = s[i] - '0';
    390 		if (trie[cur].nxt[c] == -1){
    391 			trie[cur].nxt[c] = cnt;
    392 			h[cnt] = h[cur] + 1;
    393 			++cnt;
    394 		}
    395 		cur = trie[cur].nxt[c];
    396 	}
    397 	trie[cur].cnt += m;
    398 }
    399 
    400 int n, k;
    401 
    402 int dp[N][M][N];
    403 int dp2[N][M][N][M];
    404 
    405 int calc(int x, int rem, int k){
    406 	if (dp[x][rem][k] != -1)
    407 		return dp[x][rem][k];
    408 	
    409 	vector<int> ch;
    410 	forn(i, 10) if (trie[x].nxt[i] != -1)
    411 		ch.push_back(trie[x].nxt[i]);
    412 	
    413 	dp[x][rem][k] = INF;
    414 	if (rem > 0)
    415 		dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x));
    416 	
    417 	dp2[x][rem][k][ch.size()] = 0;
    418 	for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1)
    419 		dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]);
    420 	
    421 	dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt);
    422 	
    423 	return dp[x][rem][k];
    424 }
    425 
    426 int main() {
    427 	trie[0] = node();
    428 	cnt = 1;
    429 	
    430 	cin >> n >> k;
    431 	forn(i, n){
    432 		string s;
    433 		int m;
    434 		cin >> s >> m;
    435 		add(s, m);
    436 	}
    437 	
    438 	memset(dp, -1, sizeof(dp));
    439 	
    440 	forn(i, N) forn(j, M) forn(l, N) forn(t, M)
    441 		dp2[i][j][l][t] = INF;
    442 	
    443 	int ans = calc(0, k, 0);
    444 	
    445 	cout << ans << endl;
    446 	return 0;
    447 }
    448 ```
    449 
    450 [1082G - Petya and Graph](/contest/1082/problem/G "Educational Codeforces Round 55 (Rated for Div. 2)")
    451 
    452 **Tutorial**
    453 
    454 Tutorial is loading...
    455 
    456 **Solution (Ajosteen)**
    457 
    458 ```
    459 #include <bits/stdc++.h>
    460 
    461 using namespace std;
    462 
    463 typedef long long li;
    464 
    465 const int N = 2009;
    466 const int INF = int(1e9) + 777;
    467 
    468 struct edge{
    469 	int to, f, c;
    470 	edge () {}
    471 	edge (int to, int f, int c) : to(to), f(f), c(c) {}
    472 };
    473 
    474 int n, m;
    475 int s, t;
    476 vector<edge> edges;
    477 vector <int> g[N];
    478 int u[N], cu;
    479 
    480 void addEdge(int v, int to, int cap){
    481 
    482 	g[v].push_back(edges.size());
    483 	edges.push_back(edge(to, 0, cap));
    484 
    485 	g[to].push_back(edges.size());
    486 	edges.push_back(edge(v, 0, 0));
    487 }
    488 
    489 int dfs(int v, int need){
    490 	if(v == t) return need;
    491 	u[v] = cu;
    492 	for(auto to : g[v]){
    493 		edge &e = edges[to];
    494 		if(u[e.to] != cu && e.c - e.f >= need){
    495 			int add = dfs(e.to, need);
    496 			if(add > 0){
    497 				edges[to].f += add;
    498 				edges[to ^ 1].f -= add;
    499 				return add;
    500 			}
    501 		}
    502 	}
    503 	return 0;
    504 }
    505 
    506 li enlarge(int k){
    507 	li res = 0;
    508 	while(true){
    509 		++cu;
    510 		int add = dfs(s, k);
    511 		res += add;
    512 		if(add == 0) break;
    513 	}
    514 	return res;
    515 }
    516 
    517 li maxFlow(){
    518 	li flow = 0;
    519 	for(int k = (1 << 29); k > 0; k >>= 1){
    520 		flow += enlarge(k);
    521 	}
    522 	return flow;
    523 }
    524 
    525 int main() {
    526 	//freopen("input.txt", "r", stdin);
    527 	int nn, mm;
    528 	cin >> nn >> mm;
    529 	n = nn + mm + 5;
    530 	m = nn + mm + mm + mm + 5;
    531 	s = n - 1, t = n - 2;
    532 	
    533 	for(int i = 0; i < nn; ++i){
    534 		int a;
    535 		cin >> a;
    536 		addEdge(i + mm, t, a);
    537 	}
    538 
    539 	li sum = 0;
    540 	for(int i = 0; i < mm; ++i){
    541 		int u, v, w;
    542 		cin >> u >> v >> w;
    543 		--u, --v;
    544 		sum += w;
    545 		
    546 		addEdge(s, i, w);
    547 		addEdge(i, u + mm, INF);
    548 		addEdge(i, v + mm, INF);
    549 	}
    550 	
    551 	li fl = maxFlow();
    552 	cout << sum - fl << endl;
    553 	
    554 	return 0;
    555 }
    556 ```