codeforces-scrape

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

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