1520.md (8835B)
1 Source: https://codeforces.com/blog/entry/90342 2 3 [1520A - Do Not Be Distracted!](/contest/1520/problem/A "Codeforces Round 719 (Div. 3)") 4 5 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 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 using ll = long long; 19 using ld = long double; 20 using pii = pair<int, int>; 21 using cd = complex<ld>; 22 23 void solve() { 24 int n; 25 cin >> n; 26 string s; 27 cin >> s; 28 for (char c = 'A'; c <= 'Z'; c++) { 29 int first = n; 30 int last = -1; 31 for (int i = 0; i < n; i++) { 32 if (s[i] == c) { 33 first = min(first, i); 34 last = max(last, i); 35 } 36 } 37 for (int i = first; i <= last; i++) { 38 if (s[i] != c) { 39 cout << "NO\n"; 40 return; 41 } 42 } 43 } 44 cout << "YES\n"; 45 } 46 47 int main() { 48 ios_base::sync_with_stdio(false); 49 cin.tie(nullptr); 50 int t; 51 cin >> t; 52 while (t--) { 53 solve(); 54 } 55 } 56 ``` 57 58 [1520B - Ordinary Numbers](/contest/1520/problem/B "Codeforces Round 719 (Div. 3)") 59 60 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 61 62 **Tutorial** 63 64 Tutorial is loading... 65 66 **Solution** 67 68 ``` 69 #include <bits/stdc++.h> 70 using namespace std; 71 72 using ll = long long; 73 74 void solve() { 75 int n; 76 cin >> n; 77 int res = 0; 78 for (ll pw = 1; pw <= n; pw = pw * 10 + 1) { 79 for (int d = 1; d <= 9; d++) { 80 if (pw * d <= n) { 81 res++; 82 } 83 } 84 } 85 cout << res << endl; 86 } 87 88 int main() { 89 int tests; 90 cin >> tests; 91 while (tests-- > 0) { 92 solve(); 93 } 94 return 0; 95 } 96 ``` 97 98 [1520C - Not Adjacent Matrix](/contest/1520/problem/C "Codeforces Round 719 (Div. 3)") 99 100 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 101 102 **Tutorial** 103 104 Tutorial is loading... 105 106 **Solution** 107 108 ``` 109 #include <bits/stdc++.h> 110 using namespace std; 111 112 void solve() { 113 int n; 114 cin >> n; 115 if (n == 1) { 116 cout << "1" << endl; 117 return; 118 } else if (n == 2) { 119 cout << "-1" << endl; 120 return; 121 } 122 vector<vector<int>> a(n, vector<int>(n)); 123 a[0][0] = 1; 124 a[n - 1][n - 1] = n * n; 125 int x = n * n - 1; 126 for (int i = 1; i + 1 < n; i++) { 127 for (int j = i; j >= 0; j--, x--) { 128 a[i - j][j] = x; 129 } 130 } 131 x = 2; 132 for (int j = n - 2; j > 0; j--) { 133 for (int i = 0; i < n - j; i++, x++) { 134 a[n - i - 1][j + i] = x; 135 } 136 } 137 for (int i = n - 1; i >= 0; i--, x++) { 138 a[i][n - i - 1] = x; 139 } 140 for (int i = 0; i < n; i++) { 141 for (int j = 0; j < n; j++) { 142 cout << a[i][j] << " "; 143 } 144 cout << endl; 145 } 146 } 147 148 int main() { 149 int tests; 150 cin >> tests; 151 while (tests-- > 0) { 152 solve(); 153 } 154 return 0; 155 } 156 ``` 157 158 [1520D - Same Differences](/contest/1520/problem/D "Codeforces Round 719 (Div. 3)") 159 160 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution** 167 168 ``` 169 #include <bits/stdc++.h> 170 using namespace std; 171 172 void solve() { 173 int n; 174 cin >> n; 175 map<int, int> a; 176 long long res = 0; 177 for (int i = 0; i < n; i++) { 178 int x; 179 cin >> x; 180 x -= i; 181 res += a[x]; 182 a[x]++; 183 } 184 cout << res << endl; 185 } 186 187 int main() { 188 int tests; 189 cin >> tests; 190 while (tests-- > 0) { 191 solve(); 192 } 193 return 0; 194 } 195 ``` 196 197 [1520E - Arranging The Sheep](/contest/1520/problem/E "Codeforces Round 719 (Div. 3)") 198 199 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution** 206 207 ``` 208 #include<bits/stdc++.h> 209 210 using namespace std; 211 212 void solve() 213 { 214 int n; 215 cin >> n; 216 string s; 217 cin >> s; 218 int cnt = 0; 219 for(auto x : s) 220 cnt += (x == '*' ? 1 : 0); 221 int pos = -1; 222 int cur = -1; 223 for(int i = 0; i < n; i++) 224 { 225 if(s[i] == '*') 226 { 227 cur++; 228 if(cur == cnt / 2) 229 pos = i; 230 } 231 } 232 long long ans = 0; 233 cur = pos - cnt / 2; 234 for(int i = 0; i < n; i++) 235 if(s[i] == '*') 236 { 237 ans += abs(cur - i); 238 cur++; 239 } 240 cout << ans << endl; 241 } 242 243 int main() 244 { 245 ios_base::sync_with_stdio(0); 246 cin.tie(0); 247 int tc = 1; 248 cin >> tc; 249 for(int i = 0; i < tc; i++) 250 { 251 solve(); 252 } 253 } 254 ``` 255 256 [1520F1 - Guess the K-th Zero (Easy version)](/contest/1520/problem/F1 "Codeforces Round 719 (Div. 3)") 257 258 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly") 259 260 **Tutorial** 261 262 Tutorial is loading... 263 264 **Solution** 265 266 ``` 267 #include <bits/stdc++.h> 268 269 using namespace std; 270 271 using ll = long long; 272 using ld = long double; 273 using pii = pair<int, int>; 274 using cd = complex<ld>; 275 276 void calc(int l, int r, int k) { 277 if (l == r) { 278 cout << "! " << l << endl; 279 return; 280 } 281 int m = (l + r) / 2; 282 cout << "? " << l << " " << m << endl; 283 int sum; 284 cin >> sum; 285 if ((m - l + 1) - sum >= k) { 286 calc(l, m, k); 287 } else { 288 calc(m + 1, r, k - (m - l + 1) + sum); 289 } 290 } 291 292 int main() { 293 ios_base::sync_with_stdio(false); 294 cin.tie(nullptr); 295 int n, t, k; 296 cin >> n >> t >> k; 297 calc(1, n, k); 298 } 299 ``` 300 301 [1520F2 - Guess the K-th Zero (Hard version)](/contest/1520/problem/F2 "Codeforces Round 719 (Div. 3)") 302 303 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 304 305 **Tutorial** 306 307 Tutorial is loading... 308 309 **Solution** 310 311 ``` 312 #include <bits/stdc++.h> 313 314 using namespace std; 315 316 #define forn(i, n) for (int i = 0; i < int(n); i++) 317 318 map<pair<int,int>, int> cache; 319 320 void dec(int pos, int L, int R) { 321 cache[{L, R}]--; 322 323 if (L != R) { 324 int M = (L + R) / 2; 325 if (pos <= M) 326 dec(pos, L, M); 327 else 328 dec(pos, M + 1, R); 329 } 330 } 331 332 int main() { 333 int n, cases; 334 cin >> n >> cases; 335 forn(case_, cases) { 336 int k; 337 cin >> k; 338 int L = 0, R = n - 1; 339 while (L != R) { 340 int M = (L + R) / 2; 341 342 pair<int,int> range = make_pair(L, M); 343 if (cache.count(range) == 0) { 344 cout << "? " << range.first + 1 << " " << range.second + 1 << endl; 345 cin >> cache[range]; 346 cache[range] = range.second - range.first + 1 - cache[range]; 347 } 348 349 int value = cache[range]; 350 if (k <= value) 351 R = M; 352 else { 353 k -= value; 354 L = M + 1; 355 } 356 } 357 358 cout << "! " << L + 1 << endl; 359 dec(L, 0, n - 1); 360 } 361 } 362 ``` 363 364 [1520G - To Go Or Not To Go?](/contest/1520/problem/G "Codeforces Round 719 (Div. 3)") 365 366 Authors: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly"), [Aris](/profile/Aris "Candidate Master Aris") 367 368 **Tutorial** 369 370 Tutorial is loading... 371 372 **Solution** 373 374 ``` 375 #include <bits/stdc++.h> 376 377 using namespace std; 378 379 using ll = long long; 380 using ld = long double; 381 using pii = pair<int, int>; 382 using cd = complex<ld>; 383 384 const int MAX_N = 2010; 385 386 int dd[4][2] = { 387 {1, 0}, 388 {0, 1}, 389 {-1, 0}, 390 {0, -1} 391 }; 392 393 void bfs(int sx, int sy, vector<vector<int>> &d, vector<vector<int>> &a) { 394 int n = d.size(); 395 int m = d[0].size(); 396 queue<pair<int, int>> q; 397 q.push({sx, sy}); 398 d[sx][sy] = 1; 399 while (!q.empty()) { 400 auto [x, y] = q.front(); 401 q.pop(); 402 for (auto [dx, dy] : dd) { 403 int tx = x + dx; 404 int ty = y + dy; 405 if (tx >= 0 && ty >= 0 && tx < n && ty < m && d[tx][ty] == 0 && a[tx][ty] != -1) { 406 d[tx][ty] = d[x][y] + 1; 407 q.push({tx, ty}); 408 } 409 } 410 } 411 for (auto &e : d) { 412 for (auto &i : e) { 413 i--; 414 } 415 } 416 } 417 418 int main() { 419 ios_base::sync_with_stdio(false); 420 cin.tie(nullptr); 421 int n, m, w; 422 cin >> n >> m >> w; 423 vector<vector<int>> a(n, vector<int>(m)); 424 vector<vector<int>> d1(n, vector<int>(m)); 425 vector<vector<int>> d2(n, vector<int>(m)); 426 for (int i = 0; i < n; i++) { 427 for (int j = 0; j < m; j++) { 428 cin >> a[i][j]; 429 } 430 } 431 bfs(0, 0, d1, a); 432 bfs(n - 1, m - 1, d2, a); 433 ll bestFinish = 1e18; 434 for (int i = 0; i < n; i++) { 435 for (int j = 0; j < m; j++) { 436 if (d2[i][j] != -1 && a[i][j] >= 1) { 437 bestFinish = min(bestFinish, a[i][j] + w * 1ll * d2[i][j]); 438 } 439 } 440 } 441 ll ans = w * 1ll * d1[n - 1][m - 1]; 442 if (d1[n - 1][m - 1] == -1) { 443 ans = 1e18; 444 } 445 for (int i = 0; i < n; i++) { 446 for (int j = 0; j < m; j++) { 447 if (d1[i][j] != -1 && a[i][j] >= 1 && bestFinish != 1e18) { 448 ans = min(ans, w * 1ll * d1[i][j] + a[i][j] + bestFinish); 449 } 450 } 451 } 452 if (ans == 1e18) { 453 cout << -1; 454 } else { 455 cout << ans; 456 } 457 } 458 ```