1176.md (6738B)
1 Source: https://codeforces.com/blog/entry/67598 2 3 [1176A - Divide it!](/contest/1176/problem/A "Codeforces Round 565 (Div. 3)") 4 5 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 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 long long n; 28 cin >> n; 29 int cnt2 = 0, cnt3 = 0, cnt5 = 0; 30 while (n % 2 == 0) { 31 n /= 2; 32 ++cnt2; 33 } 34 while (n % 3 == 0) { 35 n /= 3; 36 ++cnt3; 37 } 38 while (n % 5 == 0) { 39 n /= 5; 40 ++cnt5; 41 } 42 if (n != 1) { 43 cout << -1 << endl; 44 } else { 45 cout << cnt2 + cnt3 * 2 + cnt5 * 3 << endl; 46 } 47 } 48 49 return 0; 50 } 51 ``` 52 53 [1176B - Merge it!](/contest/1176/problem/B "Codeforces Round 565 (Div. 3)") 54 55 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution** 62 63 ``` 64 #include<bits/stdc++.h> 65 66 using namespace std; 67 68 int t, n; 69 int cnt[3]; 70 71 int main(){ 72 cin >> t; 73 for(int tc = 0; tc < t; ++tc){ 74 memset(cnt, 0, sizeof cnt); 75 cin >> n; 76 for(int i = 0; i < n; ++i){ 77 int x; 78 cin >> x; 79 ++cnt[x % 3]; 80 } 81 82 int res = cnt[0]; 83 int mn = min(cnt[1], cnt[2]); 84 res += mn; 85 cnt[1] -= mn, cnt[2] -= mn; 86 res += (cnt[1] + cnt[2]) / 3; 87 cout << res << endl; 88 } 89 return 0; 90 } 91 ``` 92 93 [1176C - Lose it!](/contest/1176/problem/C "Codeforces Round 565 (Div. 3)") 94 95 Idea: [vovuh](/profile/vovuh "Candidate Master vovuh") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution** 102 103 ``` 104 #include <bits/stdc++.h> 105 106 using namespace std; 107 108 int main() { 109 #ifdef _DEBUG 110 freopen("input.txt", "r", stdin); 111 // freopen("output.txt", "w", stdout); 112 #endif 113 114 vector<int> p({4, 8, 15, 16, 23, 42}); 115 116 int n; 117 cin >> n; 118 vector<int> a(n); 119 for (int i = 0; i < n; ++i) { 120 cin >> a[i]; 121 a[i] = lower_bound(p.begin(), p.end(), a[i]) - p.begin(); 122 } 123 124 vector<int> seq(6); 125 for (int i = 0; i < n; ++i) { 126 if (a[i] == 0) { 127 ++seq[0]; 128 } else { 129 if (seq[a[i] - 1] > 0) { 130 --seq[a[i] - 1]; 131 ++seq[a[i]]; 132 } 133 } 134 } 135 136 cout << n - seq[5] * 6 << endl; 137 138 return 0; 139 } 140 ``` 141 142 [1176D - Recover it!](/contest/1176/problem/D "Codeforces Round 565 (Div. 3)") 143 144 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 145 146 **Tutorial** 147 148 Tutorial is loading... 149 150 **Solution** 151 152 ``` 153 #include <bits/stdc++.h> 154 155 #define forn(i, n) for (int i = 0; i < int(n); i++) 156 157 using namespace std; 158 159 const int N = 3 * 1000 * 1000 + 13; 160 161 int lst[N]; 162 int num[N]; 163 164 void sieve(){ 165 forn(i, N) lst[i] = i; 166 for (int i = 2; i < N; ++i){ 167 if (lst[i] != i){ 168 lst[i] = i / lst[i]; 169 continue; 170 } 171 for (long long j = i * 1ll * i; j < N; j += i) 172 lst[j] = min(lst[j], i); 173 } 174 int cur = 0; 175 for (int i = 2; i < N; ++i) if (lst[i] == i) 176 num[i] = ++cur; 177 } 178 179 int cnt[N]; 180 181 int main() { 182 int n; 183 scanf("%d", &n); 184 forn(i, 2 * n){ 185 int x; 186 scanf("%d", &x); 187 ++cnt[x]; 188 } 189 190 sieve(); 191 192 vector<int> res; 193 for (int i = N - 1; i >= 0; --i){ 194 while (cnt[i] > 0){ 195 if (lst[i] == i){ 196 --cnt[num[i]]; 197 res.push_back(num[i]); 198 } 199 else{ 200 --cnt[lst[i]]; 201 res.push_back(i); 202 } 203 --cnt[i]; 204 } 205 } 206 207 for (auto it : res) 208 printf("%d ", it); 209 return 0; 210 } 211 ``` 212 213 [1176E - Cover it!](/contest/1176/problem/E "Codeforces Round 565 (Div. 3)") 214 215 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution** 222 223 ``` 224 #include <bits/stdc++.h> 225 226 using namespace std; 227 228 const int INF = 1e9; 229 230 int n, m; 231 vector<int> d; 232 vector<vector<int>> g; 233 234 void bfs(int s) { 235 d = vector<int>(n, INF); 236 d[s] = 0; 237 238 queue<int> q; 239 q.push(s); 240 241 while (!q.empty()) { 242 int v = q.front(); 243 q.pop(); 244 245 for (auto to : g[v]) { 246 if (d[to] == INF) { 247 d[to] = d[v] + 1; 248 q.push(to); 249 } 250 } 251 } 252 } 253 254 int main() { 255 #ifdef _DEBUG 256 freopen("input.txt", "r", stdin); 257 // freopen("output.txt", "w", stdout); 258 #endif 259 260 int t; 261 cin >> t; 262 263 for (int tc = 0; tc < t; ++tc){ 264 cin >> n >> m; 265 g = vector<vector<int>>(n); 266 for (int i = 0; i < m; ++i) { 267 int x, y; 268 cin >> x >> y; 269 --x, --y; 270 g[x].push_back(y); 271 g[y].push_back(x); 272 } 273 274 bfs(0); 275 vector<int> even, odd; 276 for (int i = 0; i < n; ++i) { 277 if (d[i] & 1) odd.push_back(i); 278 else even.push_back(i); 279 } 280 281 if (even.size() < odd.size()) { 282 cout << even.size() << endl; 283 for (auto v : even) cout << v + 1 << " "; 284 } else { 285 cout << odd.size() << endl; 286 for (auto v : odd) cout << v + 1 << " "; 287 } 288 cout << endl; 289 } 290 291 return 0; 292 } 293 ``` 294 295 [1176F - Destroy it!](/contest/1176/problem/F "Codeforces Round 565 (Div. 3)") 296 297 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 298 299 **Tutorial** 300 301 Tutorial is loading... 302 303 **Solution** 304 305 ``` 306 #define _CRT_SECURE_NO_WARNINGS 307 308 #include<iostream> 309 #include<cstdio> 310 #include<vector> 311 #include<algorithm> 312 313 using namespace std; 314 315 typedef long long li; 316 317 const li INF64 = li(1e18); 318 319 const int N = 200043; 320 vector<int> cards[N][4]; 321 li dp[N][10]; 322 int n; 323 li dp2[4][2]; 324 325 int main() 326 { 327 #ifdef _DEBUG 328 freopen("input.txt", "r", stdin); 329 freopen("output.txt", "w", stdout); 330 #endif 331 for(int i = 0; i < N; i++) 332 for(int j = 0; j < 10; j++) 333 dp[i][j] = -INF64; 334 dp[0][0] = 0; 335 scanf("%d", &n); 336 for (int i = 0; i < n; i++) 337 { 338 int k; 339 scanf("%d", &k); 340 for (int j = 0; j < k; j++) 341 { 342 int c, d; 343 scanf("%d %d", &c, &d); 344 cards[i][c].push_back(d); 345 } 346 } 347 for (int i = 0; i < n; i++) 348 { 349 for (int j = 1; j <= 3; j++) 350 { 351 int s = (j == 1 ? 3 : 1); 352 sort(cards[i][j].begin(), cards[i][j].end()); 353 reverse(cards[i][j].begin(), cards[i][j].end()); 354 while (cards[i][j].size() > s) 355 cards[i][j].pop_back(); 356 } 357 } 358 for (int i = 0; i < n; i++) 359 { 360 for (int j = 0; j < 4; j++) 361 for (int k = 0; k < 2; k++) 362 dp2[j][k] = -INF64; 363 dp2[0][0] = 0; 364 vector<pair<int, int> > cur; 365 for (int j = 1; j <= 3; j++) 366 for (auto x : cards[i][j]) 367 cur.push_back(make_pair(j, x)); 368 sort(cur.begin(), cur.end()); 369 do 370 { 371 int mana = 3; 372 li score = 0; 373 li mx = 0; 374 int cnt = 0; 375 for (auto x : cur) 376 { 377 cnt++; 378 if (mana < x.first) 379 break; 380 mana -= x.first; 381 mx = max(mx, li(x.second)); 382 score += x.second; 383 dp2[cnt][0] = max(dp2[cnt][0], score); 384 dp2[cnt][1] = max(dp2[cnt][1], score + mx); 385 } 386 } while (next_permutation(cur.begin(), cur.end())); 387 for(int j = 0; j < 10; j++) 388 for (int k = 0; k <= 3; k++) 389 { 390 int nxt = (j + k) % 10; 391 int f = (j + k >= 10 ? 1 : 0); 392 dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + dp2[k][f]); 393 } 394 } 395 li ans = 0; 396 for (int i = 0; i <= 9; i++) 397 ans = max(ans, dp[n][i]); 398 printf("%lld\n", ans); 399 return 0; 400 } 401 ```