codeforces-scrape

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

1213.md (7118B)


      1 Source: https://codeforces.com/blog/entry/69464
      2 
      3 All ideas except the problem C belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1213A - Chips Moving](/contest/1213/problem/A "Codeforces Round 582 (Div. 3)")
      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 n;
     25 	cin >> n;
     26 	int cnto = 0;
     27 	for (int i = 0; i < n; ++i) {
     28 		int x;
     29 		cin >> x;
     30 		cnto += x & 1;
     31 	}
     32 	
     33 	cout << min(cnto, n - cnto) << endl;
     34 	
     35 	return 0;
     36 }
     37 ```
     38 
     39 [1213B - Bad Prices](/contest/1213/problem/B "Codeforces Round 582 (Div. 3)")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 #define forn(i, n) for (int i = 0; i < int(n); i++)
     53 
     54 int main() {
     55     int t;
     56     cin >> t;
     57     forn(tt, t) {
     58         int n;
     59         cin >> n;
     60         vector<int> a(n);
     61         forn(i, n)
     62             cin >> a[i];
     63         int ans = 0;
     64         int right_min = INT_MAX;
     65         for (int i = n -  1; i >= 0; i--) {
     66             if (a[i] > right_min)
     67                 ans++;
     68             right_min = min(right_min, a[i]);
     69         }
     70         cout << ans << endl;
     71     }
     72 }
     73 ```
     74 
     75 [1213C - Book Reading](/contest/1213/problem/C "Codeforces Round 582 (Div. 3)")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85 
     86 using namespace std;
     87 
     88 #define forn(i, n) for (int i = 0; i < int(n); i++)
     89 
     90 int main() {
     91     int q;
     92     cin >> q;
     93     forn(i, q) {
     94         long long n, m;
     95         cin >> n >> m;
     96         n = n / m;
     97         vector<int> digits(10);
     98         forn(i, 10)
     99             digits[i] = ((i + 1) * m) % 10;
    100         long long sum = 0;
    101         forn(i, n % 10)
    102             sum += digits[i];
    103         cout << sum + n / 10 * accumulate(digits.begin(), digits.end(), 0LL) << endl;
    104     }
    105 }
    106 ```
    107 
    108 [1213D1 - Equalizing by Division (easy version)](/contest/1213/problem/D1 "Codeforces Round 582 (Div. 3)")
    109 
    110 **Tutorial**
    111 
    112 Tutorial is loading...
    113 
    114 **Solution**
    115 
    116 ```
    117 #include <bits/stdc++.h>
    118 
    119 using namespace std;
    120 
    121 int main() {
    122 #ifdef _DEBUG
    123 	freopen("input.txt", "r", stdin);
    124 //	freopen("output.txt", "w", stdout);
    125 #endif
    126 	
    127 	int n, k;
    128 	cin >> n >> k;
    129 	vector<int> a(n);
    130 	for (int i = 0; i < n; ++i) {
    131 		cin >> a[i];
    132 	}
    133 	
    134 	vector<int> poss;
    135 	for (int i = 0; i < n; ++i) {
    136 		int x = a[i];
    137 		while (x > 0) {
    138 			poss.push_back(x);
    139 			x /= 2;
    140 		}
    141 	}
    142 	
    143 	int ans = 1e9;
    144 	for (auto res : poss) {
    145 		vector<int> cnt;
    146 		for (int i = 0; i < n; ++i) {
    147 			int x = a[i];
    148 			int cur = 0;
    149 			while (x > res) {
    150 				x /= 2;
    151 				++cur;
    152 			}
    153 			if (x == res) {
    154 				cnt.push_back(cur);
    155 			}
    156 		}
    157 		if (int(cnt.size()) < k) continue;
    158 		sort(cnt.begin(), cnt.end());
    159 		ans = min(ans, accumulate(cnt.begin(), cnt.begin() + k, 0));
    160 	}
    161 	
    162 	cout << ans << endl;
    163 	
    164 	return 0;
    165 }
    166 ```
    167 
    168 [1213D2 - Equalizing by Division (hard version)](/contest/1213/problem/D2 "Codeforces Round 582 (Div. 3)")
    169 
    170 **Tutorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Solution**
    175 
    176 ```
    177 #include <bits/stdc++.h>
    178 
    179 using namespace std;
    180 
    181 int main() {
    182 #ifdef _DEBUG
    183 	freopen("input.txt", "r", stdin);
    184 //	freopen("output.txt", "w", stdout);
    185 #endif
    186 	
    187 	int n, k;
    188 	cin >> n >> k;
    189 	vector<int> a(n);
    190 	for (int i = 0; i < n; ++i) {
    191 		cin >> a[i];
    192 	}
    193 	
    194 	vector<vector<int>> vals(200 * 1000 + 11);
    195 	for (int i = 0; i < n; ++i) {
    196 		int x = a[i];
    197 		int cur = 0;
    198 		while (x > 0) {
    199 			vals[x].push_back(cur);
    200 			x /= 2;
    201 			++cur;
    202 		}
    203 	}
    204 	
    205 	int ans = 1e9;
    206 	for (int i = 0; i <= 200 * 1000; ++i) {
    207 		sort(vals[i].begin(), vals[i].end());
    208 		if (int(vals[i].size()) < k) continue;
    209 		ans = min(ans, accumulate(vals[i].begin(), vals[i].begin() + k, 0));
    210 	}
    211 	
    212 	cout << ans << endl;
    213 	
    214 	return 0;
    215 }
    216 ```
    217 
    218 [1213E - Two Small Strings](/contest/1213/problem/E "Codeforces Round 582 (Div. 3)")
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution**
    225 
    226 ```
    227 #include <bits/stdc++.h>
    228 
    229 using namespace std;
    230 
    231 int main() {
    232 #ifdef _DEBUG
    233 	freopen("input.txt", "r", stdin);
    234 //	freopen("output.txt", "w", stdout);
    235 #endif
    236 	
    237 	int n;
    238 	string s, t;
    239 	cin >> n >> s >> t;
    240 	string abc = "abc";
    241 	vector<string> res;
    242 	do {
    243 		string cur;
    244 		for (int i = 0; i < n; ++i) cur += abc;
    245 		res.push_back(cur);
    246 		res.push_back(string(n, abc[0]) + string(n, abc[1]) + string(n, abc[2]));
    247 	} while (next_permutation(abc.begin(), abc.end()));
    248 	
    249 	for (auto str : res) {
    250 		if (str.find(s) == string::npos && str.find(t) == string::npos) {
    251 			cout << "YES" << endl << str << endl;
    252 			return 0;
    253 		}
    254 	}
    255 	
    256 	assert(false);
    257 	cout << "NO" << endl;
    258 	
    259 	return 0;
    260 }
    261 ```
    262 
    263 [1213F - Unstable String Sort](/contest/1213/problem/F "Codeforces Round 582 (Div. 3)")
    264 
    265 **Tutorial**
    266 
    267 Tutorial is loading...
    268 
    269 **Solution**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 
    274 using namespace std;
    275 
    276 int main() {
    277 #ifdef _DEBUG
    278 	freopen("input.txt", "r", stdin);
    279 //	freopen("output.txt", "w", stdout);
    280 #endif
    281 	
    282 	int n, k;
    283 	cin >> n >> k;
    284 	vector<int> p1(n), p2(n);
    285 	for (int i = 0; i < n; ++i) {
    286 		cin >> p1[i];
    287 		--p1[i];
    288 	}
    289 	for (int i = 0; i < n; ++i) {
    290 		cin >> p2[i];
    291 		--p2[i];
    292 	}
    293 	
    294 	set<int> vals1, vals2;
    295 	vector<int> rb;
    296 	for (int i = 0; i < n; ++i) {
    297 		if (vals2.count(p1[i])) {
    298 			vals2.erase(p1[i]);
    299 		} else {
    300 			vals1.insert(p1[i]);
    301 		}
    302 		if (vals1.count(p2[i])) {
    303 			vals1.erase(p2[i]);
    304 		} else {
    305 			vals2.insert(p2[i]);
    306 		}
    307 		if (vals1.empty() && vals2.empty()) {
    308 			rb.push_back(i);
    309 		}
    310 	}
    311 	
    312 	if (int(rb.size()) < k) {
    313 		cout << "NO" << endl;
    314 	} else {
    315 		string s(n, ' ');
    316 		int l = 0;
    317 		for (int it = 0; it < int(rb.size()); ++it) {
    318 			int r = rb[it];
    319 			char c = 'a' + min(it, 25);
    320 			for (int i = l; i <= r; ++i) {
    321 				s[p1[i]] = c;
    322 			}
    323 			l = r + 1;
    324 		}
    325 		cout << "YES" << endl << s << endl;
    326 	}
    327 	
    328 	return 0;
    329 }
    330 ```
    331 
    332 [1213G - Path Queries](/contest/1213/problem/G "Codeforces Round 582 (Div. 3)")
    333 
    334 **Tutorial**
    335 
    336 Tutorial is loading...
    337 
    338 **Solution**
    339 
    340 ```
    341 #include <bits/stdc++.h>
    342 
    343 using namespace std;
    344 
    345 vector<int> p, rk;
    346 
    347 int getp(int v) {
    348 	if (v == p[v]) return v;
    349 	return p[v] = getp(p[v]);
    350 }
    351 
    352 long long res;
    353 
    354 long long get(int cnt) {
    355 	return cnt * 1ll * (cnt - 1) / 2;
    356 }
    357 
    358 void merge(int u, int v) {
    359 	u = getp(u);
    360 	v = getp(v);
    361 	
    362 	if (rk[u] < rk[v]) swap(u, v);
    363 	
    364 	res -= get(rk[u]);
    365 	res -= get(rk[v]);
    366 	
    367 	rk[u] += rk[v];
    368 	
    369 	res += get(rk[u]);
    370 	
    371 	p[v] = u;
    372 }
    373 
    374 int main() {
    375 #ifdef _DEBUG
    376 	freopen("input.txt", "r", stdin);
    377 //	freopen("output.txt", "w", stdout);
    378 #endif
    379 	
    380 	int n, m;
    381 	cin >> n >> m;
    382 	
    383 	res = 0;
    384 	p = rk = vector<int>(n, 1);
    385 	iota(p.begin(), p.end(), 0);
    386 	
    387 	vector<pair<int, pair<int, int>>> e(n - 1);
    388 	for (int i = 0; i < n - 1; ++i) {
    389 		cin >> e[i].second.first >> e[i].second.second >> e[i].first;
    390 		--e[i].second.first;
    391 		--e[i].second.second;
    392 	}
    393 	
    394 	vector<pair<int, int>> q(m);
    395 	vector<long long> ans(m);
    396 	for (int i = 0; i < m; ++i) {
    397 		cin >> q[i].first;
    398 		q[i].second = i;
    399 	}
    400 	
    401 	sort(e.begin(), e.end());
    402 	sort(q.begin(), q.end());
    403 	
    404 	int pos = 0;
    405 	for (int i = 0; i < m; ++i) {
    406 		while (pos < n - 1 && e[pos].first <= q[i].first) {
    407 			int u = e[pos].second.first;
    408 			int v = e[pos].second.second;
    409 			merge(u, v);
    410 			++pos;
    411 		}
    412 		ans[q[i].second] = res;
    413 	}
    414 	
    415 	for (int i = 0; i < m; ++i) {
    416 		cout << ans[i] << " ";
    417 	}
    418 	cout << endl;
    419 	
    420 	return 0;
    421 }
    422 ```