1203.md (7282B)
1 Source: https://codeforces.com/blog/entry/69108 2 3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 4 5 [1203A - Circle of Students](/contest/1203/problem/A "Codeforces Round 579 (Div. 3)") 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 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int q; 25 cin >> q; 26 for (int i = 0; i < q; ++i) { 27 int n; 28 cin >> n; 29 vector<int> a(n); 30 int pos = -1; 31 for (int j = 0; j < n; ++j) { 32 cin >> a[j]; 33 if (a[j] == 1) pos = j; 34 } 35 bool okl = true, okr = true; 36 for (int j = 1; j < n; ++j) { 37 okl &= (a[(pos - j + n) % n] == j + 1); 38 okr &= (a[(pos + j + n) % n] == j + 1); 39 } 40 if (okl || okr) cout << "YES" << endl; 41 else cout << "NO" << endl; 42 } 43 44 return 0; 45 } 46 ``` 47 48 [1203B - Equal Rectangles](/contest/1203/problem/B "Codeforces Round 579 (Div. 3)") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 61 int main() { 62 #ifdef _DEBUG 63 freopen("input.txt", "r", stdin); 64 // freopen("output.txt", "w", stdout); 65 #endif 66 67 int q; 68 cin >> q; 69 for (int i = 0; i < q; ++i) { 70 int n; 71 cin >> n; 72 vector<int> a(4 * n); 73 for (int j = 0; j < 4 * n; ++j) { 74 cin >> a[j]; 75 } 76 sort(a.begin(), a.end()); 77 int area = a[0] * a.back(); 78 bool ok = true; 79 for (int i = 0; i < n; ++i) { 80 int lf = i * 2, rg = 4 * n - (i * 2) - 1; 81 if (a[lf] != a[lf + 1] || a[rg] != a[rg - 1] || a[lf] * 1ll * a[rg] != area) { 82 ok = false; 83 } 84 } 85 if (ok) cout << "YES" << endl; 86 else cout << "NO" << endl; 87 } 88 89 return 0; 90 } 91 ``` 92 93 [1203C - Common Divisors](/contest/1203/problem/C "Codeforces Round 579 (Div. 3)") 94 95 **Tutorial** 96 97 Tutorial is loading... 98 99 **Solution** 100 101 ``` 102 #include <bits/stdc++.h> 103 104 using namespace std; 105 106 int main() { 107 #ifdef _DEBUG 108 freopen("input.txt", "r", stdin); 109 // freopen("output.txt", "w", stdout); 110 #endif 111 112 int n; 113 cin >> n; 114 long long g = 0; 115 for (int i = 0; i < n; ++i) { 116 long long x; 117 cin >> x; 118 g = __gcd(g, x); 119 } 120 121 int ans = 0; 122 for (int i = 1; i * 1ll * i <= g; ++i) { 123 if (g % i == 0) { 124 ++ans; 125 if (i != g / i) { 126 ++ans; 127 } 128 } 129 } 130 131 cout << ans << endl; 132 133 return 0; 134 } 135 ``` 136 137 [1203D1 - Remove the Substring (easy version)](/contest/1203/problem/D1 "Codeforces Round 579 (Div. 3)") 138 139 **Tutorial** 140 141 Tutorial is loading... 142 143 **Solution** 144 145 ``` 146 #include <bits/stdc++.h> 147 148 using namespace std; 149 150 int main() { 151 #ifdef _DEBUG 152 freopen("input.txt", "r", stdin); 153 // freopen("output.txt", "w", stdout); 154 #endif 155 156 string s, t; 157 cin >> s >> t; 158 int ans = 0; 159 for (int i = 0; i < int(s.size()); ++i) { 160 for (int j = i; j < int(s.size()); ++j) { 161 int pos = 0; 162 for (int p = 0; p < int(s.size()); ++p) { 163 if (i <= p && p <= j) continue; 164 if (pos < int(t.size()) && t[pos] == s[p]) ++pos; 165 } 166 if (pos == int(t.size())) ans = max(ans, j - i + 1); 167 } 168 } 169 cout << ans << endl; 170 171 return 0; 172 } 173 ``` 174 175 [1203D2 - Remove the Substring (hard version)](/contest/1203/problem/D2 "Codeforces Round 579 (Div. 3)") 176 177 **Tutorial** 178 179 Tutorial is loading... 180 181 **Solution** 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 string s, t; 195 cin >> s >> t; 196 vector<int> rg(t.size()); 197 198 for (int i = int(t.size()) - 1; i >= 0; --i) { 199 int pos = int(s.size()) - 1; 200 if (i + 1 < int(t.size())) pos = rg[i + 1] - 1; 201 while (s[pos] != t[i]) --pos; 202 rg[i] = pos; 203 } 204 205 int ans = 0; 206 int pos = 0; 207 for (int i = 0; i < int(s.size()); ++i) { 208 int rpos = int(s.size()) - 1; 209 if (pos < int(t.size())) rpos = rg[pos] - 1; 210 ans = max(ans, rpos - i + 1); 211 if (pos < int(t.size()) && t[pos] == s[i]) ++pos; 212 } 213 214 cout << ans << endl; 215 216 return 0; 217 } 218 ``` 219 220 [1203E - Boxers](/contest/1203/problem/E "Codeforces Round 579 (Div. 3)") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution** 227 228 ``` 229 #include <bits/stdc++.h> 230 231 using namespace std; 232 233 int main() { 234 int n; 235 cin >> n; 236 vector<int> a(n); 237 for (int i = 0; i < n; ++i) { 238 cin >> a[i]; 239 } 240 sort(a.rbegin(), a.rend()); 241 int lst = a[0] + 2; 242 int ans = 0; 243 for (int i = 0; i < n; ++i) { 244 int cur = -1; 245 for (int dx = 1; dx >= -1; --dx) { 246 if (a[i] + dx > 0 && a[i] + dx < lst) { 247 cur = a[i] + dx; 248 break; 249 } 250 } 251 if (cur == -1) continue; 252 ++ans; 253 lst = cur; 254 } 255 cout << ans << endl; 256 } 257 ``` 258 259 [1203F1 - Complete the Projects (easy version)](/contest/1203/problem/F1 "Codeforces Round 579 (Div. 3)") 260 261 **Tutorial** 262 263 Tutorial is loading... 264 265 **Solution** 266 267 ``` 268 #include <bits/stdc++.h> 269 270 using namespace std; 271 272 bool comp(const pair<int, int>& a, const pair<int, int>& b) { 273 return a.first + a.second > b.first + b.second; 274 } 275 276 int main() { 277 #ifdef _DEBUG 278 freopen("input.txt", "r", stdin); 279 // freopen("output.txt", "w", stdout); 280 #endif 281 282 int n, r; 283 cin >> n >> r; 284 vector<pair<int, int>> pos, neg; 285 for (int i = 0; i < n; ++i) { 286 pair<int, int> cur; 287 cin >> cur.first >> cur.second; 288 if (cur.second >= 0) pos.push_back(cur); 289 else { 290 cur.first = max(cur.first, abs(cur.second)); 291 neg.push_back(cur); 292 } 293 } 294 295 sort(pos.begin(), pos.end()); 296 sort(neg.begin(), neg.end(), comp); 297 298 int taken = 0; 299 for (int i = 0; i < int(pos.size()); ++i) { 300 if (r >= pos[i].first) { 301 r += pos[i].second; 302 ++taken; 303 } 304 } 305 306 vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0)); 307 dp[0][r] = taken; 308 for (int i = 0; i < int(neg.size()); ++i) { 309 for (int cr = 0; cr <= r; ++cr) { 310 if (cr >= neg[i].first && cr + neg[i].second >= 0) { 311 dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1); 312 } 313 dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]); 314 } 315 } 316 317 int ans = 0; 318 for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]); 319 cout << (ans == n ? "YES" : "NO") << endl; 320 321 return 0; 322 } 323 ``` 324 325 [1203F2 - Complete the Projects (hard version)](/contest/1203/problem/F2 "Codeforces Round 579 (Div. 3)") 326 327 **Tutorial** 328 329 Tutorial is loading... 330 331 **Solution** 332 333 ``` 334 #include <bits/stdc++.h> 335 336 using namespace std; 337 338 bool comp(const pair<int, int>& a, const pair<int, int>& b) { 339 return a.first + a.second > b.first + b.second; 340 } 341 342 int main() { 343 #ifdef _DEBUG 344 freopen("input.txt", "r", stdin); 345 // freopen("output.txt", "w", stdout); 346 #endif 347 348 int n, r; 349 cin >> n >> r; 350 vector<pair<int, int>> pos, neg; 351 for (int i = 0; i < n; ++i) { 352 pair<int, int> cur; 353 cin >> cur.first >> cur.second; 354 if (cur.second >= 0) pos.push_back(cur); 355 else { 356 cur.first = max(cur.first, abs(cur.second)); 357 neg.push_back(cur); 358 } 359 } 360 361 sort(pos.begin(), pos.end()); 362 sort(neg.begin(), neg.end(), comp); 363 364 int taken = 0; 365 for (int i = 0; i < int(pos.size()); ++i) { 366 if (r >= pos[i].first) { 367 r += pos[i].second; 368 ++taken; 369 } 370 } 371 372 vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0)); 373 dp[0][r] = taken; 374 for (int i = 0; i < int(neg.size()); ++i) { 375 for (int cr = 0; cr <= r; ++cr) { 376 if (cr >= neg[i].first && cr + neg[i].second >= 0) { 377 dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1); 378 } 379 dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]); 380 } 381 } 382 383 int ans = 0; 384 for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]); 385 cout << ans << endl; 386 387 return 0; 388 } 389 ```