codeforces-scrape

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

1343.md (6321B)


      1 Source: https://codeforces.com/blog/entry/76352
      2 
      3 [1343A - Candies](/contest/1343/problem/A "Codeforces Round 636 (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 n;
     28 		cin >> n;
     29 		for (int pw = 2; pw < 30; ++pw) {
     30 			int val = (1 << pw) - 1;
     31 			if (n % val == 0) {
     32 				cerr << val << endl;
     33 				cout << n / val << endl;
     34 				break;
     35 			}
     36 		}
     37 	}
     38 	
     39 	return 0;
     40 }
     41 ```
     42 
     43 [1343B - Balanced Array](/contest/1343/problem/B "Codeforces Round 636 (Div. 3)")
     44 
     45 Idea: [vovuh](/profile/vovuh "Master vovuh")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 int main() {
     59 #ifdef _DEBUG
     60 	freopen("input.txt", "r", stdin);
     61 //	freopen("output.txt", "w", stdout);
     62 #endif
     63 	
     64 	int t;
     65 	cin >> t;
     66 	while (t--) {
     67 		int n;
     68 		cin >> n;
     69 		n /= 2;
     70 		if (n & 1) {
     71 			cout << "NO" << endl;
     72 			continue;
     73 		}
     74 		cout << "YES" << endl;
     75 		for (int i = 1; i <= n; ++i) {
     76 			cout << i * 2 << " ";
     77 		}
     78 		for (int i = 1; i < n; ++i) {
     79 			cout << i * 2 - 1 << " ";
     80 		}
     81 		cout << 3 * n - 1 << endl;
     82 	}
     83 	
     84 	return 0;
     85 }
     86 ```
     87 
     88 [1343C - Alternating Subsequence](/contest/1343/problem/C "Codeforces Round 636 (Div. 3)")
     89 
     90 Idea: [vovuh](/profile/vovuh "Master vovuh") and [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 
    101 using namespace std;
    102 
    103 int main() {
    104 #ifdef _DEBUG
    105 	freopen("input.txt", "r", stdin);
    106 //	freopen("output.txt", "w", stdout);
    107 #endif
    108 	
    109 	auto sgn = [&](int x) {
    110 		if (x > 0) return 1;
    111 		else return -1;
    112 	};
    113 
    114 	int t;
    115 	cin >> t;
    116 	while (t--) {
    117 		int n;
    118 		cin >> n;
    119 		vector<int> a(n);
    120 		for (auto &it : a) cin >> it;
    121 		long long sum = 0;
    122 		for (int i = 0; i < n; ++i) {
    123 			int cur = a[i];
    124 			int j = i;
    125 			while (j < n && sgn(a[i]) == sgn(a[j])) {
    126 				cur = max(cur, a[j]);
    127 				++j;
    128 			}
    129 			sum += cur;
    130 			i = j - 1;
    131 		}
    132 		cout << sum << endl;
    133 	}
    134 	
    135 	return 0;
    136 }
    137 ```
    138 
    139 [1343D - Constant Palindrome Sum](/contest/1343/problem/D "Codeforces Round 636 (Div. 3)")
    140 
    141 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    142 
    143 **Tutorial**
    144 
    145 Tutorial is loading...
    146 
    147 **Solution**
    148 
    149 ```
    150 #include <bits/stdc++.h>
    151 
    152 using namespace std;
    153 
    154 int main() {
    155 #ifdef _DEBUG
    156 	freopen("input.txt", "r", stdin);
    157 //	freopen("output.txt", "w", stdout);
    158 #endif
    159 	
    160 	int t;
    161 	cin >> t;
    162 	while (t--) {
    163 		int n, k;
    164 		cin >> n >> k;
    165 		vector<int> a(n);
    166 		for (auto &it : a) cin >> it;
    167 		vector<int> cnt(2 * k + 1);
    168 		for (int i = 0; i < n / 2; ++i) {
    169 			++cnt[a[i] + a[n - i - 1]];
    170 		}
    171 		vector<int> pref(2 * k + 2);
    172 		for (int i = 0; i < n / 2; ++i) {
    173 			int l1 = 1 + a[i], r1 = k + a[i];
    174 			int l2 = 1 + a[n - i - 1], r2 = k + a[n - i - 1];
    175 			assert(max(l1, l2) <= min(r1, r2));
    176 			++pref[min(l1, l2)];
    177 			--pref[max(r1, r2) + 1];
    178 		}
    179 		for (int i = 1; i <= 2 * k + 1; ++i) {
    180 			pref[i] += pref[i - 1];
    181 		}
    182 		int ans = 1e9;
    183 		for (int sum = 2; sum <= 2 * k; ++sum) {
    184 			ans = min(ans, (pref[sum] - cnt[sum]) + (n / 2 - pref[sum]) * 2);
    185 		}
    186 		cout << ans << endl;
    187 	}
    188 	
    189 	return 0;
    190 }
    191 ```
    192 
    193 [1343E - Weights Distributing](/contest/1343/problem/E "Codeforces Round 636 (Div. 3)")
    194 
    195 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    196 
    197 **Tutorial**
    198 
    199 Tutorial is loading...
    200 
    201 **Solution**
    202 
    203 ```
    204 #include <bits/stdc++.h>
    205 
    206 using namespace std;
    207 
    208 const int INF = 1e9;
    209 
    210 vector<vector<int>> g;
    211 
    212 void bfs(int s, vector<int> &d) {
    213 	d[s] = 0;
    214 	queue<int> q;
    215 	q.push(s);
    216 	while (!q.empty()) {
    217 		int v = q.front();
    218 		q.pop();
    219 		for (auto to : g[v]) {
    220 			if (d[to] == INF) {
    221 				d[to] = d[v] + 1;
    222 				q.push(to);
    223 			}
    224 		}
    225 	}
    226 }
    227 
    228 int main() {
    229 #ifdef _DEBUG
    230 	freopen("input.txt", "r", stdin);
    231 //	freopen("output.txt", "w", stdout);
    232 #endif
    233 	
    234 	int t;
    235 	cin >> t;
    236 	while (t--) {
    237 		int n, m, a, b, c;
    238 		cin >> n >> m >> a >> b >> c;
    239 		--a, --b, --c;
    240 		
    241 		vector<int> p(m);
    242 		for (auto &it : p) cin >> it;
    243 		sort(p.begin(), p.end());
    244 		vector<long long> pref(m + 1);
    245 		for (int i = 0; i < m; ++i) {
    246 			pref[i + 1] = pref[i] + p[i];
    247 		}
    248 		
    249 		g = vector<vector<int>>(n);
    250 		for (int i = 0; i < m; ++i) {
    251 			int x, y;
    252 			cin >> x >> y;
    253 			--x, --y;
    254 			g[x].push_back(y);
    255 			g[y].push_back(x);
    256 		}
    257 		
    258 		vector<int> da(n, INF), db(n, INF), dc(n, INF);
    259 		bfs(a, da);
    260 		bfs(b, db);
    261 		bfs(c, dc);
    262 		
    263 		long long ans = 1e18;
    264 		for (int i = 0; i < n; ++i) {
    265 			if (da[i] + db[i] + dc[i] > m) continue;
    266 			ans = min(ans, pref[db[i]] + pref[da[i] + db[i] + dc[i]]);
    267 		}
    268 		cout << ans << endl;
    269 	}
    270 	
    271 	return 0;
    272 }
    273 ```
    274 
    275 [1343F - Restore the Permutation by Sorted Segments](/contest/1343/problem/F "Codeforces Round 636 (Div. 3)")
    276 
    277 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    278 
    279 **Tutorial**
    280 
    281 Tutorial is loading...
    282 
    283 **Solution**
    284 
    285 ```
    286 #include <bits/stdc++.h>
    287 
    288 using namespace std;
    289 
    290 int main() {
    291 #ifdef _DEBUG
    292 	freopen("input.txt", "r", stdin);
    293 //	freopen("output.txt", "w", stdout);
    294 #endif
    295 	
    296 	int t;
    297 	cin >> t;
    298 	while (t--) {
    299 		int n;
    300 		cin >> n;
    301 		vector<set<int>> segs;
    302 		for (int i = 0; i < n - 1; ++i) {
    303 			set<int> cur;
    304 			int k;
    305 			cin >> k;
    306 			for (int j = 0; j < k; ++j) {
    307 				int x;
    308 				cin >> x;
    309 				cur.insert(x);
    310 			}
    311 			segs.push_back(cur);
    312 		}
    313 		for (int fst = 1; fst <= n; ++fst) {
    314 			vector<int> ans;
    315 			bool ok = true;
    316 			vector<set<int>> cur = segs;
    317 			for (auto &it : cur) if (it.count(fst)) it.erase(fst);
    318 			ans.push_back(fst);
    319 			for (int i = 1; i < n; ++i) {
    320 				int cnt1 = 0;
    321 				int nxt = -1;
    322 				for (auto  &it : cur) if (it.size() == 1) {
    323 					++cnt1;
    324 					nxt = *it.begin();
    325 				}
    326 				if (cnt1 != 1) {
    327 					ok = false;
    328 					break;
    329 				}
    330 				for (auto &it : cur) if (it.count(nxt)) it.erase(nxt);
    331 				ans.push_back(nxt);
    332 			}
    333 			if (ok) {
    334 				set<set<int>> all(segs.begin(), segs.end());
    335 				for (int i = 1; i < n; ++i) {
    336 					set<int> seg;
    337 					seg.insert(ans[i]);
    338 					bool found = false;
    339 					for (int j = i - 1; j >= 0; --j) {
    340 						seg.insert(ans[j]);
    341 						if (all.count(seg)) {
    342 							found = true;
    343 							all.erase(seg);
    344 							break;
    345 						}
    346 					}
    347 					if (!found) ok = false;
    348 				}
    349 			}
    350 			if (ok) {
    351 				for (auto it : ans) cout << it << " ";
    352 				cout << endl;
    353 				break;
    354 			}
    355 		}
    356 	}
    357 	
    358 	return 0;
    359 }
    360 ```