codeforces-scrape

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

1374.md (8774B)


      1 Source: https://codeforces.com/blog/entry/79517
      2 
      3 [1374A - Required Remainder](/contest/1374/problem/A "Codeforces Round 653 (Div. 3)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      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 t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int x, y, n;
     28 		cin >> x >> y >> n;
     29 		if (n - n % x + y <= n) {
     30 			cout << n - n % x + y << endl;
     31 		} else {
     32 			cout << n - n % x - (x - y) << endl;
     33 		}
     34 	}
     35 	
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1374B - Multiply by 2, divide by 6](/contest/1374/problem/B "Codeforces Round 653 (Div. 3)")
     41 
     42 Idea: [vovuh](/profile/vovuh "Master vovuh")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 int main() {
     56 #ifdef _DEBUG
     57 	freopen("input.txt", "r", stdin);
     58 //	freopen("output.txt", "w", stdout);
     59 #endif
     60 	
     61 	int t;
     62 	cin >> t;
     63 	while (t--) {
     64 		int n;
     65 		cin >> n;
     66 		int cnt2 = 0, cnt3 = 0;
     67 		while (n % 2 == 0) {
     68 			n /= 2;
     69 			++cnt2;
     70 		}
     71 		while (n % 3 == 0) {
     72 			n /= 3;
     73 			++cnt3;
     74 		}
     75 		if (n == 1 && cnt2 <= cnt3) {
     76 			cout << 2 * cnt3 - cnt2 << endl;
     77 		} else {
     78 			cout << -1 << endl;
     79 		}
     80 	}
     81 	
     82 	return 0;
     83 }
     84 ```
     85 
     86 [1374C - Move Brackets](/contest/1374/problem/C "Codeforces Round 653 (Div. 3)")
     87 
     88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 
     99 using namespace std;
    100 
    101 int main() {
    102 #ifdef _DEBUG
    103 	freopen("input.txt", "r", stdin);
    104 //	freopen("output.txt", "w", stdout);
    105 #endif
    106 	
    107 	int t;
    108 	cin >> t;
    109 	while (t--) {
    110 		int n;
    111 		string s;
    112 		cin >> n >> s;
    113 		int ans = 0;
    114 		int bal = 0;
    115 		for (int i = 0; i < n; ++i) {
    116 			if (s[i] == '(') ++bal;
    117 			else {
    118 				--bal;
    119 				if (bal < 0) {
    120 					bal = 0;
    121 					++ans;
    122 				}
    123 			}
    124 		}
    125 		cout << ans << endl;
    126 	}
    127 	
    128 	return 0;
    129 }
    130 ```
    131 
    132 [1374D - Zero Remainder Array](/contest/1374/problem/D "Codeforces Round 653 (Div. 3)")
    133 
    134 Idea: [vovuh](/profile/vovuh "Master vovuh")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 
    145 using namespace std;
    146 
    147 int main() {
    148 #ifdef _DEBUG
    149 	freopen("input.txt", "r", stdin);
    150 //	freopen("output.txt", "w", stdout);
    151 #endif
    152 
    153 	int t;
    154 	cin >> t;
    155 	while (t--) {
    156 		int n, k;
    157 		cin >> n >> k;
    158 		vector<int> a(n);
    159 		for (auto &it : a) cin >> it;
    160 		map<int, int> cnt;
    161 		int mx = 0;
    162 		for (auto &it : a) {
    163 			if (it % k == 0) continue;
    164 			++cnt[k - it % k];
    165 			mx = max(mx, cnt[k - it % k]);
    166 		}
    167 		long long ans = 0;
    168 		for (auto [key, value] : cnt) {
    169 			if (value == mx) {
    170 				ans = k * 1ll * (value - 1) + key + 1;
    171 			}
    172 		}
    173 		cout << ans << endl;
    174 	}
    175 	
    176 	return 0;
    177 }
    178 ```
    179 
    180 [1374E1 - Reading Books (easy version)](/contest/1374/problem/E1 "Codeforces Round 653 (Div. 3)")
    181 
    182 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    183 
    184 **Tutorial**
    185 
    186 Tutorial is loading...
    187 
    188 **Solution**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 
    193 using namespace std;
    194 
    195 const int INF = 2e9 + 1;
    196 
    197 int main() {
    198 #ifdef _DEBUG
    199 	freopen("input.txt", "r", stdin);
    200 //	freopen("output.txt", "w", stdout);
    201 #endif
    202 	
    203 	int n, k;
    204 	cin >> n >> k;
    205 	vector<int> times[4];
    206 	vector<int> sums[4];
    207 	for (int i = 0; i < n; ++i) {
    208 		int t, a, b;
    209 		cin >> t >> a >> b;
    210 		times[a * 2 + b].push_back(t);
    211 	}
    212 	for (int i = 0; i < 4; ++i) {
    213 		sort(times[i].begin(), times[i].end());
    214 		sums[i].push_back(0);
    215 		for (auto it : times[i]) {
    216 			sums[i].push_back(sums[i].back() + it);
    217 		}
    218 	}
    219 	
    220 	int ans = INF;
    221 	for (int cnt = 0; cnt < min(k + 1, int(sums[3].size())); ++cnt) {
    222 		if (k - cnt < int(sums[1].size()) && k - cnt < int(sums[2].size())) {
    223 			ans = min(ans, sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt]);
    224 		}
    225 	}
    226 	
    227 	if (ans == INF) ans = -1;
    228 	cout << ans << endl;
    229 	
    230 	return 0;
    231 }
    232 ```
    233 
    234 [1374E2 - Reading Books (hard version)](/contest/1374/problem/E2 "Codeforces Round 653 (Div. 3)")
    235 
    236 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    237 
    238 **Tutorial**
    239 
    240 Tutorial is loading...
    241 
    242 **Solution**
    243 
    244 ```
    245 #include <bits/stdc++.h>
    246 
    247 using namespace std;
    248 
    249 const int INF = 2e9 + 1;
    250 
    251 #define size(a) int((a).size())
    252 
    253 void updateSt(set<pair<int, int>> &st, set<pair<int, int>> &fr, int &sum, int need) {
    254 	need = max(need, 0);
    255 	while (true) {
    256 		bool useful = false;
    257 		while (size(st) > need) {
    258 			sum -= st.rbegin()->first;
    259 			fr.insert(*st.rbegin());
    260 			st.erase(prev(st.end()));
    261 			useful = true;
    262 		}
    263 		while (size(st) < need && size(fr) > 0) {
    264 			sum += fr.begin()->first;
    265 			st.insert(*fr.begin());
    266 			fr.erase(fr.begin());
    267 			useful = true;
    268 		}
    269 		while (!st.empty() && !fr.empty() && fr.begin()->first < st.rbegin()->first) {
    270 			sum -= st.rbegin()->first;
    271 			sum += fr.begin()->first;
    272 			fr.insert(*st.rbegin());
    273 			st.erase(prev(st.end()));
    274 			st.insert(*fr.begin());
    275 			fr.erase(fr.begin());
    276 			useful = true;
    277 		}
    278 		if (!useful) break;
    279 	}
    280 }
    281 
    282 int main() {
    283 #ifdef _DEBUG
    284 	freopen("input.txt", "r", stdin);
    285 //	freopen("output.txt", "w", stdout);
    286 #endif
    287 	
    288 	int n, m, k;
    289 	cin >> n >> m >> k;
    290 	vector<pair<int, int>> times[4];
    291 	vector<int> sums[4];
    292 	for (int i = 0; i < n; ++i) {
    293 		int t, a, b;
    294 		cin >> t >> a >> b;
    295 		times[a * 2 + b].push_back({t, i});
    296 	}
    297 	for (int i = 0; i < 4; ++i) {
    298 		sort(times[i].begin(), times[i].end());
    299 		sums[i].push_back(0);
    300 		for (auto it : times[i]) {
    301 			sums[i].push_back(sums[i].back() + it.first);
    302 		}
    303 	}
    304 	
    305 	int ans = INF;
    306 	int pos = INF;
    307 	set<pair<int, int>> st;
    308 	set<pair<int, int>> fr;
    309 	int sum = 0;
    310 	vector<int> res;
    311 	for (int iter = 0; iter < 2; ++iter) {
    312 		st.clear();
    313 		fr.clear();
    314 		sum = 0;
    315 		int start = 0;
    316 		while (k - start >= size(sums[1]) || k - start >= size(sums[2]) || m - start - (k - start) * 2 < 0) {
    317 			++start;
    318 		}
    319 		if (start >= size(sums[3])) {
    320 			cout << -1 << endl;
    321 			return 0;
    322 		}
    323 		int need = m - start - (k - start) * 2;
    324 		for (int i = 0; i < 3; ++i) {
    325 			for (int p = size(times[i]) - 1; p >= (i == 0 ? 0 : k - start); --p) {
    326 				fr.insert(times[i][p]);
    327 			}
    328 		}
    329 		updateSt(st, fr, sum, need);
    330 		for (int cnt = start; cnt < (iter == 0 ? size(sums[3]) : pos); ++cnt) {
    331 			if (k - cnt >= 0) {	
    332 				if (cnt + (k - cnt) * 2 + size(st) == m) {
    333 					if (ans > sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum) {
    334 						ans = sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum;
    335 						pos = cnt + 1;
    336 					}
    337 				}
    338 			} else {
    339 				if (cnt + size(st) == m) {
    340 					if (ans > sums[3][cnt] + sum) {
    341 						ans = sums[3][cnt] + sum;
    342 						pos = cnt + 1;
    343 					}
    344 				}
    345 			}
    346 			if (iter == 1 && cnt + 1 == pos) break;
    347 			need -= 1;
    348 			if (k - cnt > 0) {
    349 				need += 2;
    350 				fr.insert(times[1][k - cnt - 1]);
    351 				fr.insert(times[2][k - cnt - 1]);
    352 			}
    353 			updateSt(st, fr, sum, need);
    354 		}
    355 		if (iter == 1) {
    356 			for (int i = 0; i + 1 < pos; ++i) res.push_back(times[3][i].second);
    357 			for (int i = 0; i <= k - pos; ++i) {
    358 				res.push_back(times[1][i].second);
    359 				res.push_back(times[2][i].second);
    360 			}
    361 			for (auto [value, position] : st) res.push_back(position);
    362 		}
    363 	}
    364 	
    365 	cout << ans << endl;
    366 	for (auto it : res) cout << it + 1 << " ";
    367 	cout << endl;
    368 	
    369 	return 0;
    370 }
    371 ```
    372 
    373 [1374F - Cyclic Shifts Sorting](/contest/1374/problem/F "Codeforces Round 653 (Div. 3)")
    374 
    375 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    376 
    377 **Tutorial**
    378 
    379 Tutorial is loading...
    380 
    381 **Solution**
    382 
    383 ```
    384 #include <bits/stdc++.h>
    385 
    386 using namespace std;
    387 
    388 int main() {
    389 #ifdef _DEBUG
    390 	freopen("input.txt", "r", stdin);
    391 //	freopen("output.txt", "w", stdout);
    392 #endif
    393 	
    394 	auto make = [](vector<int> &a, int pos) {
    395 		swap(a[pos + 1], a[pos + 2]);
    396 		swap(a[pos], a[pos + 1]);
    397 	};
    398 
    399 	int t;
    400 	cin >> t;
    401 	while (t--) {
    402 		int n;
    403 		cin >> n;
    404 		vector<int> a(n);
    405 		vector<pair<int, int>> res(n);
    406 		for (int i = 0; i < n; ++i) {
    407 			cin >> a[i];
    408 			res[i] = { a[i], i };
    409 		}
    410 		sort(res.begin(), res.end());
    411 		for (int i = 0; i < n; ++i) {
    412 			a[res[i].second] = i;
    413 		}
    414 		int cnt = 0;
    415 		for (int i = 0; i < n; ++i) {
    416 			for (int j = i + 1; j < n; ++j) {
    417 				cnt += a[j] < a[i];
    418 			}
    419 		}
    420 		if (cnt & 1) {
    421 			for (int i = 0; i < n - 1; ++i) {
    422 				if (res[i].first == res[i + 1].first) {
    423 					swap(a[res[i].second], a[res[i + 1].second]);
    424 					break;
    425 				}
    426 			}
    427 		}
    428 		vector<int> ans;
    429 		for (int i = 0; i < n - 2; ++i) {
    430 			int pos = min_element(a.begin() + i, a.end()) - a.begin();
    431 			while (pos > i + 1) {
    432 				make(a, pos - 2);
    433 				ans.push_back(pos - 2);
    434 				pos -= 2;
    435 			}
    436 			if (pos != i) {
    437 				make(a, i);
    438 				make(a, i);
    439 				ans.push_back(i);
    440 				ans.push_back(i);
    441 				pos = i;
    442 			}
    443 		}
    444 		for (int i = 0; i < 3; ++i) {
    445 			if (is_sorted(a.begin(), a.end())) {
    446 				break;
    447 			}
    448 			make(a, n - 3);
    449 			ans.push_back(n - 3);
    450 		}
    451 		if (!is_sorted(a.begin(), a.end())) {
    452 			cout << -1 << endl;
    453 		} else {
    454 			cout << ans.size() << endl;
    455 			for (auto it : ans) cout << it + 1 << " ";
    456 			cout << endl;
    457 		}
    458 	}
    459 	
    460 	return 0;
    461 }
    462 ```