codeforces-scrape

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

1430.md (12676B)


      1 Source: https://codeforces.com/blog/entry/83614
      2 
      3 [1430A - Number of Apartments](/contest/1430/problem/A "Educational Codeforces Round 96 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (fcspartakm)**
     12 
     13 ```
     14 #include <iostream>
     15 #include <sstream>
     16 #include <cstdio>
     17 #include <vector>
     18 #include <cmath>
     19 #include <queue>
     20 #include <string>
     21 #include <cstring>
     22 #include <cassert>
     23 #include <iomanip>
     24 #include <algorithm>
     25 #include <set>
     26 #include <map>
     27 #include <ctime>
     28 #include <cmath>
     29 
     30 #define forn(i, n) for(int i=0;i<n;++i)
     31 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
     32 #define sz(v) int(v.size())
     33 #define all(v) v.begin(), v.end()
     34 #define pb push_back
     35 #define mp make_pair
     36 #define x first
     37 #define y1 ________y1
     38 #define y second
     39 #define ft first
     40 #define sc second
     41 #define pt pair<int, int>
     42 
     43 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
     44 template<typename X> inline X sqr(const X& a) { return a * a; }
     45 
     46 typedef long long li;
     47 typedef long double ld;
     48 
     49 using namespace std;
     50 
     51 const int INF = 1000 * 1000 * 1000;
     52 const ld EPS = 1e-9;
     53 const ld PI = acos(-1.0);
     54 
     55 li n;
     56 
     57 inline void read() {	
     58 	cin >> n;
     59 }
     60 
     61 inline void solve() {
     62 	if (n == 1 || n == 2 || n == 4) {
     63 		cout << -1 << endl;
     64 		return;
     65 	}
     66 	if (n % 3 == 0) {
     67 		cout << n / 3 << ' ' << 0 << ' ' << 0 << endl;
     68 	} else if (n % 3 == 1) {
     69 		cout << (n - 7) / 3 << ' ' << 0 << ' ' << 1 << endl;
     70 	} else {
     71 		cout << (n - 5) / 3 << ' ' << 1 << ' ' << 0 << endl;
     72 	}
     73 }
     74 
     75 int main () {
     76 #ifdef fcspartakm
     77     freopen("input.txt", "r", stdin);
     78     //freopen("output.txt", "w", stdout);
     79 #endif
     80     cerr << setprecision(10) << fixed;
     81     
     82     int t; cin >> t;
     83     while(t--) {
     84     	read();
     85     	solve();
     86     }
     87  
     88     //cerr << "TIME: " << clock() << endl;
     89 }
     90 ```
     91 
     92 [1430B - Barrels](/contest/1430/problem/B "Educational Codeforces Round 96 (Rated for Div. 2)")
     93 
     94 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution (fcspartakm)**
    101 
    102 ```
    103 #include <iostream>
    104 #include <sstream>
    105 #include <cstdio>
    106 #include <vector>
    107 #include <cmath>
    108 #include <queue>
    109 #include <string>
    110 #include <cstring>
    111 #include <cassert>
    112 #include <iomanip>
    113 #include <algorithm>
    114 #include <set>
    115 #include <map>
    116 #include <ctime>
    117 #include <cmath>
    118 
    119 #define forn(i, n) for(int i=0;i<n;++i)
    120 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    121 #define sz(v) int(v.size())
    122 #define all(v) v.begin(), v.end()
    123 #define pb push_back
    124 #define mp make_pair
    125 #define x first
    126 #define y1 ________y1
    127 #define y second
    128 #define ft first
    129 #define sc second
    130 #define pt pair<int, int>
    131 
    132 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    133 template<typename X> inline X sqr(const X& a) { return a * a; }
    134 
    135 typedef long long li;
    136 typedef long double ld;
    137 
    138 using namespace std;
    139 
    140 const int INF = 1000 * 1000 * 1000;
    141 const ld EPS = 1e-9;
    142 const ld PI = acos(-1.0);
    143 const int N = 200 * 1000 + 13;
    144 
    145 int n, k;
    146 int a[N];
    147 
    148 inline void read() {	
    149 	cin >> n >> k;
    150 	for (int i = 0; i < n; i++) cin >> a[i];
    151 }
    152 
    153 inline void solve() {
    154 	sort(a, a + n);
    155 	reverse(a, a + n);
    156 	li ans = 0;
    157 	for (int i = 0; i <= k; i++) {
    158 		ans += a[i];
    159 	}
    160 	cout << ans << endl;
    161 }
    162 
    163 int main () {
    164 #ifdef fcspartakm
    165     freopen("input.txt", "r", stdin);
    166     //freopen("output.txt", "w", stdout);
    167 #endif
    168     cerr << setprecision(10) << fixed;
    169     
    170     int t; cin >> t;
    171     while(t--) {
    172     	read();
    173     	solve();
    174  	}
    175     //cerr << "TIME: " << clock() << endl;
    176 }
    177 ```
    178 
    179 [1430C - Numbers on Whiteboard](/contest/1430/problem/C "Educational Codeforces Round 96 (Rated for Div. 2)")
    180 
    181 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution (fcspartakm)**
    188 
    189 ```
    190 #include <iostream>
    191 #include <sstream>
    192 #include <cstdio>
    193 #include <vector>
    194 #include <cmath>
    195 #include <queue>
    196 #include <string>
    197 #include <cstring>
    198 #include <cassert>
    199 #include <iomanip>
    200 #include <algorithm>
    201 #include <set>
    202 #include <map>
    203 #include <ctime>
    204 #include <cmath>
    205 
    206 #define forn(i, n) for(int i=0;i<n;++i)
    207 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    208 #define sz(v) int(v.size())
    209 #define all(v) v.begin(), v.end()
    210 #define pb push_back
    211 #define mp make_pair
    212 #define x first
    213 #define y1 ________y1
    214 #define y second
    215 #define ft first
    216 #define sc second
    217 #define pt pair<int, int>
    218 
    219 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    220 template<typename X> inline X sqr(const X& a) { return a * a; }
    221 
    222 typedef long long li;
    223 typedef long double ld;
    224 
    225 using namespace std;
    226 
    227 const int INF = 1000 * 1000 * 1000;
    228 const ld EPS = 1e-9;
    229 const ld PI = acos(-1.0);
    230 
    231 int n;
    232 
    233 inline void read() {	
    234 	cin >> n;
    235 }
    236 
    237 inline void solve() {
    238 	multiset<int> was;
    239 	for (int i = 1; i <= n; i++) {
    240 		was.insert(i);
    241 	}
    242 	vector<pair<int, int> > ans;
    243 	for (int i = 0; i < n - 1; i++) {
    244 		auto it = was.end();
    245 		it--;
    246 		int a = *it;
    247 		was.erase(it);
    248 		it = was.end();
    249 		it--;
    250 		int b = *it;
    251 		was.erase(it);
    252 		was.insert((a + b + 1) / 2);
    253 		ans.pb(mp(a, b));
    254 	}
    255 	cout << *was.begin() << endl;
    256 	for (int i = 0; i < sz(ans); i++) {
    257 		cout << ans[i].ft << ' ' << ans[i].sc << endl;
    258 	}	
    259 }
    260 
    261 int main () {
    262 #ifdef fcspartakm
    263     freopen("input.txt", "r", stdin);
    264     //freopen("output.txt", "w", stdout);
    265 #endif
    266     cerr << setprecision(10) << fixed;
    267     
    268     int t; cin >> t;
    269     while(t--) {
    270     	read();
    271     	solve();
    272     }
    273     //cerr << "TIME: " << clock() << endl;
    274 }
    275 ```
    276 
    277 [1430D - String Deletion](/contest/1430/problem/D "Educational Codeforces Round 96 (Rated for Div. 2)")
    278 
    279 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Solution (BledDest)**
    286 
    287 ```
    288 #include<bits/stdc++.h>
    289 
    290 using namespace std;
    291 
    292 char buf[200043];
    293 
    294 int main()
    295 {
    296 	int t;
    297 	scanf("%d", &t);
    298 	for(int tc = 1; tc <= t; tc++) {
    299 		int n;
    300 		scanf("%d", &n);
    301 		scanf("%s", buf);
    302 		string s = buf;
    303 		queue<int> q;
    304 		int cur = 0;
    305 		for(int i = 0; i < n; i++)
    306 		{
    307 		 	if(i > 0 && s[i] != s[i - 1])
    308 		 		cur++;
    309 		 	if(i > 0 && s[i] == s[i - 1])
    310 		 		q.push(cur);
    311 		}
    312 		int deleted = 0;       
    313 		int score = 0;
    314 		for(int i = 0; i < n; i++)
    315 		{
    316 			if(q.empty())
    317 				break;
    318 			q.pop();
    319 			deleted++;
    320 			score++;
    321 			while(!q.empty() && q.front() == i)
    322 			{
    323 				q.pop();
    324 				deleted++; 	
    325 			}
    326 			deleted++;
    327 			//cerr << deleted << endl;
    328 		}
    329 		score += (n - deleted + 1) / 2;
    330 		printf("%d\n", score);
    331 	}
    332 }
    333 ```
    334 
    335 [1430E - String Reversal](/contest/1430/problem/E "Educational Codeforces Round 96 (Rated for Div. 2)")
    336 
    337 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
    338 
    339 **Tutorial**
    340 
    341 Tutorial is loading...
    342 
    343 **Solution (fcspartakm)**
    344 
    345 ```
    346 #include <iostream>
    347 #include <sstream>
    348 #include <cstdio>
    349 #include <vector>
    350 #include <cmath>
    351 #include <queue>
    352 #include <string>
    353 #include <cstring>
    354 #include <cassert>
    355 #include <iomanip>
    356 #include <algorithm>
    357 #include <set>
    358 #include <map>
    359 #include <ctime>
    360 #include <cmath>
    361 
    362 #define forn(i, n) for(int i=0;i<n;++i)
    363 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    364 #define sz(v) int(v.size())
    365 #define all(v) v.begin(), v.end()
    366 #define pb push_back
    367 #define mp make_pair
    368 #define x first
    369 #define y1 ________y1
    370 #define y second
    371 #define ft first
    372 #define sc second
    373 #define pt pair<int, int>
    374 
    375 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    376 template<typename X> inline X sqr(const X& a) { return a * a; }
    377 
    378 typedef long long li;
    379 typedef long double ld;
    380 
    381 using namespace std;
    382 
    383 const int INF = 1000 * 1000 * 1000;
    384 const ld EPS = 1e-9;
    385 const ld PI = acos(-1.0);
    386 const int N = 200 * 1000 + 13;
    387 
    388 int n;
    389 string s;
    390 string revS;
    391 vector<int> posS[30];
    392 vector<int> posT[30];
    393 int cnt[30];
    394 int t[N];
    395 
    396 inline int sum (int r) {
    397 	int result = 0;
    398 	for (; r >= 0; r = (r & (r+1)) - 1)
    399 		result += t[r];
    400 	return result;
    401 }
    402 
    403 inline void inc (int i, int d) {
    404 	for (; i < n; i = (i | (i+1)))
    405 		t[i] += d;
    406 }
    407 
    408 int sum (int l, int r) {
    409 	return sum (r) - sum (l-1);
    410 }
    411      
    412 inline void read() {	
    413 	cin >> n >> s;
    414 }
    415 
    416 inline void solve() {
    417 	revS = s;
    418 	reverse(all(revS));
    419 	for (int i = 0; i < sz(s); i++) {
    420 		posS[s[i] - 'a'].pb(i);
    421 		posT[revS[i] - 'a'].pb(i);
    422 	}
    423 	li ans = 0;
    424 	for (int i = 0; i < sz(revS); i++) {
    425 		int let = revS[i] - 'a';
    426 		int cur = posS[let][cnt[let]];
    427 		int oldC = cur;
    428 		cur += sum(cur, n - 1);
    429 		int need = i;
    430 		ans += cur - need;
    431 		inc(oldC, 1);
    432 		cnt[let]++;
    433 	}
    434 	cout << ans << endl;
    435 }
    436 
    437 int main () {
    438 #ifdef fcspartakm
    439     freopen("input.txt", "r", stdin);
    440     //freopen("output.txt", "w", stdout);
    441 #endif
    442     srand(time(NULL));
    443     cerr << setprecision(10) << fixed;
    444     
    445     read();
    446     solve();
    447  
    448     //cerr << "TIME: " << clock() << endl;
    449 }
    450 ```
    451 
    452 [1430F - Realistic Gameplay](/contest/1430/problem/F "Educational Codeforces Round 96 (Rated for Div. 2)")
    453 
    454 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    455 
    456 **Tutorial**
    457 
    458 Tutorial is loading...
    459 
    460 **Solution (adedalic)**
    461 
    462 ```
    463 #include<bits/stdc++.h>
    464 
    465 using namespace std;
    466 
    467 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    468 #define sz(a) int((a).size())
    469 
    470 #define x first
    471 #define y second
    472 
    473 typedef long long li;
    474 typedef long double ld;
    475 typedef pair<int, int> pt;
    476 
    477 const int INF = int(1e9);
    478 const li INF64 = li(1e18);
    479 const ld EPS = 1e-9;
    480 
    481 int n, k;
    482 vector<int> l, r, a;
    483 
    484 inline bool read() {
    485 	if(!(cin >> n >> k))
    486 		return false;
    487 	l.resize(n);
    488 	r.resize(n);
    489 	a.resize(n);
    490 	
    491 	fore(i, 0, n)
    492 		cin >> l[i] >> r[i] >> a[i];
    493 	
    494 	return true;
    495 }
    496 
    497 inline void solve() {
    498 	vector<li> d(n + 1, INF64);
    499 	d[0] = 0;
    500 	
    501 	li ans = INF64;
    502 	fore(i, 0, n) {
    503 		li rem = k, total = d[i];
    504 		for (int j = i; j < n; j++) {
    505 			li cntReloads = (max(0LL, a[j] - rem) + k - 1) / k;
    506 			if (cntReloads > r[j] - l[j])
    507 				break;
    508 			
    509 			li newRem = (rem + cntReloads * k) - a[j];
    510 			total += a[j];
    511 			if (j + 1 < n) {
    512 				if (l[j] + cntReloads < l[j + 1])
    513 					d[j + 1] = min(d[j + 1], total + newRem);
    514 			} else
    515 				ans = min(ans, total);
    516 			rem = newRem;
    517 		}
    518 	}
    519 	if (ans > INF64 / 2)
    520 		ans = -1;
    521 	cout << ans << endl;
    522 }
    523 
    524 int main() {
    525 #ifdef _DEBUG
    526 	freopen("input.txt", "r", stdin);
    527 	int tt = clock();
    528 #endif
    529 	ios_base::sync_with_stdio(false);
    530 	cin.tie(0), cout.tie(0);
    531 	cout << fixed << setprecision(15);
    532 	
    533 	if(read()) {
    534 		solve();
    535 		
    536 #ifdef _DEBUG
    537 		cerr << "TIME = " << clock() - tt << endl;
    538 		tt = clock();
    539 #endif
    540 	}
    541 	return 0;
    542 }
    543 ```
    544 
    545 [1430G - Yet Another DAG Problem](/contest/1430/problem/G "Educational Codeforces Round 96 (Rated for Div. 2)")
    546 
    547 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    548 
    549 **Tutorial**
    550 
    551 Tutorial is loading...
    552 
    553 **Solution (BledDest)**
    554 
    555 ```
    556 #include<bits/stdc++.h>
    557 
    558 using namespace std;
    559 
    560 typedef long long li;
    561 
    562 const int N = 18;
    563 const int M = (1 << N);
    564 const li INF64 = li(1e18);
    565 
    566 int n, m;
    567 vector<int> g[N];
    568 li sum[N];
    569 int need_mask[N];
    570 li dp[N + 1][N + 1][M];
    571 bool p[N + 1][N + 1][M];
    572 
    573 vector<int> order;       
    574 vector<int> used;
    575 
    576 void dfs(int x, bool build_topo)
    577 {
    578     if(used[x])
    579     	return;
    580     used[x] = 1;
    581     for(auto y : g[x])
    582     	dfs(y, build_topo);
    583     if(build_topo)
    584     	order.push_back(x);
    585 }
    586 
    587 int main()
    588 {
    589 	cin >> n >> m;
    590 	for(int i = 0; i < m; i++)
    591 	{
    592 	 	int x, y, w;
    593 	 	cin >> x >> y >> w;
    594 	 	--x;
    595 	 	--y;
    596 	 	sum[x] += w;
    597 	 	sum[y] -= w;
    598 	 	g[x].push_back(y);
    599 	}
    600 	used.resize(n);
    601 	for(int i = 0; i < n; i++)
    602 		dfs(i, true);
    603 	for(int i = 0; i < n; i++)
    604 	{
    605 	 	used = vector<int>(n, 0);
    606 	 	dfs(i, false);
    607 	 	for(int j = 0; j < n; j++)
    608 	 		if(j != i && used[j] == 1)
    609 	 			need_mask[i] |= (1 << j);		
    610 	}
    611 	for(int i = 0; i <= n; i++)
    612 		for(int j = 0; j <= n; j++)
    613 			for(int k = 0; k < (1 << n); k++)
    614 				dp[i][j][k] = INF64;
    615 	dp[0][0][0] = 0;
    616 	reverse(order.begin(), order.end());
    617 	for(int i = 0; i < n; i++)
    618 		for(int j = 0; j <= n; j++)
    619 			for(int k = 0; k < (1 << n); k++)
    620 			{
    621 			 	if(dp[i][j][k] > INF64 / 2)
    622 			 		continue;
    623 			 	if(j == n)
    624 			 	{
    625 			 	 	if(dp[i + 1][0][k] > dp[i][j][k])
    626 			 	 	{
    627 			 	 	 	dp[i + 1][0][k] = dp[i][j][k];
    628 			 	 	 	p[i + 1][0][k] = false;
    629 			 	 	}
    630 			 	}
    631 			 	else
    632 			 	{
    633 			 		int v = order[j];
    634 			 		li add = sum[v] * i;
    635 			 		if(dp[i][j + 1][k] > dp[i][j][k])
    636 			 		{
    637 			 		 	dp[i][j + 1][k] = dp[i][j][k];
    638 			 		 	p[i][j + 1][k] = false;
    639 			 		}
    640 			 		if(((k & (1 << v)) == 0) && ((need_mask[v] & k) == need_mask[v]))
    641 			 		{
    642 			 		 	int nk = k | (1 << v);
    643 			 		 	if(dp[i][j + 1][nk] > dp[i][j][k] + add)
    644 			 		 	{
    645 			 		 	 	dp[i][j + 1][nk] = dp[i][j][k] + add;
    646 			 		 	 	p[i][j + 1][nk] = true;
    647 			 		 	}
    648 				 	}
    649 				}
    650 			}
    651 	vector<int> ans(n);
    652 	int i = n;
    653 	int j = 0;
    654 	int k = (1 << n) - 1;
    655 	while(i > 0 || j > 0 || k > 0)
    656 	{
    657 	 	if(j == 0)
    658 	 	{
    659 	 	 	j = n;
    660 	 	 	i--;
    661 	 	}
    662 	 	else
    663 	 	{
    664 	 	 	if(p[i][j][k])
    665 	 	 	{
    666 	 	 	 	int v = order[j - 1];
    667 	 	 	 	ans[v] = i;
    668 	 	 	 	k ^= (1 << v);
    669 	 		}
    670 	 		j--;
    671 	 	}
    672 	}
    673 	for(int i = 0; i < n; i++)
    674 		cout << ans[i] << " \n"[i == n - 1];
    675 }
    676 ```