codeforces-scrape

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

1238.md (7073B)


      1 Source: https://codeforces.com/blog/entry/70450
      2 
      3 [1238A - Prime Subtraction](/contest/1238/problem/A "Educational Codeforces Round 74 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 
     16 for i in range(t):
     17 	x, y = map(int, input().split())
     18 	if(x - y > 1):
     19 		print('YES')
     20 	else:
     21 		print('NO')
     22 ```
     23 
     24 [1238B - Kill `Em All](/contest/1238/problem/B "Educational Codeforces Round 74 (Rated for Div. 2)")
     25 
     26 Idea: [Neon](/profile/Neon "Candidate Master Neon")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (Ne0n25)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36 
     37 using namespace std;
     38 
     39 #define forn(i, n) for (int i = 0; i < int(n); i++)
     40 
     41 const int N = 100 * 1000 + 13;
     42 
     43 int n, r;
     44 int a[N];
     45 
     46 void solve() {
     47 	scanf("%d%d", &n, &r);
     48 	forn(i, n) scanf("%d", &a[i]);
     49 	
     50 	sort(a, a + n);
     51 	n = unique(a, a + n) - a;
     52 	
     53 	int ans = 0;
     54 	for (int i = n - 1; i >= 0; i--) 
     55 		ans += (a[i] - ans * r > 0);
     56 
     57 	printf("%d\n", ans);
     58 }
     59 
     60 int main() {
     61 	int q;
     62 	scanf("%d", &q);
     63 	forn(i, q) solve();
     64 }
     65 ```
     66 
     67 [1238C - Standard Free2play](/contest/1238/problem/C "Educational Codeforces Round 74 (Rated for Div. 2)")
     68 
     69 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution (adedalic)**
     76 
     77 ```
     78 #include<bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
     83 #define sz(a) int((a).size())
     84 
     85 #define x first
     86 #define y second
     87 
     88 const int INF = int(1e9);
     89 
     90 int h, n;
     91 vector<int> p;
     92 
     93 inline bool read() {
     94 	if(!(cin >> h >> n))
     95 		return false;
     96 	p.resize(n);
     97 	fore(i, 0, n)
     98 		cin >> p[i];
     99 	return true;
    100 }
    101 
    102 inline void solve() {
    103 	int ans = 0;
    104 	
    105 	int lf = 0;
    106 	fore(i, 0, n) {
    107 		if (i > 0 && p[i - 1] > p[i] + 1) {
    108 			if (lf > 0)
    109 				ans += (i - lf) & 1;
    110 			else
    111 				ans += 1 - ((i - lf) & 1);
    112 			lf = i;
    113 		}
    114 	}
    115 	if (p[n - 1] > 1) {
    116 		if (lf != 0)
    117 			ans += (n - lf) & 1;
    118 		else
    119 			ans += 1 - ((n - lf) & 1);
    120 	}
    121 	
    122 	cout << ans << endl;
    123 }
    124 
    125 int main() {
    126 #ifdef _DEBUG
    127 	freopen("input.txt", "r", stdin);
    128 #endif
    129 	ios_base::sync_with_stdio(false);
    130 	cin.tie(0), cout.tie(0);
    131 	cout << fixed << setprecision(15);
    132 	
    133 	int tc; cin >> tc;
    134 	while(tc--) {
    135 		read();
    136 		solve();
    137 	}
    138 	return 0;
    139 }
    140 ```
    141 
    142 [1238D - AB-string](/contest/1238/problem/D "Educational Codeforces Round 74 (Rated for Div. 2)")
    143 
    144 Idea: [Roms](/profile/Roms "Master Roms")
    145 
    146 **Tutorial**
    147 
    148 Tutorial is loading...
    149 
    150 **Solution (Roms)**
    151 
    152 ```
    153 n = int(input())
    154 s = input()
    155 res = n * (n - 1) // 2
    156 
    157 for x in range(2):
    158 	cur = 1
    159 	for i in range(1, n):
    160 		if s[i] == s[i - 1]:
    161 			cur += 1
    162 		else:
    163 			res -= cur - x
    164 			cur = 1
    165 	s = s[::-1]
    166 
    167 print(res)
    168 ```
    169 
    170 [1238E - Keyboard Purchase](/contest/1238/problem/E "Educational Codeforces Round 74 (Rated for Div. 2)")
    171 
    172 Idea: [Roms](/profile/Roms "Master Roms")
    173 
    174 **Tutorial**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution (Roms)**
    179 
    180 ```
    181 #include <bits/stdc++.h>
    182 
    183 using namespace std;
    184 
    185 void upd(int &a, int b){
    186 	a = min(a, b);
    187 }
    188 
    189 const int N = 20;
    190 const int M = (1 << N) + 55;
    191 const int INF = int(1e9) + 100;
    192 
    193 int a, n;
    194 string s;
    195 int cnt[N][N];
    196 int d[M][N];
    197 int dp[M];
    198 int cntBit[M];
    199 int minBit[M];
    200 
    201 int main() {	
    202 	cin >> n >> a >> s;
    203 	
    204 	int B = (1 << a) - 1;
    205 	for(int i = 1; i < s.size(); ++i){
    206 		++cnt[s[i] - 'a'][s[i - 1] - 'a'];
    207 		++cnt[s[i - 1] - 'a'][s[i] - 'a'];
    208 	}
    209 	for(int i = 0; i < M; ++i)
    210 		dp[i] = INF;
    211 	dp[0] = 0;
    212 	for(int msk = 1; msk < M; ++msk){
    213 		cntBit[msk] = 1 + cntBit[msk & (msk - 1)];
    214 		for(int i = 0; i < N; ++i) if((msk >> i) & 1){
    215 			minBit[msk] = i;
    216 			break;
    217 		}
    218 	}
    219 	for(int msk = 1; msk < M; ++msk)
    220 		for(int i = 0; i < a; ++i){
    221 			int b = minBit[msk];
    222 			d[msk][i] = d[msk ^ (1 << b)][i] + cnt[i][b];		
    223 		}
    224 
    225 	for(int msk = 0; msk < (1 << a); ++msk){
    226 		for(int i = 0; i < a; ++i){
    227 			if((msk >> i) & 1) continue;
    228 			//i -> x
    229 			int pos = cntBit[msk];
    230 			int nmsk = msk | (1 << i);
    231 			upd(dp[nmsk], dp[msk] + pos * (d[msk][i] - d[B ^ nmsk][i]));
    232 		}
    233 	}	
    234 
    235 	cout << dp[B] << endl;
    236 	return 0;
    237 }
    238 ```
    239 
    240 [1238F - The Maximum Subtree](/contest/1238/problem/F "Educational Codeforces Round 74 (Rated for Div. 2)")
    241 
    242 Idea: [Roms](/profile/Roms "Master Roms")
    243 
    244 **Tutorial**
    245 
    246 Tutorial is loading...
    247 
    248 **Solution (Roms)**
    249 
    250 ```
    251 #include <bits/stdc++.h>
    252 
    253 using namespace std;
    254 
    255 const int N = int(3e5) + 99;
    256 
    257 int n;
    258 vector <int> g[N];
    259 int d[N];
    260 int dp[N][2];
    261 
    262 void dfs(int v, int p){
    263 	vector <int> d1;
    264 	dp[v][1] = d[v] - 1;
    265 	for(auto to : g[v]){
    266 		if(to == p) continue;
    267 		dfs(to, v);
    268 		dp[v][0] = max(dp[v][0], dp[to][0]);
    269 		if(g[to].size() > 1){
    270 			d1.push_back(dp[to][1]);
    271 			dp[v][1] = max(dp[v][1], d[v] + dp[to][1] - 1);	
    272 		}
    273 	}
    274 
    275 	sort(d1.rbegin(), d1.rend());
    276 	int x = d[v] + 1;
    277 	for(int i = 0; i < 2; ++i)
    278 		if(i < d1.size())
    279 			x += d1[i];
    280     dp[v][0] = max(dp[v][0], x);
    281 }
    282 
    283 int main() {	
    284     int q;
    285     scanf("%d", &q);
    286     for(int qc = 0; qc < q; ++qc){
    287     	scanf("%d", &n);
    288     	for(int i = 0; i < n; ++i){
    289     	    g[i].clear();
    290     	    d[i] = 0;
    291     	    dp[i][0] = dp[i][1] = 0;
    292     	}
    293     	for(int i = 0; i < n - 1; ++i){
    294     		int u, v;
    295     		scanf("%d %d", &u, &v);
    296     		--u, --v;
    297     		g[u].push_back(v), g[v].push_back(u);
    298     	}
    299     
    300         if(n <= 2){
    301             printf("%d\n", n);
    302             continue;
    303         }
    304         
    305     	for(int v = 0; v < n; ++v){
    306     		//d[v] = 1;
    307     		//for(auto to : g[v])	
    308     		//	d[v] += g[to].size() == 1;
    309     		d[v] = g[v].size();
    310     	}
    311         
    312         int r = -1;
    313         for(int v = 0; v < n; ++v)
    314             if(g[v].size() != 1)
    315                 r = v;
    316                 
    317     	dfs(r, r);
    318     	printf("%d\n", dp[r][0]);
    319     }
    320 	return 0;
    321 }                             	
    322 ```
    323 
    324 [1238G - Adilbek and the Watering System](/contest/1238/problem/G "Educational Codeforces Round 74 (Rated for Div. 2)")
    325 
    326 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    327 
    328 **Tutorial**
    329 
    330 Tutorial is loading...
    331 
    332 **Solution (Ne0n25)**
    333 
    334 ```
    335 #include <bits/stdc++.h>
    336 
    337 using namespace std;
    338 
    339 #define x first
    340 #define y second
    341 #define mp make_pair
    342 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    343 
    344 typedef long long li;
    345 typedef pair<int, int> pt;
    346 
    347 const int N = 500 * 1000 + 13;
    348 
    349 int n, m, c, c0;
    350 pair<int, pt> a[N];
    351 
    352 li solve() {
    353 	scanf("%d%d%d%d", &n, &m, &c, &c0);
    354 	forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].y.x, &a[i].y.y);
    355 	a[n++] = mp(m, mp(0, 0));
    356 	sort(a, a + n);
    357 
    358 	int sum = c0;
    359 	map<int, int> q;
    360 	q[0] = c0;
    361 	
    362 	li ans = 0;
    363 	forn(i, n) {
    364 		int x = a[i].x;
    365 		int cnt = a[i].y.x;
    366 		int cost = a[i].y.y;
    367 	
    368 		int dist = x - (i ? a[i - 1].x : 0);
    369 		while (!q.empty() && dist > 0) {
    370 			int can = min(q.begin()->y, dist);
    371 			ans += q.begin()->x * 1ll * can;
    372 			sum -= can;
    373 			dist -= can;
    374 			q.begin()->y -= can;
    375 			if (q.begin()->y == 0) q.erase(q.begin());
    376 		}
    377 		
    378 		if (dist > 0) 
    379 			return -1;
    380 		
    381 		int add = min(c - sum, cnt);
    382 		sum += add;
    383 		
    384 		while (add < cnt && !q.empty() && q.rbegin()->x > cost) {
    385 			if (cnt - add >= q.rbegin()->y) {
    386 				add += q.rbegin()->y;
    387 				q.erase(--q.end());
    388 			} else {
    389 				q.rbegin()->y -= cnt - add;
    390 				add = cnt;
    391 			}
    392 		}
    393 		
    394 		q[cost] += add;
    395 	}
    396 	
    397 	return ans;
    398 }
    399 
    400 int main() {
    401 	int q;
    402 	scanf("%d", &q);
    403 	forn(i, q) printf("%lld\n", solve());
    404 }
    405 ```