codeforces-scrape

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

1066.md (6927B)


      1 Source: https://codeforces.com/blog/entry/62419
      2 
      3 [1066A - Vova and Train](/contest/1066/problem/A "Codeforces Round 515 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int t;
     23 	cin >> t;
     24 	
     25 	for (int i = 0; i < t; ++i) {	
     26 		int L, v, l, r;
     27 		cin >> L >> v >> l >> r;
     28 		cout << L / v - r / v + (l - 1) / v << endl;
     29 	}
     30 	
     31 	return 0;
     32 }
     33 ```
     34 
     35 [1066B - Heaters](/contest/1066/problem/B "Codeforces Round 515 (Div. 3)")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution 1**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 int main() {
     49 #ifdef _DEBUG
     50 	freopen("input.txt", "r", stdin);
     51 //	freopen("output.txt", "w", stdout);
     52 #endif
     53 	
     54 	int n, r;
     55 	cin >> n >> r;
     56 	vector<int> a(n);
     57 	for (int i = 0; i < n; ++i) {
     58 		cin >> a[i];
     59 	}
     60 	
     61 	int ans = 0;
     62 	int last = -1;
     63 	while (last < n - 1) {
     64 		int pos = -1;
     65 		for (int i = n - 1; i > max(-1, last - r + 1); --i) {
     66 			if (a[i] == 1 && i - r <= last) {
     67 				pos = i;
     68 				break;
     69 			}
     70 		}
     71 		if (pos == -1) {
     72 			cout << -1 << "\n";
     73 			return 0;
     74 		}
     75 		++ans;
     76 		last = pos + r - 1;
     77 	}
     78 	
     79 	cout << ans << "\n";
     80 	
     81 	return 0;
     82 }
     83 ```
     84 
     85 **Solution 2**
     86 
     87 ```
     88 #include <vector>
     89 #include <iostream>
     90 
     91 #define forn(i,n) for (int i=0; i<int(n); i++)
     92 
     93 using namespace std;
     94 
     95 const int N = 2e5;
     96 
     97 int main()
     98 {
     99 	ios_base::sync_with_stdio(false);
    100 	cin.tie(nullptr);
    101 	int n, r; cin >> n >> r;
    102 	vector<int> a(n);
    103 	vector<int> cnt(n);
    104 	int ans = 0;
    105 	forn(i, n)
    106         {
    107             cin >> a[i];
    108             if (a[i])ans++;
    109             if (a[i])
    110                 for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
    111                     cnt[j]++;
    112         }
    113     forn(i, n)
    114         if (!cnt[i])
    115         {
    116             cout << -1;
    117             return 0;
    118         }
    119     forn(i, n)
    120     {
    121         bool fl = true;
    122         if (a[i])
    123             for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
    124                 if (cnt[j] == 1)
    125                 {
    126                     fl = false;
    127                     break;
    128                 }
    129         if (fl && a[i])
    130         {
    131             ans--;
    132             for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
    133                 cnt[j]--;
    134         }
    135     }
    136     cout << ans;
    137 
    138 }
    139 ```
    140 
    141 [1066C - Books Queries](/contest/1066/problem/C "Codeforces Round 515 (Div. 3)")
    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 const int M = 200 * 1000 + 11;
    155 
    156 int main() {
    157 #ifdef _DEBUG
    158 	freopen("input.txt", "r", stdin);
    159 //	freopen("output.txt", "w", stdout);
    160 #endif
    161 	
    162 	int q;
    163 	cin >> q;
    164 	
    165 	vector<int> pos(M);
    166 	int curl = 0;
    167 	int curr = 0;
    168 	
    169 	for (int i = 0; i < q; ++i) {
    170 		string type;
    171 		int id;
    172 		cin >> type >> id;
    173 		if (i == 0) {
    174 			pos[id] = curl;
    175 			--curl;
    176 			++curr;
    177 		} else {
    178 			if (type == "L") {
    179 				pos[id] = curl;
    180 				--curl;
    181 			} else if (type == "R") {
    182 				pos[id] = curr;
    183 				++curr;
    184 			} else {
    185 				cout << min(abs(pos[id] - curl), abs(pos[id] - curr)) - 1 << "\n";
    186 			}
    187 		}
    188 	}
    189 	
    190 	return 0;
    191 }
    192 ```
    193 
    194 [1066D - Boxes Packing](/contest/1066/problem/D "Codeforces Round 515 (Div. 3)")
    195 
    196 **Tutorial**
    197 
    198 Tutorial is loading...
    199 
    200 **Solution 1**
    201 
    202 ```
    203 #include <bits/stdc++.h>
    204 using namespace std;
    205 
    206 const int MAX = 2e5 + 10;
    207 
    208 int ar[MAX];
    209 int n, m, k;
    210 
    211 int find(int pos){
    212     int ans = n - pos + 1;
    213     int used = 0;
    214     while(used < m && pos <= n){
    215         int t = k;
    216         while(pos <= n && ar[pos] <= t){
    217             t -= ar[pos++];
    218         }
    219         used++;
    220     }
    221     return pos == n + 1 ? ans : 0;
    222 }
    223 
    224 int main(){
    225     ios_base::sync_with_stdio(0);
    226     cin.tie(0);
    227     cout.tie(0);
    228     cin >> n >> m >> k;
    229     for(int i = 1; i <= n; i++){
    230         cin >> ar[i];
    231     }
    232     int ans = 0;
    233     int l = 1, r = n;
    234     while(l <= r){
    235         int x = (l + r) >> 1;
    236         if(find(x)){
    237             ans = max(ans, n - x + 1);
    238             r = x - 1;
    239         }else{
    240             l = x + 1;
    241         }
    242     }
    243     cout << ans << endl;
    244 }
    245 ```
    246 
    247 **Solution 2**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251 
    252 using namespace std;
    253 
    254 int main() {
    255 #ifdef _DEBUG
    256 	freopen("input.txt", "r", stdin);
    257 //	freopen("output.txt", "w", stdout);
    258 #endif
    259 	
    260 	int n, m, k;
    261 	cin >> n >> m >> k;
    262 	vector<int> a(n);
    263 	for (int i = 0; i < n; ++i) {
    264 		cin >> a[i];
    265 	}
    266 	
    267 	reverse(a.begin(), a.end());
    268 	int rem = 0;
    269 	for (int i = 0; i < n; ++i) {
    270 		if (rem - a[i] < 0) {
    271 			if (m == 0) {
    272 				cout << i << endl;
    273 				return 0;
    274 			} else {
    275 				--m;
    276 				rem = k - a[i];
    277 			}
    278 		} else {
    279 			rem -= a[i];
    280 		}
    281 	}
    282 	
    283 	cout << n << endl;
    284 	
    285 	return 0;
    286 }
    287 ```
    288 
    289 [1066E - Binary Numbers AND Sum](/contest/1066/problem/E "Codeforces Round 515 (Div. 3)")
    290 
    291 **Tutorial**
    292 
    293 Tutorial is loading...
    294 
    295 **Solution**
    296 
    297 ```
    298 #include <bits/stdc++.h>
    299 
    300 using namespace std;
    301 
    302 const int MOD = 998244353;
    303 
    304 int add(int a, int b) {
    305 	a += b;
    306 	if (a < 0) a += MOD;
    307 	if (a >= MOD) a -= MOD;
    308 	return a;
    309 }
    310 
    311 int main() {
    312 #ifdef _DEBUG
    313 	freopen("input.txt", "r", stdin);
    314 //	freopen("output.txt", "w", stdout);
    315 #endif
    316 	
    317 	int n, m;
    318 	cin >> n >> m;
    319 	string s, t;
    320 	cin >> s >> t;
    321 	
    322 	int pw = 1;
    323 	int res = 0;
    324 	int ans = 0;
    325 	
    326 	for (int i = 0; i < m; ++i) {
    327 		if (i < n && s[n - i - 1] == '1') {
    328 			res = add(res, pw);
    329 		}
    330 		if (t[m - i - 1] == '1') {
    331 			ans = add(ans, res);
    332 		}
    333 		pw = add(pw, pw);
    334 	}
    335 	
    336 	cout << ans << endl;
    337 	
    338 	return 0;
    339 }
    340 ```
    341 
    342 [1066F - Yet another 2D Walking](/contest/1066/problem/F "Codeforces Round 515 (Div. 3)")
    343 
    344 **Tutorial**
    345 
    346 Tutorial is loading...
    347 
    348 **Solution**
    349 
    350 ```
    351 #include <bits/stdc++.h>
    352 
    353 using namespace std;
    354 
    355 const long long INF64 = 1e18;
    356 
    357 long long dist(pair<int, int> a, pair<int, int> b) {
    358 	return abs(a.first - b.first) + abs(a.second - b.second);
    359 }
    360 
    361 int main() {
    362 #ifdef _DEBUG
    363 	freopen("input.txt", "r", stdin);
    364 //	freopen("output.txt", "w", stdout);
    365 #endif
    366 	
    367 	int n;
    368 	map<int, vector<pair<int, int>>> pts;
    369 	cin >> n;
    370 	for (int i = 0; i < n; ++i) {
    371 		int x, y;
    372 		cin >> x >> y;
    373 		pts[max(x, y)].push_back(make_pair(x, y));
    374 	}
    375 	pts[0].push_back(make_pair(0, 0));
    376 	
    377 	for (auto &it : pts) {
    378 		sort(it.second.begin(), it.second.end(), [&](pair<int, int> a, pair<int, int> &b) {
    379 			if (a.first == b.first)
    380 				return a.second > b.second;
    381 			return a.first < b.first;
    382 		});
    383 	}
    384 	
    385 	vector<vector<long long>> dp(int(pts.size()) + 1, vector<long long>(2, INF64));
    386 	dp[0][0] = dp[0][1] = 0;
    387 	
    388 	int lvl = 0;
    389 	int prv = 0;
    390 	for (auto &it : pts) {
    391 		++lvl;
    392 		
    393 		pair<int, int> curl = it.second[0];
    394 		pair<int, int> curr = it.second.back();
    395 		
    396 		pair<int, int> prvl = pts[prv][0];
    397 		pair<int, int> prvr = pts[prv].back();
    398 		
    399 		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][0] + dist(prvl, curr) + dist(curl, curr));
    400 		dp[lvl][0] = min(dp[lvl][0], dp[lvl - 1][1] + dist(prvr, curr) + dist(curl, curr));
    401 		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][0] + dist(prvl, curl) + dist(curl, curr));
    402 		dp[lvl][1] = min(dp[lvl][1], dp[lvl - 1][1] + dist(prvr, curl) + dist(curl, curr));
    403 		
    404 		prv = it.first;
    405 	}
    406 	
    407 	cout << min(dp[lvl][0], dp[lvl][1]) << endl;
    408 	
    409 	return 0;
    410 }
    411 ```