codeforces-scrape

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

1118.md (9156B)


      1 Source: https://codeforces.com/blog/entry/65396
      2 
      3 [1118A - Water Buying](/contest/1118/problem/A "Codeforces Round 540 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int q;
     25 	cin >> q;
     26 	
     27 	for (int i = 0; i < q; ++i) {
     28 		long long n;
     29 		int a, b;
     30 		cin >> n >> a >> b;
     31 		cout << (n / 2) * min(2 * a, b) + (n % 2) * a << endl;
     32 	}
     33 	
     34 	return 0;
     35 }
     36 ```
     37 
     38 [1118B - Tanya and Candies](/contest/1118/problem/B "Codeforces Round 540 (Div. 3)")
     39 
     40 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int main() {
     54 #ifdef _DEBUG
     55 	freopen("input.txt", "r", stdin);
     56 //	freopen("output.txt", "w", stdout);
     57 #endif
     58 
     59 	int n;
     60 	cin >> n;
     61 	
     62 	vector<int> a(n);
     63 	
     64 	int ePref = 0, oPref = 0, eSuf = 0, oSuf = 0;
     65 	for (int i = 0; i < n; ++i) {
     66 		cin >> a[i];
     67 		if (i & 1) eSuf += a[i];
     68 		else oSuf += a[i];
     69 	}
     70 	
     71 	int ans = 0;
     72 	for (int i = 0; i < n; ++i) {
     73 		if (i & 1) eSuf -= a[i];
     74 		else oSuf -= a[i];
     75 		if (ePref + oSuf == oPref + eSuf) {
     76 			++ans;
     77 		}
     78 		if (i & 1) ePref += a[i];
     79 		else oPref += a[i];
     80 	}
     81 	
     82 	cout << ans << endl;
     83 	
     84 	return 0;
     85 }
     86 ```
     87 
     88 [1118C - Palindromic Matrix](/contest/1118/problem/C "Codeforces Round 540 (Div. 3)")
     89 
     90 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     91 
     92 I should mention [this](//codeforces.com/blog/entry/65383) blog because it is amazing! This is a tutorial of this problem from [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution**
     99 
    100 ```
    101 #include <bits/stdc++.h>
    102 
    103 #define forn(i, n) for (int i = 0; i < int(n); i++)
    104 
    105 using namespace std;
    106 
    107 typedef pair<int, int> pt;
    108 
    109 const int N = 1000 + 7;
    110 
    111 int cnt[N];
    112 int a[20][20];
    113 
    114 int main() {
    115 	int n;
    116 	scanf("%d", &n);
    117 	forn(i, n * n){
    118 		int x;
    119 		scanf("%d", &x);
    120 		++cnt[x];
    121 	}
    122 	
    123 	vector<pair<int, pt>> cells;
    124 	forn(i, (n + 1) / 2) forn(j, (n + 1) / 2){
    125 		if (i != n - i - 1 && j != n - j - 1)
    126 			cells.push_back({4, {i, j}});
    127 		else if ((i != n - i - 1) ^ (j != n - j - 1))
    128 			cells.push_back({2, {i, j}});
    129 		else
    130 			cells.push_back({1, {i, j}});
    131 	}
    132 	
    133 	for (auto cur : {4, 2, 1}){
    134 		int lst = 1;
    135 		for (auto it : cells){
    136 			if (it.first != cur) continue;
    137 			int i = it.second.first;
    138 			int j = it.second.second;
    139 			while (lst < N && cnt[lst] < cur)
    140 				++lst;
    141 			if (lst == N){
    142 				puts("NO");
    143 				return 0;
    144 			}
    145 			a[i][j] = a[n - i - 1][j] = a[i][n - j - 1] = a[n - i - 1][n - j - 1] = lst;
    146 			cnt[lst] -= cur;
    147 		}
    148 	}
    149 	
    150 	puts("YES");
    151 	forn(i, n){
    152 		forn(j, n)
    153 			printf("%d ", a[i][j]);
    154 		puts("");
    155 	}
    156 	return 0;
    157 }
    158 ```
    159 
    160 [1118D1 - Coffee and Coursework (Easy version)](/contest/1118/problem/D1 "Codeforces Round 540 (Div. 3)")
    161 
    162 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    163 
    164 **Tutorial**
    165 
    166 Tutorial is loading...
    167 
    168 **Solution**
    169 
    170 ```
    171 #include <bits/stdc++.h>
    172 
    173 using namespace std;
    174 
    175 int main() {
    176 #ifdef _DEBUG
    177 	freopen("input.txt", "r", stdin);
    178 //	freopen("output.txt", "w", stdout);
    179 #endif
    180 	
    181 	int n, m;
    182 	cin >> n >> m;
    183 	
    184 	vector<int> a(n);
    185 	for (int i = 0; i < n; ++i) {
    186 		cin >> a[i];
    187 	}
    188 	sort(a.rbegin(), a.rend());
    189 	
    190 	for (int i = 1; i <= n; ++i) {
    191 		int sum = 0;
    192 		for (int j = 0; j < n; ++j) {
    193 			sum += max(a[j] - j / i, 0);
    194 		}
    195 		if (sum >= m) {
    196 			cout << i << endl;
    197 			return 0;
    198 		}
    199 	}
    200 	
    201 	cout << -1 << endl;
    202 	
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1118D2 - Coffee and Coursework (Hard Version)](/contest/1118/problem/D2 "Codeforces Round 540 (Div. 3)")
    208 
    209 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 int n, m;
    223 vector<int> a;
    224 
    225 bool can(int i) {
    226 	long long sum = 0; // there can be a bug
    227 	for (int j = 0; j < n; ++j) {
    228 		sum += max(a[j] - j / i, 0);
    229 	}
    230 	return sum >= m;
    231 }
    232 
    233 int main() {
    234 #ifdef _DEBUG
    235 	freopen("input.txt", "r", stdin);
    236 //	freopen("output.txt", "w", stdout);
    237 #endif
    238 	
    239 	cin >> n >> m;
    240 	
    241 	a = vector<int>(n);
    242 	for (int i = 0; i < n; ++i) {
    243 		cin >> a[i];
    244 	}
    245 	sort(a.rbegin(), a.rend());
    246 	
    247 	int l = 1, r = n;
    248 	while (r - l > 1) {
    249 		int mid = (l + r) >> 1;
    250 		if (can(mid)) r = mid;
    251 		else l = mid;
    252 	}
    253 	
    254 	if (can(l)) cout << l << endl;
    255 	else if (can(r)) cout << r << endl;
    256 	else cout << -1 << endl;
    257 	
    258 	return 0;
    259 }
    260 ```
    261 
    262 [1118E - Yet Another Ball Problem](/contest/1118/problem/E "Codeforces Round 540 (Div. 3)")
    263 
    264 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    265 
    266 **Tutorial**
    267 
    268 Tutorial is loading...
    269 
    270 **Solution**
    271 
    272 ```
    273 #include <bits/stdc++.h>
    274 
    275 using namespace std;
    276 
    277 int main() {
    278 #ifdef _DEBUG
    279 	freopen("input.txt", "r", stdin);
    280 //	freopen("output.txt", "w", stdout);
    281 #endif
    282 	
    283 	int n, k;
    284 	cin >> n >> k;
    285 	
    286 	if (n > k * 1ll * (k - 1)) {
    287 		cout << "NO" << endl;
    288 	} else {
    289 		cout << "YES" << endl;
    290 		int cur = 0;
    291 		for (int i = 0; i < n; ++i) {
    292 			cur += (i % k == 0);
    293 			cout << i % k + 1 << " " << (cur + i % k) % k + 1 << endl;
    294 		}
    295 	}
    296 	
    297 	return 0;
    298 }
    299 ```
    300 
    301 [1118F1 - Tree Cutting (Easy Version)](/contest/1118/problem/F1 "Codeforces Round 540 (Div. 3)")
    302 
    303 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    304 
    305 **Tutorial**
    306 
    307 Tutorial is loading...
    308 
    309 **Solution**
    310 
    311 ```
    312 #include <bits/stdc++.h>
    313 
    314 #define forn(i, n) for (int i = 0; i < int(n); i++)
    315 
    316 using namespace std;
    317 
    318 const int N = 300 * 1000 + 13;
    319 
    320 int n;
    321 int a[N];
    322 vector<int> g[N];
    323 int red, blue;
    324 int ans;
    325 
    326 pair<int, int> dfs(int v, int p = -1){
    327 	int r = (a[v] == 1), b = (a[v] == 2);
    328 	for (auto u : g[v]) if (u != p){
    329 		auto tmp = dfs(u, v);
    330 		ans += (tmp.first == red && tmp.second == 0);
    331 		ans += (tmp.first == 0 && tmp.second == blue);
    332 		r += tmp.first;
    333 		b += tmp.second;
    334 	}
    335 	return make_pair(r, b);
    336 }
    337 
    338 int main() {
    339 	int n;
    340 	scanf("%d", &n);
    341 	
    342 	forn(i, n){
    343 		scanf("%d", &a[i]);
    344 		red += (a[i] == 1);
    345 		blue += (a[i] == 2);
    346 	}
    347 	
    348 	forn(i, n - 1){
    349 		int v, u;
    350 		scanf("%d%d", &v, &u);
    351 		--v, --u;
    352 		g[v].push_back(u);
    353 		g[u].push_back(v);
    354 	}
    355 	
    356 	ans = 0;
    357 	dfs(0);
    358 	printf("%d\n", ans);
    359 	return 0;
    360 }
    361 ```
    362 
    363 [1118F2 - Tree Cutting (Hard Version)](/contest/1118/problem/F2 "Codeforces Round 540 (Div. 3)")
    364 
    365 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    366 
    367 **Tutorial**
    368 
    369 Tutorial is loading...
    370 
    371 **Solution**
    372 
    373 ```
    374 #include <bits/stdc++.h>
    375 
    376 #define forn(i, n) for (int i = 0; i < int(n); i++)
    377 
    378 using namespace std;
    379 
    380 const int N = 300 * 1000 + 13;
    381 const int LOGN = 19;
    382 const int MOD = 998244353;
    383 
    384 int add(int a, int b){
    385 	a += b;
    386 	if (a >= MOD)
    387 		a -= MOD;
    388 	if (a < 0)
    389 		a += MOD;
    390 	return a;
    391 }
    392 
    393 int mul(int a, int b){
    394 	return a * 1ll * b % MOD;
    395 }
    396 
    397 int a[N];
    398 vector<int> g[N];
    399 int up[N][LOGN];
    400 int d[N];
    401 
    402 void init(int v, int p = -1){
    403 	for (auto u : g[v]) if (u != p){
    404 		up[u][0] = v;
    405 		for (int i = 1; i < LOGN; ++i)
    406 			up[u][i] = up[up[u][i - 1]][i - 1];
    407 		d[u] = d[v] + 1;
    408 		init(u, v);
    409 	}
    410 }
    411 
    412 int lca(int v, int u){
    413 	if (d[v] < d[u]) swap(v, u);
    414 	for (int i = LOGN - 1; i >= 0; --i)
    415 		if (d[up[v][i]] >= d[u])
    416 			v = up[v][i];
    417 	if (v == u) return v;
    418 	for (int i = LOGN - 1; i >= 0; --i)
    419 		if (up[v][i] != up[u][i]){
    420 			v = up[v][i];
    421 			u = up[u][i];
    422 		}
    423 	return up[v][0];
    424 }
    425 
    426 int l[N];
    427 int dp[N][2];
    428 
    429 int dfs(int v, int p = -1){
    430 	vector<pair<int, int>> cur;
    431 	for (auto u : g[v]) if (u != p){
    432 		int c = dfs(u, v);
    433 		if (c != 0)
    434 			cur.push_back(make_pair(c, u));
    435 	}
    436 	
    437 	vector<int> vals;
    438 	forn(i, cur.size()) if (cur[i].first > 0)
    439 		vals.push_back(cur[i].first);
    440 	
    441 	sort(vals.begin(), vals.end());
    442 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    443 	
    444 	if (int(vals.size()) > 1){
    445 		puts("0");
    446 		exit(0);
    447 	}
    448 	
    449 	if (a[v] != 0 && !vals.empty() && vals[0] != a[v]){
    450 		puts("0");
    451 		exit(0);
    452 	}
    453 	
    454 	if (a[v] == 0 && cur.empty())
    455 		return 0;
    456 	
    457 	if (a[v] == 0 && vals.empty()){		
    458 		vector<int> pr(1, 1), su(1, 1);
    459 		forn(i, cur.size())
    460 			pr.push_back(mul(pr.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
    461 		for (int i = int(cur.size()) - 1; i >= 0; --i)
    462 			su.push_back(mul(su.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
    463 		reverse(su.begin(), su.end());
    464 		dp[v][1] = 0;
    465 		forn(i, cur.size())
    466 			dp[v][1] = add(dp[v][1], mul(mul(pr[i], su[i + 1]), dp[cur[i].second][1]));
    467 		dp[v][0] = add(dp[v][0], pr[cur.size()]);
    468 		return -1;
    469 	}
    470 	
    471 	dp[v][1] = 1;
    472 	for (auto it : cur){
    473 		if (it.first == -1)
    474 			dp[v][1] = mul(dp[v][1], add(dp[it.second][0], dp[it.second][1]));	
    475 		else
    476 			dp[v][1] = mul(dp[v][1], dp[it.second][1]);
    477 	}
    478 	
    479 	if (a[v] == 0)
    480 		return vals[0];
    481 	
    482 	return (l[a[v]] == v ? -1 : a[v]);
    483 }
    484 
    485 int main() {
    486 	int n, k;
    487 	scanf("%d%d", &n, &k);
    488 	
    489 	forn(i, n)
    490 		scanf("%d", &a[i]);
    491 	
    492 	forn(i, n - 1){
    493 		int v, u;
    494 		scanf("%d%d", &v, &u);
    495 		--v, --u;
    496 		g[v].push_back(u);
    497 		g[u].push_back(v);
    498 	}
    499 	
    500 	init(0);
    501 	
    502 	memset(l, -1, sizeof(l));
    503 	forn(i, n) if (a[i] != 0)
    504 		l[a[i]] = (l[a[i]] == -1 ? i : lca(l[a[i]], i));
    505 	
    506 	for (int i = 1; i <= k; ++i){
    507 		if (a[l[i]] != 0 && a[l[i]] != i){
    508 			puts("0");
    509 			exit(0);
    510 		}
    511 		a[l[i]] = i;
    512 	}
    513 	
    514 	dfs(0);
    515 	
    516 	printf("%d\n", dp[0][1]);
    517 	return 0;
    518 }
    519 ```