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