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 ```