codeforces-scrape

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

1328.md (7242B)


      1 Source: https://codeforces.com/blog/entry/75246
      2 
      3 [1328A - Divisibility Problem](/contest/1328/problem/A "Codeforces Round 629 (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 t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int a, b;
     28 		cin >> a >> b;
     29 		if (a % b == 0) cout << 0 << endl;
     30 		else cout << b - a % b << endl;
     31 	}
     32 	
     33 	return 0;
     34 }
     35 ```
     36 
     37 [1328B - K-th Beautiful String](/contest/1328/problem/B "Codeforces Round 629 (Div. 3)")
     38 
     39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     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, k;
     59         cin >> n >> k;
     60         string s(n, 'a');
     61         for (int i = n - 2; i >= 0; i--) {
     62             if (k <= (n - i - 1)) {
     63                 s[i] = 'b';
     64                 s[n - k] = 'b';
     65                 cout << s << endl;
     66                 break;
     67             }
     68             k -= (n - i - 1);
     69         }
     70     }
     71 }
     72 ```
     73 
     74 [1328C - Ternary XOR](/contest/1328/problem/C "Codeforces Round 629 (Div. 3)")
     75 
     76 Idea: [vovuh](/profile/vovuh "Master vovuh")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 
     87 using namespace std;
     88 
     89 int main() {
     90 #ifdef _DEBUG
     91 	freopen("input.txt", "r", stdin);
     92 //	freopen("output.txt", "w", stdout);
     93 #endif
     94 	
     95 	int t;
     96 	cin >> t;
     97 	while (t--) {
     98 		int n;
     99 		string x;
    100 		cin >> n >> x;
    101 		string a(n, '0'), b(n, '0');
    102 		for (int i = 0; i < n; ++i) {
    103 			if (x[i] == '1') {
    104 				a[i] = '1';
    105 				b[i] = '0';
    106 				for (int j = i + 1; j < n; ++j) {
    107 					b[j] = x[j];
    108 				}
    109 				break;
    110 			} else {
    111 				a[i] = b[i] = '0' + (x[i] - '0') / 2;
    112 			}
    113 		}
    114 		cout << a << endl << b << endl;
    115 	}
    116 	
    117 	return 0;
    118 }
    119 ```
    120 
    121 [1328D - Carousel](/contest/1328/problem/D "Codeforces Round 629 (Div. 3)")
    122 
    123 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    124 
    125 **Tutorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Solution**
    130 
    131 ```
    132 #include <bits/stdc++.h>
    133 
    134 using namespace std;
    135 
    136 int solve() {
    137 	int n;
    138 	cin >> n;
    139 	vector<int> a(n);
    140 	for (int i = 0; i < n; ++i) {
    141 		cin >> a[i];
    142 	}
    143 	
    144 	if (count(a.begin(), a.end(), a[0]) == n) {
    145 		cout << 1 << endl;
    146 		for (int i = 0; i < n; ++i) {
    147 			cout << 1 << " ";
    148 		}
    149 		cout << endl;
    150 		return 0;
    151 	}
    152 	
    153 	if (n % 2 == 0) {
    154 		cout << 2 << endl;
    155 		for (int i = 0; i < n; ++i) {
    156 			cout << i % 2 + 1 << " ";
    157 		}
    158 		cout << endl;
    159 		return 0;
    160 	}
    161 	
    162 	for (int i = 0; i < n; ++i) {
    163 		if (a[i] == a[(i + 1) % n]) {
    164 			vector<int> ans(n);
    165 			for (int j = 0, pos = i + 1; pos < n; ++pos, j ^= 1) {
    166 				ans[pos] = j + 1;
    167 			}
    168 			for (int j = 0, pos = i; pos >= 0; --pos, j ^= 1) {
    169 				ans[pos] = j + 1;
    170 			}
    171 			cout << 2 << endl;
    172 			for (int pos = 0; pos < n; ++pos) {
    173 				cout << ans[pos] << " ";
    174 			}
    175 			cout << endl;
    176 			return 0;
    177 		}
    178 	}
    179 	
    180 	cout << 3 << endl;
    181 	for (int i = 0; i < n - 1; ++i) {
    182 		cout << i % 2 + 1 << " ";
    183 	}
    184 	cout << 3 << endl;
    185     return 0;    
    186 }
    187 
    188 int main() {
    189 #ifdef _DEBUG
    190 	freopen("input.txt", "r", stdin);
    191 //	freopen("output.txt", "w", stdout);
    192 #endif
    193 
    194 int q;
    195 cin >> q;
    196 for (int qq = 0; qq < q; qq++) {
    197     solve();
    198 }
    199 
    200 	return 0;
    201 }
    202 ```
    203 
    204 [1328E - Tree Queries](/contest/1328/problem/E "Codeforces Round 629 (Div. 3)")
    205 
    206 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [vovuh](/profile/vovuh "Master vovuh")
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 
    217 using namespace std;
    218 
    219 int T;
    220 vector<int> p, d;
    221 vector<int> tin, tout;
    222 vector<vector<int>> g;
    223 
    224 void dfs(int v, int par = -1, int dep = 0) {
    225 	p[v] = par;
    226 	d[v] = dep;
    227 	tin[v] = T++;
    228 	for (auto to : g[v]) {
    229 		if (to == par) continue;
    230 		dfs(to, v, dep + 1);
    231 	}
    232 	tout[v] = T++;
    233 }
    234 
    235 bool isAnc(int v, int u) {
    236 	return tin[v] <= tin[u] && tout[u] <= tout[v];
    237 }
    238 
    239 int main() {
    240 #ifdef _DEBUG
    241 	freopen("input.txt", "r", stdin);
    242 //	freopen("output.txt", "w", stdout);
    243 #endif
    244 	
    245 	int n, m;
    246 	cin >> n >> m;
    247 	T = 0;
    248 	p = d = vector<int>(n);
    249 	tin = tout = vector<int>(n);
    250 	g = vector<vector<int>>(n);
    251 	for (int i = 0; i < n - 1; ++i) {
    252 		int x, y;
    253 		cin >> x >> y;
    254 		--x, --y;
    255 		g[x].push_back(y);
    256 		g[y].push_back(x);
    257 	}
    258 	dfs(0);
    259 	
    260 	for (int i = 0; i < m; ++i) {
    261 		int k;
    262 		cin >> k;
    263 		vector<int> v(k);
    264 		for (auto &it : v) {
    265 			cin >> it;
    266 			--it;
    267 		}
    268 		
    269 		int u = v[0];
    270 		for (auto it : v) if (d[u] < d[it]) u = it;
    271 		for (auto &it : v) {
    272 			if (it == u) continue;
    273 			if (p[it] != -1) it = p[it];
    274 		}
    275 		bool ok = true;
    276 		for (auto it : v) ok &= isAnc(it, u);
    277 		if (ok) cout << "YES" << endl;
    278 		else cout << "NO" << endl;
    279 	}
    280 	
    281 	return 0;
    282 }
    283 ```
    284 
    285 [1328F - Make k Equal](/contest/1328/problem/F "Codeforces Round 629 (Div. 3)")
    286 
    287 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    288 
    289 **Tutorial**
    290 
    291 Tutorial is loading...
    292 
    293 **Solution**
    294 
    295 ```
    296 #include <bits/stdc++.h>
    297 
    298 using namespace std;
    299 
    300 const long long INF64 = 1e18;
    301 
    302 int main() {
    303 #ifdef _DEBUG
    304 	freopen("input.txt", "r", stdin);
    305 //	freopen("output.txt", "w", stdout);
    306 #endif
    307 	
    308 	int n, k;
    309 	cin >> n >> k;
    310 	vector<int> a(n);
    311 	for (auto &it : a) cin >> it;
    312 	
    313 	sort(a.begin(), a.end());
    314 	vector<pair<int, int>> cnt;
    315 	for (auto it : a) {
    316 		if (cnt.empty() || cnt.back().first != it) {
    317 			cnt.push_back({it, 1});
    318 		} else {
    319 			++cnt.back().second;
    320 		}
    321 	}
    322 	vector<long long> prefsum, sufsum;
    323 	vector<int> prefcnt, sufcnt; 
    324 	for (int i = 0; i < int(cnt.size()); ++i) {
    325 		long long cursum = cnt[i].first * 1ll * cnt[i].second;
    326 		int curcnt = cnt[i].second;
    327 		if (prefsum.empty()) {
    328 			prefsum.push_back(cursum);
    329 			prefcnt.push_back(curcnt);
    330 		} else {
    331 			prefsum.push_back(prefsum.back() + cursum);
    332 			prefcnt.push_back(prefcnt.back() + curcnt);
    333 		}
    334 	}
    335 	for (int i = int(cnt.size()) - 1; i >= 0; --i) {
    336 		long long cursum = cnt[i].first * 1ll * cnt[i].second;
    337 		int curcnt = cnt[i].second;
    338 		if (sufsum.empty()) {
    339 			sufsum.push_back(cursum);
    340 			sufcnt.push_back(curcnt);
    341 		} else {
    342 			sufsum.push_back(sufsum.back() + cursum);
    343 			sufcnt.push_back(sufcnt.back() + curcnt);
    344 		}
    345 	}
    346 	reverse(sufsum.begin(), sufsum.end());
    347 	reverse(sufcnt.begin(), sufcnt.end());
    348 	
    349 	long long ans = INF64;
    350 	for (int i = 0; i < int(cnt.size()); ++i) {
    351 		int cur = max(0, k - cnt[i].second);
    352 		
    353 		int needl = 0;
    354 		if (i > 0) needl = min(cur, prefcnt[i - 1]);
    355 		int needr = max(0, cur - needl);
    356 		long long res = 0;
    357 		if (i > 0 && needl > 0) {
    358 			res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
    359 			res += needl;
    360 		}
    361 		if (i + 1 < int(cnt.size()) && needr > 0) {
    362 			res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
    363 			res += needr;
    364 		}
    365 		ans = min(ans, res);
    366 		
    367 		needr = 0;
    368 		if (i + 1 < int(cnt.size())) needr = min(cur, sufcnt[i + 1]);
    369 		needl = max(0, cur - needr);
    370 		res = 0;
    371 		if (i > 0 && needl > 0) {
    372 			res += prefcnt[i - 1] * 1ll * (cnt[i].first - 1) - prefsum[i - 1];
    373 			res += needl;
    374 		}
    375 		if (i + 1 < int(cnt.size()) && needr > 0) {
    376 			res += sufsum[i + 1] - sufcnt[i + 1] * 1ll * (cnt[i].first + 1);
    377 			res += needr;
    378 		}
    379 		ans = min(ans, res);
    380 	}
    381 	
    382 	cout << ans << endl;
    383 	
    384 	return 0;
    385 }
    386 ```