1015.md (9262B)
1 Source: https://codeforces.com/blog/entry/60949 2 3 [1015A - Points in Segments](/contest/1015/problem/A "Codeforces Round 501 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh, O(n + m))** 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 n, m; 23 cin >> n >> m; 24 vector<int> cnt(m + 2); 25 for (int i = 0; i < n; ++i) { 26 int l, r; 27 cin >> l >> r; 28 ++cnt[l]; 29 --cnt[r + 1]; 30 } 31 for (int i = 1; i <= m; ++i) 32 cnt[i] += cnt[i - 1]; 33 34 vector<int> ans; 35 for (int i = 1; i <= m; ++i) { 36 if (cnt[i] == 0) 37 ans.push_back(i); 38 } 39 40 cout << ans.size() << endl; 41 for (auto it : ans) cout << it << " "; 42 cout << endl; 43 44 return 0; 45 } 46 ``` 47 48 **Solution (Vovuh, O(n * m))** 49 50 ``` 51 n, m = map(int, input().split()) 52 seg = [list(map(int, input().split())) for i in range(n)] 53 def bad(x): 54 for i in range(n): 55 if (seg[i][0] <= x and x <= seg[i][1]): return False 56 return True 57 ans = list(filter(bad, [i for i in range(1, m + 1)])) 58 print(len(ans)) 59 print(' '.join([str(x) for x in ans])) 60 ``` 61 62 [1015B - Obtaining the String](/contest/1015/problem/B "Codeforces Round 501 (Div. 3)") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (Vovuh)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 using namespace std; 74 75 int main() { 76 #ifdef _DEBUG 77 freopen("input.txt", "r", stdin); 78 // freopen("output.txt", "w", stdout); 79 #endif 80 81 int n; 82 string s, t; 83 cin >> n >> s >> t; 84 85 vector<int> ans; 86 for (int i = 0; i < n; ++i) { 87 if (s[i] == t[i]) continue; 88 int pos = -1; 89 for (int j = i + 1; j < n; ++j) { 90 if (s[j] == t[i]) { 91 pos = j; 92 break; 93 } 94 } 95 if (pos == -1) { 96 cout << -1 << endl; 97 return 0; 98 } 99 for (int j = pos - 1; j >= i; --j) { 100 swap(s[j], s[j + 1]); 101 ans.push_back(j); 102 } 103 } 104 105 assert(s == t); 106 107 cout << ans.size() << endl; 108 for (auto it : ans) cout << it + 1 << " "; 109 cout << endl; 110 111 return 0; 112 } 113 ``` 114 115 [1015C - Songs Compression](/contest/1015/problem/C "Codeforces Round 501 (Div. 3)") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution (Vovuh)** 122 123 ``` 124 #include <bits/stdc++.h> 125 126 using namespace std; 127 128 int main() { 129 #ifdef _DEBUG 130 freopen("input.txt", "r", stdin); 131 // freopen("output.txt", "w", stdout); 132 #endif 133 134 int n, m; 135 cin >> n >> m; 136 vector<pair<int, int>> a(n); 137 long long sum = 0; 138 for (int i = 0; i < n; ++i) { 139 cin >> a[i].first >> a[i].second; 140 sum += a[i].first; 141 } 142 143 sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b) { return a.first - a.second > b.first - b.second; }); 144 145 for (int i = 0; i < n; ++i) { 146 if (sum <= m) { 147 cout << i << endl; 148 return 0; 149 } 150 sum -= a[i].first - a[i].second; 151 } 152 153 if (sum <= m) 154 cout << n << endl; 155 else 156 cout << -1 << endl; 157 158 return 0; 159 } 160 ``` 161 162 [1015D - Walking Between Houses](/contest/1015/problem/D "Codeforces Round 501 (Div. 3)") 163 164 **Tutorial** 165 166 Tutorial is loading... 167 168 **Solution (BledDest)** 169 170 ``` 171 def step(cur, x): 172 if(cur - x > 0): 173 return cur - x 174 else: 175 return cur + x 176 177 n, k, s = map(int, input().split()) 178 cur = 1 179 180 if(k > s or k * (n - 1) < s): 181 print('NO') 182 else: 183 print('YES') 184 while(k > 0): 185 l = min(n - 1, s - (k - 1)) 186 cur = step(cur, l) 187 print(cur, end = ' ') 188 s -= l 189 k -= 1 190 ``` 191 192 [1015E1 - Stars Drawing (Easy Edition)](/contest/1015/problem/E1 "Codeforces Round 501 (Div. 3)") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution (MikeMirzayanov, O(n^3))** 199 200 ``` 201 #include <bits/stdc++.h> 202 203 using namespace std; 204 205 #define forn(i, n) for (int i = 0; i < int(n); i++) 206 207 const int dx[] = {1, 0, -1, 0}; 208 const int dy[] = {0, 1, 0, -1}; 209 const int N = 1001; 210 211 int n, m; 212 vector<string> f; 213 int d[N][N][4]; 214 int r[N][N], a[N][N], b[N][N]; 215 216 int getd(int i, int j, int k) { 217 int dxk = dx[k]; 218 int dyk = dy[k]; 219 int result = 0; 220 while (i >= 0 && i < n && j >= 0 && j < m && f[i][j] == '*') 221 result++, i += dxk, j += dyk; 222 return result; 223 } 224 225 int main() { 226 cin >> n >> m; 227 f = vector<string>(n); 228 forn(i, n) 229 cin >> f[i]; 230 231 memset(d, -1, sizeof(d)); 232 int result = 0; 233 for (int i = 1; i + 1 < n; i++) 234 for (int j = 1; j + 1 < m; j++) 235 if (f[i][j] == '*') { 236 bool around = true; 237 forn(k, 4) 238 around = around && (f[i + dx[k]][j + dy[k]] == '*'); 239 if (around) { 240 r[i][j] = INT_MAX; 241 forn(k, 4) 242 r[i][j] = min(r[i][j], getd(i, j, k) - 1); 243 result++; 244 a[i][j - r[i][j]] = max(a[i][j - r[i][j]], 2 * r[i][j] + 1); 245 b[i - r[i][j]][j] = max(b[i - r[i][j]][j], 2 * r[i][j] + 1); 246 } 247 } 248 249 vector<string> g(n, string(m, '.')); 250 forn(i, n) { 251 int v = 0; 252 forn(j, m) { 253 v = max(v - 1, a[i][j]); 254 if (v > 0) 255 g[i][j] = '*'; 256 } 257 } 258 forn(j, m) { 259 int v = 0; 260 forn(i, n) { 261 v = max(v - 1, b[i][j]); 262 if (v > 0) 263 g[i][j] = '*'; 264 } 265 } 266 267 if (f == g) { 268 cout << result << endl; 269 forn(i, n) 270 forn(j, m) 271 if (r[i][j] > 0) 272 cout << i + 1 << " " << j + 1 << " " << r[i][j] << endl; 273 } else 274 cout << -1 << endl; 275 } 276 ``` 277 278 [1015E2 - Stars Drawing (Hard Edition)](/contest/1015/problem/E2 "Codeforces Round 501 (Div. 3)") 279 280 **Tutorial** 281 282 Tutorial is loading... 283 284 **Solution (Vovuh, O(n^2))** 285 286 ``` 287 #include <bits/stdc++.h> 288 289 using namespace std; 290 291 int n, m; 292 vector<string> s; 293 294 vector<string> draw(const vector<pair<pair<int, int>, int>> &r) { 295 vector<string> f(n, string(m, '.')); 296 vector<vector<int>> h(n, vector<int>(m)); 297 vector<vector<int>> v(n, vector<int>(m)); 298 for (auto it : r) { 299 int x = it.first.first; 300 int y = it.first.second; 301 int len = it.second; 302 ++v[x - len][y]; 303 if (x + len + 1 < n) 304 --v[x + len + 1][y]; 305 ++h[x][y - len]; 306 if (y + len + 1 < m) 307 --h[x][y + len + 1]; 308 } 309 for (int i = 0; i < n; ++i) { 310 for (int j = 0; j < m; ++j) { 311 if (i > 0) v[i][j] += v[i - 1][j]; 312 if (j > 0) h[i][j] += h[i][j - 1]; 313 if (v[i][j] > 0 || h[i][j] > 0) 314 f[i][j] = '*'; 315 } 316 } 317 return f; 318 } 319 320 int main() { 321 #ifdef _DEBUG 322 freopen("input.txt", "r", stdin); 323 // freopen("output.txt", "w", stdout); 324 #endif 325 326 cin >> n >> m; 327 s = vector<string>(n); 328 for (int i = 0; i < n; ++i) { 329 cin >> s[i]; 330 } 331 332 vector<vector<int>> l(n, vector<int>(m)); 333 vector<vector<int>> r(n, vector<int>(m)); 334 vector<vector<int>> u(n, vector<int>(m)); 335 vector<vector<int>> d(n, vector<int>(m)); 336 337 for (int i = 0; i < n; ++i) { 338 for (int j = 0; j < m; ++j) { 339 if (i > 0) { 340 if (s[i][j] != '.') 341 u[i][j] = u[i - 1][j] + 1; 342 } else { 343 u[i][j] = s[i][j] != '.'; 344 } 345 if (j > 0) { 346 if (s[i][j] != '.') 347 l[i][j] = l[i][j - 1] + 1; 348 } else { 349 l[i][j] = s[i][j] != '.'; 350 } 351 } 352 } 353 for (int i = n - 1; i >= 0; --i) { 354 for (int j = m - 1; j >= 0; --j) { 355 if (i < n - 1) { 356 if (s[i][j] != '.') 357 d[i][j] = d[i + 1][j] + 1; 358 } else { 359 d[i][j] = s[i][j] != '.'; 360 } 361 if (j < m - 1) { 362 if (s[i][j] != '.') 363 r[i][j] = r[i][j + 1] + 1; 364 } else { 365 r[i][j] = s[i][j] != '.'; 366 } 367 } 368 } 369 370 vector<pair<pair<int, int>, int>> ans; 371 for (int i = 0; i < n; ++i) { 372 for (int j = 0; j < m; ++j) { 373 if (s[i][j] == '*') { 374 int len = min(min(u[i][j], l[i][j]), min(d[i][j], r[i][j])) - 1; 375 if (len != 0) { 376 ans.push_back(make_pair(make_pair(i, j), len)); 377 } 378 } 379 } 380 } 381 382 if (draw(ans) != s) { 383 cout << -1 << endl; 384 } else { 385 cout << ans.size() << endl; 386 for (auto it : ans) { 387 cout << it.first.first + 1 << " " << it.first.second + 1 << " " << it.second << endl; 388 } 389 } 390 391 return 0; 392 } 393 ``` 394 395 [1015F - Bracket Substring](/contest/1015/problem/F "Codeforces Round 501 (Div. 3)") 396 397 **Tutorial** 398 399 Tutorial is loading... 400 401 **Solution (Vovuh)** 402 403 ``` 404 #include <bits/stdc++.h> 405 406 using namespace std; 407 408 const int N = 203; 409 const int MOD = 1e9 + 7; 410 411 int n, ssz; 412 string s; 413 int len[N][2]; 414 int dp[N][N][N][2]; 415 416 int calc(const string &t) { 417 int tsz = t.size(); 418 for (int i = tsz; i > 0; --i) { 419 if (s.substr(0, i) == t.substr(tsz - i, i)) 420 return i; 421 } 422 return 0; 423 } 424 425 void add(int &a, int b) { 426 a += b; 427 if (a >= MOD) 428 a -= MOD; 429 if (a < 0) 430 a += MOD; 431 } 432 433 int main() { 434 #ifdef _DEBUG 435 freopen("input.txt", "r", stdin); 436 // freopen("output.txt", "w", stdout); 437 #endif 438 439 cin >> n >> s; 440 ssz = s.size(); 441 442 if (s[0] == '(') 443 len[0][0] = 1; 444 else 445 len[0][1] = 1; 446 447 string pref; 448 for (int i = 0; i < ssz; ++i) { 449 pref += s[i]; 450 pref += '('; 451 len[i + 1][0] = calc(pref); 452 pref.pop_back(); 453 pref += ')'; 454 len[i + 1][1] = calc(pref); 455 pref.pop_back(); 456 } 457 458 dp[0][0][0][0] = 1; 459 for (int i = 0; i < 2 * n; ++i) { 460 for (int j = 0; j <= n; ++j) { 461 for (int pos = 0; pos <= ssz; ++pos) { 462 for (int f = 0; f < 2; ++f) { 463 if (dp[i][j][pos][f] == 0) continue; 464 if (j + 1 <= n) 465 add(dp[i + 1][j + 1][len[pos][0]][f | (len[pos][0] == ssz)], dp[i][j][pos][f]); 466 if (j > 0) 467 add(dp[i + 1][j - 1][len[pos][1]][f | (len[pos][1] == ssz)], dp[i][j][pos][f]); 468 } 469 } 470 } 471 } 472 473 int ans = 0; 474 for (int i = 0; i <= ssz; ++i) 475 add(ans, dp[2 * n][0][i][1]); 476 477 cout << ans << endl; 478 479 return 0; 480 } 481 ```