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