1661.md (9276B)
1 Source: https://codeforces.com/blog/entry/101790 2 3 [1661A - Array Balancing](/contest/1661/problem/A "Educational Codeforces Round 126 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 import kotlin.math.abs 15 16 fun sum(a1: Int, a2: Int, b1: Int, b2: Int) = abs(a1 - a2) + abs(b1 - b2) 17 18 fun main() { 19 repeat(readLine()!!.toInt()) { 20 val n = readLine()!!.toInt() 21 val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray() 22 val b = readLine()!!.split(' ').map { it.toInt() }.toIntArray() 23 24 var sum = 0L 25 for (i in 1 until n) { 26 if (sum(a[i - 1], a[i], b[i - 1], b[i]) > sum(a[i - 1], b[i], b[i - 1], a[i])) 27 a[i] = b[i].also { b[i] = a[i] } 28 sum += sum(a[i - 1], a[i], b[i - 1], b[i]) 29 } 30 println(sum) 31 } 32 } 33 ``` 34 35 [1661B - Getting Zero](/contest/1661/problem/B "Educational Codeforces Round 126 (Rated for Div. 2)") 36 37 Idea: [adedalic](/profile/adedalic "International Master adedalic") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (adedalic)** 44 45 ``` 46 fun main() { 47 val n = readLine()!!.toInt() 48 val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray() 49 50 for (v in a) { 51 var ans = 20 52 for (cntAdd in 0..15) { 53 for (cntMul in 0..15) { 54 if (((v + cntAdd) shl cntMul) % 32768 == 0) 55 ans = minOf(ans, cntAdd + cntMul) 56 } 57 } 58 print("$ans ") 59 } 60 } 61 ``` 62 63 [1661C - Water the Trees](/contest/1661/problem/C "Educational Codeforces Round 126 (Rated for Div. 2)") 64 65 Idea: [vovuh](/profile/vovuh "Master vovuh") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution 1 (vovuh)** 72 73 ``` 74 #include <bits/stdc++.h> 75 76 using namespace std; 77 78 int main() { 79 #ifdef _DEBUG 80 freopen("input.txt", "r", stdin); 81 // freopen("output.txt", "w", stdout); 82 #endif 83 84 int tc; 85 scanf("%d", &tc); 86 while (tc--) { 87 int n; 88 scanf("%d", &n); 89 vector<int> h(n); 90 for (auto &it : h) { 91 scanf("%d", &it); 92 } 93 94 int mx = *max_element(h.begin(), h.end()); 95 long long ans = 1e18; 96 for (auto need : {mx, mx + 1}) { 97 long long l = 0, r = 1e18; 98 long long res = -1; 99 while (l <= r) { 100 long long mid = (l + r) >> 1; 101 long long cnt1 = (mid + 1) / 2, cnt2 = mid - cnt1; 102 long long need1 = 0; 103 for (auto ch : h) { 104 long long cur = (need - ch) / 2; 105 if ((need - ch) % 2 == 1) { 106 ++need1; 107 } 108 if (cnt2 >= cur) { 109 cnt2 -= cur; 110 } else { 111 cur -= cnt2; 112 cnt2 = 0; 113 need1 += cur * 2; 114 } 115 } 116 if (need1 <= cnt1) { 117 res = mid; 118 r = mid - 1; 119 } else { 120 l = mid + 1; 121 } 122 } 123 ans = min(ans, res); 124 } 125 126 printf("%lld\n", ans); 127 } 128 129 return 0; 130 } 131 ``` 132 133 **Solution 2 (awoo)** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 140 #define forn(i, n) for(int i = 0; i < int(n); i++) 141 142 int main(){ 143 int tc; 144 scanf("%d", &tc); 145 while (tc--) { 146 int n; 147 scanf("%d", &n); 148 vector<int> a(n); 149 forn(i, n) scanf("%d", &a[i]); 150 long long ans = 1e18; 151 int mx = *max_element(a.begin(), a.end()); 152 for (int x : {mx, mx + 1}){ 153 long long cnt1 = 0, cnt2 = 0; 154 forn(i, n){ 155 cnt2 += (x - a[i]) / 2; 156 cnt1 += (x - a[i]) % 2; 157 } 158 long long dif = max(0ll, cnt2 - cnt1 - 1) / 3; 159 cnt1 += dif * 2; 160 cnt2 -= dif; 161 ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2)); 162 if (cnt2 > 0){ 163 cnt1 += 2; 164 --cnt2; 165 ans = min(ans, max(cnt1 * 2 - 1, cnt2 * 2)); 166 } 167 } 168 printf("%lld\n", ans); 169 } 170 } 171 ``` 172 173 [1661D - Progressions Covering](/contest/1661/problem/D "Educational Codeforces Round 126 (Rated for Div. 2)") 174 175 Idea: [vovuh](/profile/vovuh "Master vovuh") 176 177 **Tutorial** 178 179 Tutorial is loading... 180 181 **Solution (vovuh)** 182 183 ``` 184 #include <bits/stdc++.h> 185 186 using namespace std; 187 188 int main() { 189 #ifdef _DEBUG 190 freopen("input.txt", "r", stdin); 191 // freopen("output.txt", "w", stdout); 192 #endif 193 194 int n, k; 195 scanf("%d %d", &n, &k); 196 vector<long long> b(n); 197 for (auto &it : b) { 198 scanf("%lld", &it); 199 } 200 201 vector<long long> closed(n); 202 long long sum = 0, cnt = 0, ans = 0; 203 for (int i = n - 1; i >= 0; --i) { 204 sum -= cnt; 205 cnt -= closed[i]; 206 b[i] -= sum; 207 if (b[i] <= 0) { 208 continue; 209 } 210 int el = min(i + 1, k); 211 long long need = (b[i] + el - 1) / el; 212 sum += need * el; 213 cnt += need; 214 ans += need; 215 if (i - el >= 0) { 216 closed[i - el] += need; 217 } 218 } 219 220 printf("%lld\n", ans); 221 222 return 0; 223 } 224 ``` 225 226 [1661E - Narrow Components](/contest/1661/problem/E "Educational Codeforces Round 126 (Rated for Div. 2)") 227 228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution (awoo)** 235 236 ``` 237 #include <bits/stdc++.h> 238 239 using namespace std; 240 241 #define forn(i, n) for(int i = 0; i < int(n); i++) 242 243 int main(){ 244 cin.tie(0); 245 iostream::sync_with_stdio(false); 246 int n; 247 cin >> n; 248 vector<string> s(3); 249 forn(i, 3) cin >> s[i]; 250 vector<int> pr(n + 1); 251 forn(i, n){ 252 pr[i + 1] += pr[i]; 253 forn(j, 3) pr[i + 1] += (s[j][i] == '1'); 254 } 255 256 vector<int> p(3 * n), rk(3 * n, 1); 257 iota(p.begin(), p.end(), 0); 258 function<int(int)> getp; 259 getp = [&](int a) -> int { 260 return a == p[a] ? a : p[a] = getp(p[a]); 261 }; 262 auto unite = [&](int a, int b) -> bool { 263 a = getp(a), b = getp(b); 264 if (a == b) return false; 265 if (rk[a] < rk[b]) swap(a, b); 266 p[b] = a; 267 rk[a] += rk[b]; 268 return true; 269 }; 270 271 vector<int> prhe(n + 1), prve(n + 1); 272 273 forn(j, n){ 274 forn(i, 2) if (s[i][j] == '1' && s[i + 1][j] == '1' && unite(i * n + j, (i + 1) * n + j)) 275 ++prve[j + 1]; 276 forn(i, 3) if (j > 0 && s[i][j] == '1' && s[i][j - 1] == '1' && unite(i * n + j, i * n + (j - 1))) 277 ++prhe[j]; 278 } 279 forn(i, n) prve[i + 1] += prve[i]; 280 forn(i, n) prhe[i + 1] += prhe[i]; 281 282 vector<int> nxt(n + 1, 0); 283 for (int i = n - 1; i >= 0; --i) 284 nxt[i] = (s[0][i] == '1' && s[1][i] == '0' && s[2][i] == '1' ? (nxt[i + 1] + 1) : 0); 285 286 int m; 287 cin >> m; 288 forn(_, m){ 289 int l, r; 290 cin >> l >> r; 291 --l, --r; 292 int non101 = l + nxt[l]; 293 if (non101 > r){ 294 cout << "2\n"; 295 continue; 296 } 297 int tot = pr[r + 1] - pr[non101]; 298 int in = (prve[r + 1] - prve[non101]) + (prhe[r] - prhe[non101]); 299 int res = tot - in; 300 if (non101 != l){ 301 if (s[0][non101] == '1' && s[1][non101] == '1' && s[2][non101] == '1'); 302 else if (s[0][non101] == '0' && s[2][non101] == '0') res += 2; 303 else ++res; 304 } 305 cout << res << "\n"; 306 } 307 308 return 0; 309 } 310 ``` 311 312 [1661F - Teleporters](/contest/1661/problem/F "Educational Codeforces Round 126 (Rated for Div. 2)") 313 314 Idea: [vovuh](/profile/vovuh "Master vovuh") 315 316 **Tutorial** 317 318 Tutorial is loading... 319 320 **Solution (BledDest)** 321 322 ``` 323 #include <bits/stdc++.h> 324 325 using namespace std; 326 327 int n; 328 vector<int> lens; 329 330 long long sqr(int x) 331 { 332 return x * 1ll * x; 333 } 334 335 long long eval_split(int len, int k) 336 { 337 return sqr(len / k) * (k - len % k) + sqr(len / k + 1) * (len % k); 338 } 339 340 pair<int, long long> eval_segment(int len, long long bound) 341 { 342 // only take options with value >= bound 343 if(bound <= 2 || len == 1) 344 return make_pair(len - 1, len); 345 int lf = 0; 346 int rg = len - 1; 347 while(rg - lf > 1) 348 { 349 int mid = (lf + rg) / 2; 350 if(eval_split(len, mid) - eval_split(len, mid + 1) >= bound) 351 lf = mid; 352 else 353 rg = mid; 354 } 355 return make_pair(lf, eval_split(len, lf + 1)); 356 } 357 358 pair<int, long long> eval_full(long long bound) 359 { 360 pair<int, long long> ans; 361 for(auto x : lens) 362 { 363 pair<int, long long> cur = eval_segment(x, bound); 364 ans.first += cur.first; 365 ans.second += cur.second; 366 } 367 return ans; 368 } 369 370 int main() 371 { 372 scanf("%d", &n); 373 int pr = 0; 374 for(int i = 0; i < n; i++) 375 { 376 int x; 377 scanf("%d", &x); 378 lens.push_back(x - pr); 379 pr = x; 380 } 381 long long w; 382 scanf("%lld", &w); 383 long long lf = 0ll; 384 long long rg = (long long)(1e18) + 43; 385 if(eval_full(rg).second <= w) 386 { 387 cout << 0 << endl; 388 return 0; 389 } 390 while(rg - lf > 1) 391 { 392 long long mid = (lf + rg) / 2; 393 pair<int, long long> res = eval_full(mid); 394 if(res.second <= w) 395 lf = mid; 396 else 397 rg = mid; 398 } 399 pair<int, long long> resL = eval_full(lf); 400 pair<int, long long> resR = eval_full(rg); 401 assert(resL.second <= w && resR.second > w); 402 long long change = (resR.second - resL.second) / (resR.first - resL.first); 403 cout << resL.first + (w - resL.second) / change << endl; 404 } 405 ```