codeforces-scrape

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

1195.md (13870B)


      1 Source: https://codeforces.com/blog/entry/68471
      2 
      3 [1195A - Drinks Choosing](/contest/1195/problem/A "Codeforces Round 574 (Div. 2)")
      4 
      5 Idea: [budalnik](/profile/budalnik "International Master budalnik")
      6 
      7 Preparation: [budalnik](/profile/budalnik "International Master budalnik")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 // Created by Nikolay Budin
     17 
     18 #ifdef LOCAL
     19 #  define _GLIBCXX_DEBUG
     20 #else
     21 #  define cerr __get_ce
     22 #endif
     23 #include <bits/stdc++.h>
     24 #define ff first
     25 #define ss second
     26 #define szof(x) ((int)x.size())
     27 
     28 using namespace std;
     29 typedef long long ll;
     30 typedef long double ld;
     31 typedef pair<int, int> pii;
     32 typedef unsigned long long ull;
     33 int const INF = (int)1e9 + 1e3;
     34 ll const INFL = (ll)1e18 + 1e6;
     35 #ifdef LOCAL
     36 	mt19937 tw(9450189);
     37 #else
     38 	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
     39 #endif
     40 uniform_int_distribution<ll> ll_distr;
     41 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }
     42 
     43 void solve() {
     44 	int n, k;
     45 	cin >> n >> k;
     46 	map<int, int> have;
     47 	for (int i = 0; i < n; ++i) {
     48 		int num;
     49 		cin >> num;
     50 		have[num]++;
     51 	}
     52 	int cnt = 0;
     53 	int ans = 0;
     54 	for (pii p : have) {
     55 		cnt += p.ss % 2;
     56 		ans += p.ss / 2 * 2;
     57 	}
     58 	ans += (cnt + 1) / 2;
     59 	cout << ans << "\n";
     60 }
     61 
     62 int main() {
     63 #ifdef LOCAL
     64 	auto start_time = clock();
     65 	cerr << setprecision(3) << fixed;
     66 #endif
     67 	cout << setprecision(15) << fixed;
     68 	ios::sync_with_stdio(false);
     69 	cin.tie(nullptr);
     70 
     71 	int test_count = 1;
     72 	// cin >> test_count;
     73 	for (int test = 1; test <= test_count; ++test) {
     74 		solve();
     75 	}
     76 	
     77 #ifdef LOCAL
     78 	auto end_time = clock();
     79 	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
     80 #endif
     81 }
     82 ```
     83 
     84 [1195B - Sport Mafia](/contest/1195/problem/B "Codeforces Round 574 (Div. 2)")
     85 
     86 Idea: ?
     87 
     88 Preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [cdkrot](/profile/cdkrot "Grandmaster cdkrot")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution (binary search)**
     95 
     96 ```
     97 #include <iostream>
     98 #include <cmath>
     99 
    100 int main() {
    101     long long n, k;
    102     std::cin >> n >> k;
    103     long long l = -1, r = n + 1;
    104     while (r - l > 1) {
    105         long long m = (l + r) / 2;
    106         if ((n - m) * (n - m + 1) / 2 - m > k)
    107             l = m;
    108         else
    109             r = m;
    110     }
    111     std::cout << r;
    112     return 0;
    113 }
    114 ```
    115 
    116 **Solution (formula)**
    117 
    118 ```
    119 #include <iostream>
    120 #include <cmath>
    121 
    122 int main() {
    123     long long n, k;
    124     std::cin >> n >> k;
    125     std::cout << static_cast<long long>(round(n + 1.5 - sqrt(2 * (n + k) + 2.75)));
    126     return 0;
    127 }
    128 ```
    129 
    130 [1195C - Basketball Exercise](/contest/1195/problem/C "Codeforces Round 574 (Div. 2)")
    131 
    132 Idea: [meshanya](/profile/meshanya "Grandmaster meshanya")
    133 
    134 Preparation: [tsarn](/profile/tsarn "Master tsarn")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution**
    141 
    142 ```
    143 // Created by Nikolay Budin
    144 
    145 #ifdef LOCAL
    146 #  define _GLIBCXX_DEBUG
    147 #else
    148 #  define cerr __get_ce
    149 #endif
    150 #include <bits/stdc++.h>
    151 #define ff first
    152 #define ss second
    153 #define szof(x) ((int)x.size())
    154 
    155 using namespace std;
    156 typedef long long ll;
    157 typedef long double ld;
    158 typedef pair<int, int> pii;
    159 typedef unsigned long long ull;
    160 typedef pair<ll, ll> pll;
    161 int const INF = (int)1e9 + 1e3;
    162 ll const INFL = (ll)1e18 + 1e6;
    163 #ifdef LOCAL
    164 	mt19937 tw(9450189);
    165 #else
    166 	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
    167 #endif
    168 uniform_int_distribution<ll> ll_distr;
    169 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }
    170 
    171 void solve() {
    172 	int n;
    173 	cin >> n;
    174 	vector<vector<int>> inp;
    175 	for (int i = 0; i < 2; ++i) {
    176 		inp.push_back(vector<int>());
    177 		for (int j = 0; j < n; ++j) {
    178 			int num;
    179 			cin >> num;
    180 			inp[i].push_back(num);
    181 		}
    182 	}
    183 
    184 	pll d = {0, 0};
    185 
    186 	for (int i = 0; i < n; ++i) {
    187 		pll next = {max(d.ff, d.ss + inp[0][i]), max(d.ss, d.ff + inp[1][i])};
    188 		d = next;
    189 	}
    190 
    191 	cout << max(d.ff, d.ss) << "\n";
    192 }
    193 
    194 int main() {
    195 #ifdef LOCAL
    196 	auto start_time = clock();
    197 	cerr << setprecision(3) << fixed;
    198 #endif
    199 	cout << setprecision(15) << fixed;
    200 	ios::sync_with_stdio(false);
    201 	cin.tie(nullptr);
    202 
    203 	int test_count = 1;
    204 	// cin >> test_count;
    205 	for (int test = 1; test <= test_count; ++test) {
    206 		solve();
    207 	}
    208 	
    209 #ifdef LOCAL
    210 	auto end_time = clock();
    211 	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
    212 #endif
    213 }
    214 ```
    215 
    216 [1195D1 - Submarine in the Rybinsk Sea (easy edition)](/contest/1195/problem/D1 "Codeforces Round 574 (Div. 2)")
    217 
    218 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    219 
    220 Preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution**
    227 
    228 ```
    229 #include <bits/stdc++.h>
    230 
    231 using namespace std;
    232 
    233 const int MOD = 998244353;
    234 
    235 int add(int a, int b) {
    236 	a += b;
    237 	if (a >= MOD) a -= MOD;
    238 	if (a < 0) a += MOD;
    239 	return a;
    240 }
    241 
    242 int mul(int a, int b) {
    243 	return a * 1ll * b % MOD;
    244 }
    245 
    246 int len;
    247 vector<int> pw10;
    248 
    249 int f(int a) {
    250 	int pos = 0;
    251 	int res = 0;
    252 	while (a > 0) {
    253 		int cur = a % 10;
    254 		a /= 10;
    255 		res = add(res, mul(cur, pw10[2 * pos]));
    256 		res = add(res, mul(cur, pw10[2 * pos + 1]));
    257 		++pos;
    258 	}
    259 	return res;
    260 }
    261 
    262 int main() {
    263 #ifdef _DEBUG
    264 	freopen("input.txt", "r", stdin);
    265 //	freopen("output.txt", "w", stdout);
    266 #endif
    267 
    268 	pw10 = vector<int>(30);
    269 	pw10[0] = 1;
    270 	for (int i = 1; i < 30; ++i) {
    271 		pw10[i] = mul(pw10[i - 1], 10);
    272 	}
    273 	
    274 	int n;
    275 	cin >> n;
    276 	int ans = 0;
    277 	for (int i = 0; i < n; ++i) {
    278 		int a;
    279 		cin >> a;
    280 		len = to_string(a).size();
    281 		ans = add(ans, mul(n, f(a)));
    282 	}
    283 	
    284 	cout << ans << endl;
    285 	
    286 	return 0;
    287 }
    288 ```
    289 
    290 [1195D2 - Submarine in the Rybinsk Sea (hard edition)](/contest/1195/problem/D2 "Codeforces Round 574 (Div. 2)")
    291 
    292 Idea: [meshanya](/profile/meshanya "Grandmaster meshanya")
    293 
    294 Preparation: [sava-cska](/profile/sava-cska "Grandmaster sava-cska")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Solution**
    301 
    302 ```
    303 // Created by Nikolay Budin
    304 
    305 #ifdef LOCAL
    306 #  define _GLIBCXX_DEBUG
    307 #else
    308 #  define cerr __get_ce
    309 #endif
    310 #include <bits/stdc++.h>
    311 #define ff first
    312 #define ss second
    313 #define szof(x) ((int)x.size())
    314 
    315 using namespace std;
    316 typedef long long ll;
    317 typedef long double ld;
    318 typedef pair<int, int> pii;
    319 typedef unsigned long long ull;
    320 int const INF = (int)1e9 + 1e3;
    321 ll const INFL = (ll)1e18 + 1e6;
    322 #ifdef LOCAL
    323 	mt19937 tw(9450189);
    324 #else
    325 	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
    326 #endif
    327 uniform_int_distribution<ll> ll_distr;
    328 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }
    329 
    330 const int MOD = 998244353;
    331 
    332 void add(int& a, int b) {
    333 	a += b;
    334 	if (a >= MOD) {
    335 		a -= MOD;
    336 	}
    337 }
    338 
    339 int sum(int a, int b) {
    340 	add(a, b);
    341 	return a;
    342 }
    343 
    344 int mult(int a, int b) {
    345 	return (ll) a * b % MOD;
    346 }
    347 
    348 int f(vector<int> const& a, int l) {
    349 	int res = 0;
    350 	int p = 1;
    351 	for (int i = 0; i < max(szof(a), l); ++i) {
    352 		if (i < l) {
    353 			p = mult(p, 10);
    354 		}
    355 		if (i < szof(a)) {
    356 			add(res, mult(a[i], p));
    357 			p = mult(p, 10);
    358 		}
    359 	}
    360 	return res;
    361 }
    362 
    363 int f(int l, vector<int> const& b) {
    364 	int res = 0;
    365 	int p = 1;
    366 	for (int i = 0; i < max(l, szof(b)); ++i) {
    367 		if (i < szof(b)) {
    368 			add(res, mult(b[i], p));
    369 			p = mult(p, 10);
    370 		}
    371 		if (i < l) {
    372 			p = mult(p, 10);
    373 		}
    374 	}
    375 	return res;
    376 }
    377 
    378 void solve() {
    379 	int n;
    380 	cin >> n;
    381 	vector<int> arr;
    382 	const int MAXL = 11;
    383 	vector<int> of_len(MAXL);
    384 	for (int i = 0; i < n; ++i) {
    385 		int num;
    386 		cin >> num;
    387 		arr.push_back(num);
    388 		int l = 0;
    389 		int tmp = num;
    390 		while (tmp) {
    391 			++l;
    392 			tmp /= 10;
    393 		}
    394 		of_len[l]++;
    395 	}
    396 	int ans = 0;
    397 	for (int i = 0; i < n; ++i) {
    398 		vector<int> digits;
    399 		int tmp = arr[i];
    400 		while (tmp) {
    401 			digits.push_back(tmp % 10);
    402 			tmp /= 10;
    403 		}
    404 		for (int l = 1; l < MAXL; ++l) {
    405 			int sum = f(digits, l);
    406 			add(ans, mult(sum, of_len[l]));
    407 
    408 			sum = f(l, digits);
    409 			add(ans, mult(sum, of_len[l]));
    410 		}
    411 	}
    412 
    413 	cout << ans << "\n";
    414 }
    415 
    416 int main() {
    417 #ifdef LOCAL
    418 	auto start_time = clock();
    419 	cerr << setprecision(3) << fixed;
    420 #endif
    421 	cout << setprecision(15) << fixed;
    422 	ios::sync_with_stdio(false);
    423 	cin.tie(nullptr);
    424 
    425 	int test_count = 1;
    426 	// cin >> test_count;
    427 	for (int test = 1; test <= test_count; ++test) {
    428 		solve();
    429 	}
    430 	
    431 #ifdef LOCAL
    432 	auto end_time = clock();
    433 	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
    434 #endif
    435 }
    436 ```
    437 
    438 [1195E - OpenStreetMap](/contest/1195/problem/E "Codeforces Round 574 (Div. 2)")
    439 
    440 Idea: [budalnik](/profile/budalnik "International Master budalnik")
    441 
    442 Preparation: [ima_ima_go](/profile/ima_ima_go "Specialist ima_ima_go")
    443 
    444 **Tutorial**
    445 
    446 Tutorial is loading...
    447 
    448 **Solution**
    449 
    450 ```
    451 #include <bits/stdc++.h>
    452 
    453 using namespace std;
    454 
    455 long long n, m, a, b, g, x, y, z;
    456 vector<deque<long long> > deq;
    457 vector<vector<long long> > mi;
    458 vector<int> power;
    459 const long long MAX_V = 1000000000000000ll;
    460 
    461 void ins(deque<long long>& de, long long val) {
    462     while(!de.empty() && de.back() > val) {
    463         de.pop_back();
    464     }
    465     de.push_back(val);
    466 }
    467 
    468 void del(deque<long long>& de, long long val) {
    469     if (!de.empty() && de.front() == val) {
    470         de.pop_front();
    471     }
    472 }
    473 
    474 int main() {
    475     ios::sync_with_stdio(0);
    476     cin.tie(0);
    477     cin >> n >> m;
    478     cin >> a >> b;
    479     cin >> g >> x >> y >> z;
    480     mi.resize(n);
    481     deq.resize(m);
    482     for (int i = 0; i < n; i++) {
    483         mi[i].resize(m);
    484         for (int j = 0; j < m; j++) {
    485             mi[i][j] = g;
    486             g = (g * x + y) % z;
    487         }
    488     }
    489     for (int i = 0; i < m; i++) {
    490         for (int j = 0; j < a; j++) {
    491             ins(deq[i], mi[j][i]);
    492         }
    493     }
    494     deque<long long> real_deq;
    495     for (int i = 0; i < b; i++) {
    496         ins(real_deq, deq[i].front());
    497     }
    498     long long ans = 0;
    499     ans += real_deq.front();
    500     for (int i = b; i < m; i++) {
    501         del(real_deq, deq[i - b].front());
    502         ins(real_deq, deq[i].front());
    503         ans += real_deq.front();
    504     }
    505     for (int i = a; i < n; i++) {
    506         for (int j = 0 ; j < m; j++) {
    507             ins(deq[j], mi[i][j]);
    508             del(deq[j], mi[i - a][j]);
    509         }
    510         deque<long long> real_d;
    511         for (int j = 0; j < b; j++) {
    512             ins(real_d, deq[j].front());
    513         }
    514         ans += real_d.front();
    515         for (int j = b; j < m; j++) {
    516             del(real_d, deq[j - b].front());
    517             ins(real_d, deq[j].front());
    518             ans += real_d.front();
    519         }
    520     }
    521     cout << ans << "\n";
    522 }
    523 ```
    524 
    525 [1195F - Geometers Anonymous Club](/contest/1195/problem/F "Codeforces Round 574 (Div. 2)")
    526 
    527 Idea: [craborac](/profile/craborac "International Grandmaster craborac")
    528 
    529 Preparation: [budalnik](/profile/budalnik "International Master budalnik")
    530 
    531 **Tutorial**
    532 
    533 Tutorial is loading...
    534 
    535 **Solution**
    536 
    537 ```
    538 // Created by Nikolay Budin
    539 
    540 #ifdef LOCAL
    541 #  define _GLIBCXX_DEBUG
    542 #else
    543 #  define cerr __get_ce
    544 #endif
    545 #include <bits/stdc++.h>
    546 #define ff first
    547 #define ss second
    548 #define szof(x) ((int)x.size())
    549 
    550 using namespace std;
    551 typedef long long ll;
    552 typedef long double ld;
    553 typedef pair<int, int> pii;
    554 typedef unsigned long long ull;
    555 int const INF = (int)1e9 + 1e3;
    556 ll const INFL = (ll)1e18 + 1e6;
    557 #ifdef LOCAL
    558 	mt19937 tw(9450189);
    559 #else
    560 	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
    561 #endif
    562 uniform_int_distribution<ll> ll_distr;
    563 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }
    564 
    565 struct point {
    566 	int x, y;
    567 	point(int _x, int _y) : x(_x), y(_y) {}
    568 
    569 	point operator-(point const& other) const {
    570 		return point(x - other.x, y - other.y);
    571 	}
    572 
    573 	point& operator/=(int num) {
    574 		x /= num;
    575 		y /= num;
    576 		return *this;
    577 	}
    578 
    579 	bool operator<(point const& other) const {
    580 		return x < other.x || (x == other.x && y < other.y);
    581 	}
    582 };
    583 
    584 void solve() {
    585 	int n;
    586 	cin >> n;
    587 	vector<vector<point>> polys;
    588 	vector<point> vecs;
    589 	vector<int> borders;
    590 	borders.push_back(0);
    591 	for (int i = 0; i < n; ++i) {
    592 		int k;
    593 		cin >> k;
    594 		borders.push_back(borders.back() + k);
    595 		polys.push_back({});
    596 		for (int j = 0; j < k; ++j) {
    597 			int x, y;
    598 			cin >> x >> y;
    599 			polys.back().push_back(point(x, y));
    600 		}
    601 
    602 		for (int j = 0; j < k; ++j) {
    603 			int next = (j + 1) % k;
    604 			point v = polys[i][next] - polys[i][j];
    605 			int tmp = __gcd(abs(v.x), abs(v.y));
    606 			v /= tmp;
    607 			vecs.push_back(v);
    608 		}
    609 	}
    610 
    611 	vector<int> arr;
    612 	map<point, int> inds;
    613 	for (auto v : vecs) {
    614 		if (!inds.count(v)) {
    615 			int tmp = szof(inds);
    616 			inds[v] = tmp;
    617 		}
    618 		arr.push_back(inds[v]);
    619 	}
    620 
    621 	vector<int> next(szof(vecs));
    622 	vector<int> last(szof(inds), INF);
    623 	for (int i = szof(vecs) - 1; i >= 0; --i) {
    624 		next[i] = last[arr[i]];
    625 		last[arr[i]] = i;
    626 	}
    627 
    628 	vector<vector<pii>> here(szof(vecs));
    629 	int q;
    630 	cin >> q;
    631 	vector<int> ans(q);
    632 	for (int i = 0; i < q; ++i) {
    633 		int l, r;
    634 		cin >> l >> r;
    635 		--l;
    636 		l = borders[l];
    637 		r = borders[r];
    638 		here[l].push_back({r, i});
    639 	}
    640 
    641 	int bpv = 1;
    642 	while (bpv < szof(vecs)) {
    643 		bpv *= 2;
    644 	}
    645 
    646 	vector<int> segtree(bpv * 2);
    647 
    648 	function<void(int, int)> segtree_set = [&](int pos, int val) {
    649 		pos += bpv;
    650 		segtree[pos] = val;
    651 		pos /= 2;
    652 		while (pos) {
    653 			segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
    654 			pos /= 2;
    655 		}
    656 	};
    657 
    658 	function<int(int, int, int, int, int)> segtree_get = [&](int v, int vl, int vr, int l, int r) {
    659 		if (vr <= l || r <= vl) {
    660 			return 0;
    661 		}
    662 		if (l <= vl && vr <= r) {
    663 			return segtree[v];
    664 		}
    665 		int vm = (vl + vr) / 2;
    666 		return segtree_get(v * 2, vl, vm, l, r) + segtree_get(v * 2 + 1, vm, vr, l, r);
    667 	};
    668 
    669 	for (int i = 0; i < szof(inds); ++i) {
    670 		segtree_set(last[i], 1);
    671 	}
    672 
    673 	for (int i = 0; i < szof(vecs); ++i) {
    674 		for (auto p : here[i]) {
    675 			ans[p.ss] = segtree_get(1, 0, bpv, i, p.ff);
    676 		}
    677 		segtree_set(i, 0);
    678 		if (next[i] != INF) {
    679 			segtree_set(next[i], 1);
    680 		}
    681 	}
    682 
    683 	for (int num : ans) {
    684 		cout << num << "\n";
    685 	}
    686 }
    687 
    688 int main() {
    689 #ifdef LOCAL
    690 	auto start_time = clock();
    691 	cerr << setprecision(3) << fixed;
    692 #endif
    693 	cout << setprecision(15) << fixed;
    694 	ios::sync_with_stdio(false);
    695 	cin.tie(nullptr);
    696 
    697 	int test_count = 1;
    698 	// cin >> test_count;
    699 	for (int test = 1; test <= test_count; ++test) {
    700 		solve();
    701 	}
    702 	
    703 #ifdef LOCAL
    704 	auto end_time = clock();
    705 	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
    706 #endif
    707 }
    708 ```