codeforces-scrape

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

1216.md (10278B)


      1 Source: https://codeforces.com/blog/entry/69954
      2 
      3 All problems except the problem F are invented by [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm"). The problem F idea belongs to [BledDest](/profile/BledDest "International Grandmaster BledDest").
      4 
      5 [1216A - Prefixes](/contest/1216/problem/A "Codeforces Round 587 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 n, s = int(input()), list(input())
     15 ans = 0
     16 for i in range(0, n, 2):
     17 	if (s[i] == s[i + 1]):
     18 		s[i] = chr(1 - ord(s[i]) + 2 * ord('a'))
     19 		ans += 1
     20 print(ans)
     21 print(''.join(s))
     22 ```
     23 
     24 [1216B - Shooting](/contest/1216/problem/B "Codeforces Round 587 (Div. 3)")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution**
     31 
     32 ```
     33 n, a = int(input()), list(map(int, input().split()))
     34 res = []
     35 ans = 0
     36 for i in range(n):
     37 	pos = -1
     38 	for j in range(n):
     39 		if (pos == -1 or a[j] > a[pos]): pos = j
     40 	res.append(pos + 1)
     41 	ans += i * a[pos] + 1
     42 	a[pos] = 0
     43 print(ans)
     44 print(' '.join([str(x) for x in res]))
     45 ```
     46 
     47 [1216C - White Sheet](/contest/1216/problem/C "Codeforces Round 587 (Div. 3)")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution 1**
     54 
     55 ```
     56 #include <iostream>
     57 #include <sstream>
     58 #include <cstdio>
     59 #include <vector>
     60 #include <cmath>
     61 #include <queue>
     62 #include <string>
     63 #include <cstring>
     64 #include <cassert>
     65 #include <iomanip>
     66 #include <algorithm>
     67 #include <set>
     68 #include <map>
     69 #include <ctime>
     70 #include <cmath>
     71 
     72 #define forn(i, n) for(int i=0;i<n;++i)
     73 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
     74 #define sz(v) int(v.size())
     75 #define all(v) v.begin(), v.end()
     76 #define pb push_back
     77 #define mp make_pair
     78 #define x first
     79 #define y1 ________y1
     80 #define y second
     81 #define ft first
     82 #define sc second
     83 #define pt pair<int, int>
     84 
     85 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
     86 template<typename X> inline X sqr(const X& a) { return a * a; }
     87 
     88 typedef long long li;
     89 typedef long double ld;
     90 
     91 using namespace std;
     92 
     93 const int INF = 1000 * 1000 * 1000;
     94 const ld EPS = 1e-9;
     95 const ld PI = acos(-1.0);
     96 
     97 int x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6;
     98 
     99 inline void read() {	
    100 	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 >> x5 >> y5 >> x6 >> y6;
    101     x1 *= 2, y1 *= 2;
    102     x2 *= 2, y2 *= 2;
    103     x3 *= 2, y3 *= 2;
    104     x4 *= 2, y4 *= 2;
    105     x5 *= 2, y5 *= 2;
    106     x6 *= 2, y6 *= 2;
    107 }
    108 
    109 inline bool ok(int x, int y, int x1, int y1, int x2, int y2) {
    110 	return x < x1 || x2 < x || y < y1 || y2 < y;
    111 }
    112 
    113 inline void solve() {
    114 	for (int x = x1; x <= x2; x++) {
    115 		if (ok(x, y1, x3, y3, x4, y4) && ok(x, y1, x5, y5, x6, y6)) {
    116 			cout << "YES" << endl;
    117 			return;
    118 		}
    119 		if (ok(x, y2, x3, y3, x4, y4) && ok(x, y2, x5, y5, x6, y6)) {
    120 			cout << "YES" << endl;
    121 			return;
    122 		}
    123 	}
    124 	for (int y = y1; y <= y2; y++) {
    125 		if (ok(x1, y, x3, y3, x4, y4) && ok(x1, y, x5, y5, x6, y6)) {
    126 			cout << "YES" << endl;
    127 			return;
    128 		}
    129 		if (ok(x2, y, x3, y3, x4, y4) && ok(x2, y, x5, y5, x6, y6)) {
    130 			cout << "YES" << endl;
    131 			return;
    132 		}	
    133 	}
    134 	cout << "NO" << endl;
    135 }
    136 
    137 int main () {
    138 #ifdef fcspartakm
    139     freopen("input.txt", "r", stdin);
    140     //freopen("output.txt", "w", stdout);
    141 #endif
    142     srand(time(NULL));
    143     cerr << setprecision(10) << fixed;
    144     
    145     read();
    146     solve();
    147  
    148     //cerr << "TIME: " << clock() << endl;
    149 }
    150 ```
    151 
    152 **Solution 2**
    153 
    154 ```
    155 #define _CRT_SECURE_NO_WARNINGS
    156 
    157 #include <iostream>
    158 #include <vector>
    159 #include <algorithm>
    160 #include <cstdio>
    161 #include <random>
    162 #include <ctime>
    163 #include <string>
    164 #include <iomanip>
    165 #include <set>
    166 #include <map>
    167 #include <queue>
    168 #include <stack>
    169 
    170 using namespace std;
    171 
    172 typedef long long li;
    173 typedef unsigned long long uli;
    174 typedef pair<int, int> pii;
    175 typedef long double ld;
    176 
    177 #define all(a) a.begin(), a.end()
    178 #define rall(a) a.rbegin(), a.rend()
    179 #define pb push_back
    180 #define forn(i, n) for(int i = 0; i < int(n); ++i)
    181 #define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
    182 #define forb(i, n) for(int i = int(n) - 1; i >= 0; --i)
    183 #define vi vector<int>
    184 #define x first
    185 #define y second
    186 
    187 const int INF = 2e9;
    188 const li INF64 = 1e18;
    189 const int M = 2 * 1000 * 1000;
    190 const int N = 300 * 1000 + 100;
    191 const int MOD = 1e9 + 7;
    192 const double EPS = 1e-9;
    193 const double PI = 3.14159265359;
    194 
    195 pair<pii, pii> intersect(pii a, pii b, pii c, pii d) {
    196 	int lf, rg, up, dn;
    197 	lf = max(min(a.x, b.x), min(c.x, d.x));
    198 	rg = min(max(a.x, b.x), max(c.x, d.x));
    199 	up = min(max(a.y, b.y), max(c.y, d.y));
    200 	dn = max(min(a.y, b.y), min(c.y, d.y));
    201 
    202 	if (rg <= lf || up <= dn) return { {0, 0}, {0, 0} };
    203 
    204 	return { { lf, dn }, { rg, up } };
    205 }
    206 
    207 li square(pii a, pii b) {
    208 	return 1ll * abs(a.x - b.x) * abs(a.y - b.y);
    209 }
    210 
    211 int main() {
    212 #ifdef _DEBUG
    213 	freopen("input.txt", "r", stdin);
    214 	freopen("output.txt", "w", stdout);
    215 #endif
    216 	ios_base::sync_with_stdio(0);
    217 	cin.tie(0);
    218 
    219 	vector<pii> p(6);
    220 
    221 	forn(i, 6)
    222 		cin >> p[i].x >> p[i].y;
    223 
    224 	pair<pii, pii> wb1 = intersect(p[0], p[1], p[2], p[3]);
    225 	pair<pii, pii> wb2 = intersect(p[0], p[1], p[4], p[5]);
    226 	pair<pii, pii> inter = intersect(wb1.x, wb1.y, wb2.x, wb2.y);
    227 
    228 	li swhite = square(p[0], p[1]);
    229 	li swb1 = square(wb1.x, wb1.y);
    230 	li swb2 = square(wb2.x, wb2.y);
    231 	li sinter = square(inter.x, inter.y);
    232 
    233 	if (swhite > swb1 + swb2 - sinter) cout << "YES\n";
    234 	else cout << "NO\n";
    235 }
    236 ```
    237 
    238 [1216D - Swords](/contest/1216/problem/D "Codeforces Round 587 (Div. 3)")
    239 
    240 **Tutorial**
    241 
    242 Tutorial is loading...
    243 
    244 **Solution**
    245 
    246 ```
    247 #include <iostream>
    248 #include <sstream>
    249 #include <cstdio>
    250 #include <vector>
    251 #include <cmath>
    252 #include <queue>
    253 #include <string>
    254 #include <cstring>
    255 #include <cassert>
    256 #include <iomanip>
    257 #include <algorithm>
    258 #include <set>
    259 #include <map>
    260 #include <ctime>
    261 #include <cmath>
    262 
    263 #define forn(i, n) for(int i=0;i<n;++i)
    264 #define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
    265 #define sz(v) int(v.size())
    266 #define all(v) v.begin(), v.end()
    267 #define pb push_back
    268 #define mp make_pair
    269 #define x first
    270 #define y1 ________y1
    271 #define y second
    272 #define ft first
    273 #define sc second
    274 #define pt pair<int, int>
    275 
    276 template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
    277 template<typename X> inline X sqr(const X& a) { return a * a; }
    278 
    279 typedef long long li;
    280 typedef long double ld;
    281 
    282 using namespace std;
    283 
    284 const int INF = 1000 * 1000 * 1000;
    285 const ld EPS = 1e-9;
    286 const ld PI = acos(-1.0);
    287 
    288 const int N = 200 * 1000 + 13;
    289 
    290 int n;
    291 int a[N];
    292 
    293 inline void read() {	
    294 	cin >> n;
    295 	for (int i = 0; i < n; i++) {
    296 		cin >> a[i];
    297 	}
    298 }
    299 
    300 inline int gcd(int a, int b) {
    301 	while (a != 0 && b != 0) {
    302 		if (a > b) {
    303 			a %= b;
    304 		} else {
    305 			b %= a;
    306 		}
    307 	}
    308 	return max(a, b);
    309 }
    310 
    311 inline void solve() {
    312 	int ma = *max_element(a, a + n);
    313     li sum = 0;
    314     for (int i = 0; i < n; i++) {
    315     	sum += a[i];
    316     }
    317     int g = ma - a[0];
    318     for (int i = 1; i < n; i++) {
    319     	g = gcd(g, ma - a[i]);
    320     }    
    321     li ans = (ma * 1ll * n - sum) / g;
    322     cout << ans << ' ' << g << endl;
    323 }
    324 
    325 int main () {
    326 #ifdef fcspartakm
    327     freopen("input.txt", "r", stdin);
    328     //freopen("output.txt", "w", stdout);
    329 #endif
    330     srand(time(NULL));
    331     cerr << setprecision(10) << fixed;
    332     
    333     read();
    334     solve();
    335  
    336     //cerr << "TIME: " << clock() << endl;
    337 }
    338 ```
    339 
    340 [1216E1 - Numerical Sequence (easy version)](/contest/1216/problem/E1 "Codeforces Round 587 (Div. 3)")
    341 
    342 **Tutorial**
    343 
    344 Tutorial is loading...
    345 
    346 **Solution**
    347 
    348 ```
    349 #include <bits/stdc++.h>
    350 
    351 using namespace std;
    352 
    353 int main() {
    354 #ifdef _DEBUG
    355 	freopen("input.txt", "r", stdin);
    356 //	freopen("output.txt", "w", stdout);
    357 #endif
    358 	
    359 	int q;
    360 	cin >> q;
    361 	
    362 	while (q--) {
    363 		long long k;
    364 		cin >> k;
    365 		--k;
    366 		long long lst = 0;
    367 		long long nxtpw = 1;
    368 		int numlen = 0;
    369 		for (long long i = 1; ; ++i) {
    370 			if (i == nxtpw) {
    371 				++numlen;
    372 				nxtpw *= 10;
    373 			}
    374 			lst += numlen;
    375 			if (k >= lst) {
    376 				k -= lst;
    377 			} else {
    378 				long long nxtpw = 1;
    379 				int numlen = 0;
    380 				for (long long j = 1; j <= i; ++j) {
    381 					if (j == nxtpw) {
    382 						++numlen;
    383 						nxtpw *= 10;
    384 					}
    385 					if (k >= numlen) {
    386 						k -= numlen;
    387 					} else {
    388 						cout << to_string(j)[k] << endl;
    389 						break;
    390 					}
    391 				}
    392 				break;
    393 			}
    394 		}
    395 	}
    396 	
    397 	return 0;
    398 }
    399 ```
    400 
    401 [1216E2 - Numerical Sequence (hard version)](/contest/1216/problem/E2 "Codeforces Round 587 (Div. 3)")
    402 
    403 **Tutorial**
    404 
    405 Tutorial is loading...
    406 
    407 **Solution**
    408 
    409 ```
    410 #include <bits/stdc++.h>
    411 
    412 using namespace std;
    413 
    414 long long get(long long r) {
    415 	return (r + 1) * r / 2;
    416 }
    417 
    418 long long sumto(long long r, int need) {
    419 	long long pw = 1;
    420 	long long sum = 0;
    421 	long long add = 0;
    422 	for (int len = 1; ; ++len) {
    423 		if (pw * 10 - 1 < r) {
    424 			long long cnt = pw * 10 - pw;
    425 			if (need) {
    426 				sum += add * cnt + get(cnt) * len;
    427 				add += cnt * len;
    428 			} else {
    429 				sum += cnt * len;
    430 			}
    431 		} else {
    432 			long long cnt = r - pw + 1;
    433 			if (need) {
    434 				sum += add * cnt + get(cnt) * len;
    435 			} else {
    436 				sum += cnt * len;
    437 			}
    438 			break;
    439 		}
    440 		pw *= 10;
    441 	}
    442 	return sum;
    443 }
    444 
    445 int main() {
    446 #ifdef _DEBUG
    447 	freopen("input.txt", "r", stdin);
    448 //	freopen("output.txt", "w", stdout);
    449 #endif
    450 
    451 	int q;
    452 	cin >> q;
    453 	while (q--) {
    454 		long long k;
    455 		cin >> k;
    456 		--k;
    457 		
    458 		long long l = 1	, r = 1e9;
    459 		long long res = -1;
    460 		while (r - l >= 0) {
    461 			long long mid = (l + r) >> 1;
    462 			if (sumto(mid, 1) > k) {
    463 				res = mid;
    464 				r = mid - 1;
    465 			} else {
    466 				l = mid + 1;
    467 			}
    468 		}
    469 		k -= sumto(res - 1, 1);
    470 		
    471 		l = 1, r = res;
    472 		long long num = -1;
    473 		while (r - l >= 0) {
    474 			int mid = (l + r) >> 1;
    475 			if (sumto(mid, 0) > k) {
    476 				num = mid;
    477 				r = mid - 1;
    478 			} else {
    479 				l = mid + 1;
    480 			}
    481 		}
    482 		
    483 		cout << to_string(num)[k - sumto(num - 1, 0)] << endl;
    484 	}
    485 	
    486 	return 0;
    487 }
    488 ```
    489 
    490 [1216F - Wi-Fi](/contest/1216/problem/F "Codeforces Round 587 (Div. 3)")
    491 
    492 **Tutorial**
    493 
    494 Tutorial is loading...
    495 
    496 **Solution**
    497 
    498 ```
    499 #include <bits/stdc++.h>
    500 
    501 using namespace std;
    502 
    503 int main() {
    504 #ifdef _DEBUG
    505 	freopen("input.txt", "r", stdin);
    506 //	freopen("output.txt", "w", stdout);
    507 #endif
    508 	
    509 	int n, k;
    510 	cin >> n >> k;
    511 	string s;
    512 	cin >> s;
    513 
    514 	vector<long long> dp(n + 1);
    515 	multiset<long long> mins, vals;
    516 	mins.insert(0);
    517 	vector<vector<long long>> del(n);
    518 	for (int i = n - 1; i >= 0; --i) {
    519 		dp[i] = i + 1 +  dp[i + 1];
    520 		if (i + k + 2 <= n) mins.erase(mins.find(dp[i + k + 2]));
    521 		for (auto it : del[i]) vals.erase(vals.find(it));
    522 		if (!vals.empty()) dp[i] = min(dp[i], *vals.begin());
    523 		if (s[i] == '1') {
    524 			long long val = (mins.empty() ? 0 : *mins.begin()) + i + 1;
    525 			dp[i] = min(dp[i], val);
    526 			vals.insert(val);
    527 			if (i - k - 1 >= 0) del[i - k - 1].push_back(val);
    528 		}
    529 		mins.insert(dp[i]);
    530 	}
    531 	
    532 	cout << dp[0] << endl;
    533 	
    534 	return 0;
    535 }
    536 ```