1183.md (7436B)
1 Source: https://codeforces.com/blog/entry/68003 2 3 [1183A - Nearest Interesting Number](/contest/1183/problem/A "Codeforces Round 570 (Div. 3)") 4 5 Idea: [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 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 20 int sum(int a) { 21 int result = 0; 22 while (a > 0) { 23 result += a % 10; 24 a /= 10; 25 } 26 return result; 27 } 28 29 int main() { 30 int a; 31 cin >> a; 32 while (sum(a) % 4 != 0) { 33 a++; 34 } 35 cout << a << endl; 36 } 37 ``` 38 39 [1183B - Equalize Prices](/contest/1183/problem/B "Codeforces Round 570 (Div. 3)") 40 41 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 using namespace std; 53 54 int main() { 55 #ifdef _DEBUG 56 freopen("input.txt", "r", stdin); 57 // freopen("output.txt", "w", stdout); 58 #endif 59 60 int q; 61 cin >> q; 62 for (int i = 0; i < q; ++i) { 63 int n, k; 64 cin >> n >> k; 65 vector<int> a(n); 66 for (int j = 0; j < n; ++j) { 67 cin >> a[j]; 68 } 69 int mn = *min_element(a.begin(), a.end()); 70 int mx = *max_element(a.begin(), a.end()); 71 if (mx - mn > 2 * k) cout << -1 << endl; 72 else cout << mn + k << endl; 73 } 74 75 return 0; 76 } 77 ``` 78 79 [1183C - Computer Game](/contest/1183/problem/C "Codeforces Round 570 (Div. 3)") 80 81 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [vovuh](/profile/vovuh "Candidate Master vovuh") and [BledDest](/profile/BledDest "Grandmaster BledDest") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 int main() { 95 #ifdef _DEBUG 96 freopen("input.txt", "r", stdin); 97 // freopen("output.txt", "w", stdout); 98 #endif 99 100 int q; 101 cin >> q; 102 for (int i = 0; i < q; ++i) { 103 long long k, n, a, b; 104 cin >> k >> n >> a >> b; 105 k -= n * a; 106 if (k > 0) { 107 cout << n << endl; 108 } else { 109 k = -k; 110 ++k; 111 long long diff = a - b; 112 long long turns = (k + diff - 1) / diff; 113 if (turns > n) { 114 cout << -1 << '\n'; 115 } else { 116 cout << n - turns << '\n'; 117 } 118 } 119 } 120 121 return 0; 122 } 123 ``` 124 125 [1183D - Candy Box (easy version)](/contest/1183/problem/D "Codeforces Round 570 (Div. 3)") 126 127 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 128 129 **Tutorial** 130 131 Tutorial is loading... 132 133 **Solution** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 140 int main() { 141 #ifdef _DEBUG 142 freopen("input.txt", "r", stdin); 143 // freopen("output.txt", "w", stdout); 144 #endif 145 146 int q; 147 cin >> q; 148 for (int t = 0; t < q; ++t) { 149 int n; 150 cin >> n; 151 vector<int> cnt(n + 1); 152 for (int i = 0; i < n; ++i) { 153 int x; 154 cin >> x; 155 ++cnt[x]; 156 } 157 sort(cnt.rbegin(), cnt.rend()); 158 int ans = cnt[0]; 159 int lst = cnt[0]; 160 for (int i = 1; i <= n; ++i) { 161 if (lst == 0) break; 162 if (cnt[i] >= lst) { 163 ans += lst - 1; 164 lst -= 1; 165 } else { 166 ans += cnt[i]; 167 lst = cnt[i]; 168 } 169 } 170 cout << ans << endl; 171 } 172 173 return 0; 174 } 175 ``` 176 177 [1183E - Subsequences (easy version)](/contest/1183/problem/E "Codeforces Round 570 (Div. 3)") 178 179 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 180 181 **Tutorial** 182 183 Tutorial is loading... 184 185 **Solution** 186 187 ``` 188 #include <bits/stdc++.h> 189 190 using namespace std; 191 192 int main() { 193 #ifdef _DEBUG 194 freopen("input.txt", "r", stdin); 195 // freopen("output.txt", "w", stdout); 196 #endif 197 198 int n, k; 199 cin >> n >> k; 200 string s; 201 cin >> s; 202 203 int ans = 0; 204 queue<string> q; 205 set<string> st; 206 q.push(s); 207 st.insert(s); 208 while (!q.empty() && int(st.size()) < k) { 209 string v = q.front(); 210 q.pop(); 211 for (int i = 0; i < int(v.size()); ++i) { 212 string nv = v; 213 nv.erase(i, 1); 214 if (!st.count(nv) && int(st.size()) + 1 <= k) { 215 q.push(nv); 216 st.insert(nv); 217 ans += n - nv.size(); 218 } 219 } 220 } 221 222 if (int(st.size()) < k) cout << -1 << endl; 223 else cout << ans << endl; 224 225 return 0; 226 } 227 ``` 228 229 [1183F - Topforces Strikes Back](/contest/1183/problem/F "Codeforces Round 570 (Div. 3)") 230 231 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 232 233 **Tutorial** 234 235 Tutorial is loading... 236 237 **Solution** 238 239 ``` 240 #include <bits/stdc++.h> 241 242 using namespace std; 243 244 int main() { 245 #ifdef _DEBUG 246 freopen("input.txt", "r", stdin); 247 // freopen("output.txt", "w", stdout); 248 #endif 249 250 int q; 251 cin >> q; 252 for (int i = 0; i < q; ++i) { 253 int n; 254 cin >> n; 255 set<int> st; 256 for (int j = 0; j < n; ++j) { 257 int x; 258 cin >> x; 259 st.insert(x); 260 } 261 262 int ans = 0; 263 int mx = *st.rbegin(); 264 if (mx % 2 == 0 && mx % 3 == 0 && mx % 5 == 0) { 265 if (st.count(mx / 2) && st.count(mx / 3) && st.count(mx / 5)) { 266 ans = max(ans, mx / 2 + mx / 3 + mx / 5); 267 } 268 } 269 270 vector<int> res; 271 while (!st.empty() && int(res.size()) < 3) { 272 int x = *st.rbegin(); 273 st.erase(prev(st.end())); 274 bool ok = true; 275 for (auto it : res) ok &= (it % x != 0); 276 if (ok) res.push_back(x); 277 } 278 279 ans = max(ans, accumulate(res.begin(), res.end(), 0)); 280 281 cout << ans << endl; 282 } 283 284 return 0; 285 } 286 ``` 287 288 [1183G - Candy Box (hard version)](/contest/1183/problem/G "Codeforces Round 570 (Div. 3)") 289 290 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 291 292 **Tutorial** 293 294 Tutorial is loading... 295 296 **Solution** 297 298 ``` 299 #include<bits/stdc++.h> 300 301 using namespace std; 302 303 void solve() 304 { 305 int n; 306 scanf("%d", &n); 307 vector<int> cnt(n); 308 vector<int> cnt_good(n); 309 for(int i = 0; i < n; i++) 310 { 311 int a, f; 312 scanf("%d %d", &a, &f); 313 --a; 314 cnt[a]++; 315 if(f) cnt_good[a]++; 316 } 317 vector<vector<int> > types(n + 1); 318 for(int i = 0; i < n; i++) 319 types[cnt[i]].push_back(cnt_good[i]); 320 int ans1 = 0; 321 int ans2 = 0; 322 multiset<int> cur; 323 for(int i = n; i > 0; i--) 324 { 325 for(auto x : types[i]) cur.insert(x); 326 if(!cur.empty()) 327 { 328 int z = *cur.rbegin(); 329 ans1 += i; 330 ans2 += min(i, z); 331 cur.erase(cur.find(z)); 332 } 333 } 334 printf("%d %d\n", ans1, ans2); 335 } 336 337 int main() 338 { 339 int t; 340 scanf("%d", &t); 341 for(int i = 0; i < t; i++) 342 solve(); 343 } 344 ``` 345 346 [1183H - Subsequences (hard version)](/contest/1183/problem/H "Codeforces Round 570 (Div. 3)") 347 348 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 349 350 **Tutorial** 351 352 Tutorial is loading... 353 354 **Solution** 355 356 ``` 357 #include <bits/stdc++.h> 358 359 using namespace std; 360 361 const long long INF64 = 1e12; 362 363 int main() { 364 #ifdef _DEBUG 365 freopen("input.txt", "r", stdin); 366 // freopen("output.txt", "w", stdout); 367 #endif 368 369 int n; 370 long long k; 371 cin >> n >> k; 372 --k; // the whole string costs nothing 373 string s; 374 cin >> s; 375 376 vector<vector<int>> lst(n, vector<int>(26, -1)); 377 for (int i = 0; i < n; ++i) { 378 for (int j = 0; j < 26; ++j) { 379 if (i > 0) lst[i][j] = lst[i - 1][j]; 380 } 381 lst[i][s[i] - 'a'] = i; 382 } 383 384 vector<vector<long long>> dp(n + 1, vector<long long>(n + 1)); 385 for (int i = 0; i < n; ++i) { 386 dp[i][1] = 1; 387 } 388 389 for (int len = 2; len < n; ++len) { 390 for (int i = 1; i < n; ++i) { 391 for (int j = 0; j < 26; ++j) { 392 if (lst[i - 1][j] != -1) { 393 dp[i][len] = min(INF64, dp[i][len] + dp[lst[i - 1][j]][len - 1]); 394 } 395 } 396 } 397 } 398 399 long long ans = 0; 400 for (int len = n - 1; len >= 1; --len) { 401 long long cnt = 0; 402 for (int j = 0; j < 26; ++j) { 403 if (lst[n - 1][j] != -1) { 404 cnt += dp[lst[n - 1][j]][len]; 405 } 406 } 407 if (cnt >= k) { 408 ans += k * (n - len); 409 k = 0; 410 break; 411 } else { 412 ans += cnt * (n - len); 413 k -= cnt; 414 } 415 } 416 417 if (k == 1) { 418 ans += n; 419 --k; 420 } 421 422 if (k > 0) cout << -1 << endl; 423 else cout << ans << endl; 424 425 return 0; 426 } 427 ```