codeforces-scrape

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

1463.md (7834B)


      1 Source: https://codeforces.com/blog/entry/85707
      2 
      3 [1463A - Dungeon](/contest/1463/problem/A "Educational Codeforces Round 100 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Ne0n25)**
     12 
     13 ```
     14 for i in range(int(input())):
     15 	a, b, c = map(int, input().split())
     16 	if (a + b + c) % 9 != 0:
     17 		print("NO")
     18 	else:
     19 	    print("YES" if min(a, b, c) >= (a + b + c) // 9 else "NO")
     20 ```
     21 
     22 [1463B - Find The Array](/contest/1463/problem/B "Educational Codeforces Round 100 (Rated for Div. 2)")
     23 
     24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (Ne0n25)**
     31 
     32 ```
     33 for t in range(int(input())):
     34 	n = int(input())
     35 	a = list(map(int, input().split()))
     36 	s = sum(a)
     37 	cur = [0, 0]
     38 	for i in range(n):
     39 		cur[i % 2] += a[i] - 1
     40 	for j in range(2):
     41 		if 2 * cur[j] > s:
     42 			continue
     43 		for i in range(n):
     44 			if i % 2 == j:
     45 				a[i] = 1
     46 		break
     47 	print(*a)
     48 ```
     49 
     50 [1463C - Busy Robot](/contest/1463/problem/C "Educational Codeforces Round 100 (Rated for Div. 2)")
     51 
     52 Idea: [KAN](/profile/KAN "Legendary Grandmaster KAN")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (pikmike)**
     59 
     60 ```
     61 def inside(l, r, x):
     62 	return min(l, r) <= x <= max(l, r)
     63 
     64 def sg(x):
     65 	return -1 if x < 0 else int(x > 0)
     66 
     67 for _ in range(int(input())):
     68 	n = int(input())
     69 	qs = []
     70 	for i in range(n):
     71 		qs.append(list(map(int, input().split())))
     72 	qs.append([4*10**9, 0])
     73 	ans = 0
     74 	pos, dr, lft = 0, 0, 0
     75 	for i in range(n):
     76 		t, x = qs[i]
     77 		tn = qs[i + 1][0]
     78 		if lft == 0:
     79 			lft = abs(pos - x)
     80 			dr = sg(x - pos)
     81 		tmp = min(lft, tn - t)
     82 		if inside(pos, pos + dr * tmp, x):
     83 			ans += 1
     84 		pos += dr * tmp
     85 		lft -= tmp
     86 	print(ans)
     87 ```
     88 
     89 [1463D - Pairs](/contest/1463/problem/D "Educational Codeforces Round 100 (Rated for Div. 2)")
     90 
     91 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution 1 (adedalic)**
     98 
     99 ```
    100 #include<bits/stdc++.h>
    101 
    102 using namespace std;
    103 
    104 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    105 #define sz(a) int((a).size())
    106 
    107 const int INF = int(1e9);
    108 
    109 int n;
    110 vector<int> b;
    111 
    112 inline bool read() {
    113 	if(!(cin >> n))
    114 		return false;
    115 	b.resize(n);
    116 	fore (i, 0, n)
    117 		cin >> b[i];
    118 	return true;
    119 }
    120 
    121 bool ok(const vector<int> &a, const vector<int> &b, int cnt) {
    122 	fore (i, 0, cnt) {
    123 		if (a[i] >= b[sz(b) - cnt + i])
    124 			return false;
    125 	}
    126 	return true;
    127 }
    128 
    129 inline void solve() {
    130 	vector<int> nb;
    131 	fore (i, 1, 2 * n + 1) {
    132 		if (!binary_search(b.begin(), b.end(), i))
    133 			nb.push_back(i);
    134 	}
    135 	
    136 	int mx[2] = {-1, -1};
    137 	fore (k, 0, 2) {
    138 		int lf = 0, rg = n + 1;
    139 		while (rg - lf > 1) {
    140 			int mid = (lf + rg) / 2;
    141 			if (ok(b, nb, mid))
    142 				lf = mid;
    143 			else
    144 				rg = mid;
    145 		}
    146 		mx[k] = lf;
    147 		if (!ok(nb, b, n - lf)) {
    148 			cout << 0 << endl;
    149 			return;
    150 		}
    151 		swap(b, nb);
    152 	}
    153 	
    154 	assert(n - mx[1] <= mx[0]);
    155 	cout << mx[0] - (n - mx[1]) + 1 << endl;
    156 }
    157 
    158 int main() {
    159 #ifdef _DEBUG
    160 	freopen("input.txt", "r", stdin);
    161 	int tt = clock();
    162 #endif
    163 	ios_base::sync_with_stdio(false);
    164 	cin.tie(0), cout.tie(0);
    165 	cout << fixed << setprecision(15);
    166 	
    167 	int t; cin >> t;
    168 	while(t--) {
    169 	    read();
    170 		solve();
    171 		
    172 #ifdef _DEBUG
    173 		cerr << "TIME = " << clock() - tt << endl;
    174 		tt = clock();
    175 #endif
    176 	}
    177 	return 0;
    178 }
    179 ```
    180 
    181 **Solution 2 (adedalic)**
    182 
    183 ```
    184 #include<bits/stdc++.h>
    185 
    186 using namespace std;
    187 
    188 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    189 #define sz(a) int((a).size())
    190 
    191 const int INF = int(1e9);
    192 
    193 int n;
    194 vector<int> b;
    195 
    196 inline bool read() {
    197 	if(!(cin >> n))
    198 		return false;
    199 	b.resize(n);
    200 	fore (i, 0, n)
    201 		cin >> b[i];
    202 	return true;
    203 }
    204 
    205 int getMax(const vector<int> &a, const vector<int> &b) {
    206 	int uk = 0;
    207 	fore (i, 0, sz(a)) {
    208 		while (uk < sz(b) && b[uk] < a[i])
    209 			uk++;
    210 		if (uk >= sz(b))
    211 			return i;
    212 		uk++;
    213 	}
    214 	return sz(a);
    215 }
    216 
    217 inline void solve() {
    218 	vector<int> nb;
    219 	fore (i, 1, 2 * n + 1) {
    220 		if (!binary_search(b.begin(), b.end(), i))
    221 			nb.push_back(i);
    222 	}
    223 	
    224 	int mxX = getMax(b, nb);
    225 	int mnX = n - getMax(nb, b);
    226 	
    227 	cout << mxX - mnX + 1 << endl;
    228 }
    229 
    230 int main() {
    231 #ifdef _DEBUG
    232 	freopen("input.txt", "r", stdin);
    233 	int tt = clock();
    234 #endif
    235 	ios_base::sync_with_stdio(false);
    236 	cin.tie(0), cout.tie(0);
    237 	cout << fixed << setprecision(15);
    238 	
    239 	int t; cin >> t;
    240 	while(t--) {
    241 	    read();
    242 		solve();
    243 		
    244 #ifdef _DEBUG
    245 		cerr << "TIME = " << clock() - tt << endl;
    246 		tt = clock();
    247 #endif
    248 	}
    249 	return 0;
    250 }
    251 ```
    252 
    253 [1463E - Plan of Lectures](/contest/1463/problem/E "Educational Codeforces Round 100 (Rated for Div. 2)")
    254 
    255 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    256 
    257 **Tutorial**
    258 
    259 Tutorial is loading...
    260 
    261 **Solution (pikmike)**
    262 
    263 ```
    264 #include <bits/stdc++.h>
    265 
    266 using namespace std;
    267 
    268 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    269 
    270 vector<vector<int>> g, h, ng;
    271 
    272 vector<int> rk, p;
    273 
    274 int getp(int a){
    275 	return a == p[a] ? a : p[a] = getp(p[a]);
    276 }
    277 
    278 void unite(int a, int b){
    279 	a = getp(a), b = getp(b);
    280 	if (a == b) return;
    281 	if (rk[a] < rk[b]) swap(a, b);
    282 	rk[a] += rk[b];
    283 	p[b] = a;
    284 }
    285 
    286 vector<vector<int>> comp;
    287 
    288 vector<int> ord;
    289 vector<int> used;
    290 bool fl;
    291 
    292 void ts(int v, const vector<vector<int>> &g){
    293 	used[v] = 1;
    294 	for (int u : g[v]){
    295 		if (used[u] == 0)
    296 			ts(u, g);
    297 		else if (used[u] == 1)
    298 			fl = false;
    299 		if (!fl) return;
    300 	}
    301 	ord.push_back(v);
    302 	used[v] = 2;
    303 }
    304 
    305 bool topsort(const vector<vector<int>> &g){
    306 	int n = g.size();
    307 	used.assign(n, 0);
    308 	ord.clear();
    309 	fl = true;
    310 	forn(i, n) if (!used[i]){
    311 		ts(i, g);
    312 		if (!fl) return false;
    313 	}
    314 	reverse(ord.begin(), ord.end());
    315 	return true;
    316 }
    317 
    318 vector<int> pos;
    319 
    320 bool dfs(int v){
    321 	for (int u : g[v]){
    322 		if (pos[u] < pos[v])
    323 			return false;
    324 		if (!dfs(u))
    325 			return false;
    326 	}
    327 	return true;
    328 }
    329 
    330 int main() {
    331 	int n, m;
    332 	scanf("%d%d", &n, &m);
    333 	g.resize(n);
    334 	h.resize(n);
    335 	ng.resize(n);
    336 	int rt = -1;
    337 	forn(i, n){
    338 		int p;
    339 		scanf("%d", &p);
    340 		--p;
    341 		if (p == -1)
    342 			rt = i;
    343 		else
    344 			g[p].push_back(i);
    345 	}
    346 	rk.assign(n, 1);
    347 	p.resize(n);
    348 	iota(p.begin(), p.end(), 0);
    349 	forn(i, m){
    350 		int v, u;
    351 		scanf("%d%d", &v, &u);
    352 		--v, --u;
    353 		h[v].push_back(u);
    354 		unite(v, u);
    355 	}
    356 	if (!topsort(h)){
    357 		puts("0");
    358 		return 0;
    359 	}
    360 	auto ord1 = ord;
    361 	vector<int> pos1(n);
    362 	forn(i, n) pos1[ord1[i]] = i;
    363 	forn(v, n) for (int u : g[v]) if (getp(v) != getp(u))
    364 		ng[getp(v)].push_back(getp(u));
    365 	if (!topsort(ng)){
    366 		puts("0");
    367 		return 0;
    368 	}
    369 	comp.resize(n);
    370 	forn(i, n) comp[getp(i)].push_back(i);
    371 	vector<int> fin;
    372 	for (int it : ord){
    373 		sort(comp[it].begin(), comp[it].end(), [&](int v, int u){ return pos1[v] < pos1[u]; });
    374 		for (int v : comp[it])
    375 			fin.push_back(v);
    376 	}
    377 	pos.resize(n);
    378 	forn(i, n) pos[fin[i]] = i;
    379 	if (!dfs(rt)){
    380 		puts("0");
    381 		return 0;
    382 	}
    383 	for (int v : fin)
    384 		printf("%d ", v + 1);
    385 	puts("");
    386 }
    387 ```
    388 
    389 [1463F - Max Correct Set](/contest/1463/problem/F "Educational Codeforces Round 100 (Rated for Div. 2)")
    390 
    391 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    392 
    393 **Tutorial**
    394 
    395 Tutorial is loading...
    396 
    397 **Solution (Ne0n25)**
    398 
    399 ```
    400 #include <bits/stdc++.h>
    401 
    402 using namespace std;
    403 
    404 const int INF = 1e9;
    405 const int N = 22;
    406 
    407 int dp[2][1 << N];
    408 int val[2 * N];
    409 
    410 int main() {
    411 	int n, x, y;
    412 	scanf("%d%d%d", &n, &x, &y);
    413 	
    414 	int k = x + y;
    415 	int m = max(x, y);
    416 	int FULL = (1 << m) - 1;
    417 	
    418 	for (int i = 0; i < k; ++i)
    419 		val[i] = n / k + (i < n % k);
    420 	for (int mask = 0; mask < (1 << m); ++mask)
    421 		dp[0][mask] = -INF;
    422 	dp[0][0] = 0;
    423 	
    424 	for (int i = 0; i < k; ++i) {
    425 		for (int mask = 0; mask < (1 << m); ++mask)
    426 			dp[1][mask] = -INF;
    427 		for (int mask = 0; mask < (1 << m); ++mask) {
    428 			if (dp[0][mask] == -INF)
    429 				continue;
    430 			int nmask = (mask << 1) & FULL;
    431 			dp[1][nmask] = max(dp[1][nmask], dp[0][mask]);
    432 			if (((mask >> (x - 1)) & 1) | ((mask >> (y - 1)) & 1))
    433 				continue;
    434 			nmask |= 1;
    435 			dp[1][nmask] = max(dp[1][nmask], dp[0][mask] + val[i]);
    436 		}
    437 		swap(dp[0], dp[1]);
    438 	}
    439 	
    440 	int ans = 0;
    441 	for (int mask = 0; mask < (1 << m); ++mask) 
    442 		ans = max(ans, dp[0][mask]);
    443 	printf("%d\n", ans);
    444 }
    445 ```