1551.md (7537B)
1 Source: https://codeforces.com/blog/entry/93149 2 3 Ideas: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). 4 5 [1551A - Polycarp and Coins](/contest/1551/problem/A "Codeforces Round 734 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 for i in range(0, int(input())): 15 n = int(input()) 16 c1 = n // 3; 17 c2 = c1; 18 if n % 3 == 1: 19 c1 += 1 20 elif n % 3 == 2: 21 c2 += 1 22 print(c1, c2) 23 ``` 24 25 [1551B1 - Wonderful Coloring - 1](/contest/1551/problem/B1 "Codeforces Round 734 (Div. 3)") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 using namespace std; 37 38 const int L = 26; 39 int cnt[L]; 40 41 int main() 42 { 43 int t; 44 cin >> t; 45 while (t--) 46 { 47 string s; 48 cin >> s; 49 memset(cnt, 0, sizeof(cnt)); 50 for (auto c : s) cnt[c - 'a']++; 51 int cnt1 = 0; 52 int cnt2 = 0; 53 for (int i = 0; i < L; i++) 54 if (cnt[i] == 1) 55 cnt1++; 56 else if (cnt[i] > 0) 57 cnt2++; 58 cout << (cnt2 + cnt1 / 2) << endl; 59 } 60 return 0; 61 } 62 ``` 63 64 [1551B2 - Wonderful Coloring - 2](/contest/1551/problem/B2 "Codeforces Round 734 (Div. 3)") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution** 71 72 ``` 73 #include <bits/stdc++.h> 74 using namespace std; 75 const int MAX_N = 200 * 1000 + 13; 76 77 int ans[MAX_N]; 78 map<int, vector<int>> indices; 79 80 int main() 81 { 82 int t; 83 cin >> t; 84 while (t--) 85 { 86 int n, k; 87 cin >> n >> k; 88 indices.clear(); 89 memset(ans, 0, n * sizeof(ans[0])); 90 for (int i = 0; i < n; i++) 91 { 92 int x; 93 cin >> x; 94 if (indices[x].size() < k) 95 indices[x].push_back(i); 96 } 97 int m = 0; 98 for (auto e : indices) m += e.second.size(); 99 m -= m % k; 100 int color = 0; 101 for (auto e : indices) 102 for (auto i : e.second) 103 { 104 ans[i] = ++color; 105 color %= k; 106 if (--m == 0) goto _output; 107 } 108 _output: 109 for (int i = 0; i < n; i++) 110 cout << ans[i] << ' '; 111 cout << '\n'; 112 } 113 114 return 0; 115 } 116 ``` 117 118 [1551C - Interesting Story](/contest/1551/problem/C "Codeforces Round 734 (Div. 3)") 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution** 125 126 ``` 127 #include <bits/stdc++.h> 128 using namespace std; 129 const int MAX_N = 2 * 100 * 1000 + 13; 130 const int L = 26; 131 132 vector<int> balance[L]; 133 134 int main() 135 { 136 int t; 137 cin >> t; 138 while (t--) 139 { 140 int n; 141 cin >> n; 142 for (int i = 0; i < L; i++) 143 balance[i].clear(); 144 for (int i = 1; i <= n; i++) 145 { 146 string s; 147 cin >> s; 148 int initBalance = -(int)s.length(); 149 for (int j = 0; j < L; j++) 150 balance[j].push_back(initBalance); 151 for (auto c : s) 152 balance[c - 'a'].back() += 2; 153 } 154 int bestCount = 0; 155 int bestLetter = 0; 156 for (int i = 0; i < L; i++) 157 { 158 auto& b = balance[i]; 159 sort(b.begin(), b.end()); 160 reverse(b.begin(), b.end()); 161 if (b[0] <= 0) continue; 162 int sumBalance = b[0]; 163 int j = 1; 164 for (; j < n && sumBalance > 0; j++) 165 sumBalance += b[j]; 166 if (sumBalance <= 0) j--; 167 if (j > bestCount) 168 { 169 bestCount = j; 170 bestLetter = i; 171 } 172 } 173 174 cout << bestCount << endl; 175 } 176 return 0; 177 } 178 ``` 179 180 [1551D1 - Domino (easy version)](/contest/1551/problem/D1 "Codeforces Round 734 (Div. 3)") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 using namespace std; 191 192 int main() 193 { 194 int t; 195 cin >> t; 196 while (t--) 197 { 198 int n, m, kh; 199 cin >> n >> m >> kh; 200 int kv = n * m / 2 - kh; 201 if (n & 1) 202 { 203 kh -= m / 2; 204 if (kh < 0) 205 { 206 cout << "NO\n"; 207 continue; 208 } 209 } 210 else if (m & 1) 211 { 212 kv -= n / 2; 213 if (kv < 0) 214 { 215 cout << "NO\n"; 216 continue; 217 } 218 } 219 if ((kh & 1) || (kv & 1)) 220 { 221 cout << "NO\n"; 222 continue; 223 } 224 cout << "YES\n"; 225 } 226 return 0; 227 } 228 ``` 229 230 [1551D2 - Domino (hard version)](/contest/1551/problem/D2 "Codeforces Round 734 (Div. 3)") 231 232 **Tutorial** 233 234 Tutorial is loading... 235 236 **Solution** 237 238 ``` 239 #include <bits/stdc++.h> 240 using namespace std; 241 242 char field[128][128]; 243 244 int main() 245 { 246 int t; 247 cin >> t; 248 while (t--) 249 { 250 int n, m, kh; 251 cin >> n >> m >> kh; 252 int kv = n * m / 2 - kh; 253 if (n & 1) 254 { 255 kh -= m / 2; 256 if (kh < 0) 257 { 258 cout << "NO\n"; 259 continue; 260 } 261 262 for (int i = 0; i < m / 2; i++) 263 field[n - 1][i * 2] = field[n - 1][i * 2 + 1] = ((i & 1) ? 'x' : 'y'); 264 } 265 else if (m & 1) 266 { 267 kv -= n / 2; 268 if (kv < 0) 269 { 270 cout << "NO\n"; 271 continue; 272 } 273 274 for (int i = 0; i < n / 2; i++) 275 field[i * 2][m - 1] = field[i * 2 + 1][m - 1] = ((i & 1) ? 'x' : 'y'); 276 } 277 if ((kh & 1) || (kv & 1)) 278 { 279 cout << "NO\n"; 280 continue; 281 } 282 for(int i = 0; i < n / 2; i++) 283 for (int j = 0; j < m / 2; j++) 284 { 285 if (kh) 286 { 287 kh -= 2; 288 field[2 * i][2 * j] = field[2 * i][2 * j + 1] = (((i + j) & 1) ? 'a' : 'b'); 289 field[2 * i + 1][2 * j] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd'); 290 } 291 else 292 { 293 field[2 * i][2 * j] = field[2 * i + 1][2 * j] = (((i + j) & 1) ? 'a' : 'b'); 294 field[2 * i][2 * j + 1] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd'); 295 } 296 } 297 298 cout << "YES\n"; 299 for (int i = 0; i < n; i++) 300 { 301 field[i][m] = 0; 302 cout << field[i] << '\n'; 303 } 304 } 305 return 0; 306 } 307 ``` 308 309 [1551E - Fixed Points](/contest/1551/problem/E "Codeforces Round 734 (Div. 3)") 310 311 **Tutorial** 312 313 Tutorial is loading... 314 315 **Solution** 316 317 ``` 318 #include <bits/stdc++.h> 319 using namespace std; 320 const int MAX_N = 6000; 321 322 int dp[MAX_N][MAX_N]; 323 int a[MAX_N]; 324 325 int main() 326 { 327 int t; 328 cin >> t; 329 while (t--) 330 { 331 int n, k; 332 cin >> n >> k; 333 for (int i = 1; i <= n; i++) cin >> a[i]; 334 for (int i = 0; i <= n; i++) 335 for (int j = 0; j <= i; j++) 336 dp[i][j] = 0; 337 for(int i = 0; i < n; i++) 338 for (int j = 0; j <= i; j++) 339 { 340 dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); 341 dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((a[i + 1] == j + 1) ? 1 : 0)); 342 } 343 int ans = -1; 344 for(int i = n; i >= 0; i--) 345 if (dp[n][i] >= k) 346 { 347 ans = n - i; 348 break; 349 } 350 cout << ans << '\n'; 351 } 352 return 0; 353 } 354 ``` 355 356 [1551F - Equidistant Vertices](/contest/1551/problem/F "Codeforces Round 734 (Div. 3)") 357 358 **Tutorial** 359 360 Tutorial is loading... 361 362 **Solution** 363 364 ``` 365 #include <bits/stdc++.h> 366 using namespace std; 367 const int MAX_N = 128; 368 369 typedef long long ll; 370 const ll mod = 1000 * 1000 * 1000 + 7; 371 372 ll add(ll x, ll y) { return (x + y) % mod; } 373 ll mul(ll x, ll y) { return x * y % mod; } 374 375 vector<int> g[MAX_N]; 376 bool used[MAX_N]; 377 int cnt[MAX_N]; 378 ll dp[MAX_N][MAX_N]; 379 380 ll rundp(int m, int k) 381 { 382 for (int i = 0; i <= m; i++) 383 for (int j = 0; j <= k; j++) 384 dp[i][j] = 0; 385 dp[0][0] = 1; 386 for (int i = 0; i < m; i++) 387 for (int j = 0; j <= k; j++) 388 { 389 dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]); 390 dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], cnt[i])); 391 } 392 return dp[m][k]; 393 } 394 395 void solve() 396 { 397 int n, k; 398 cin >> n >> k; 399 for (int i = 0; i < n; i++) 400 g[i].clear(); 401 for (int i = 1; i < n; i++) 402 { 403 int a, b; 404 cin >> a >> b; 405 g[--a].push_back(--b); 406 g[b].push_back(a); 407 } 408 if (k == 2) 409 { 410 cout << n * (n - 1LL) / 2 % mod << '\n'; 411 return; 412 } 413 ll ans = 0; 414 for (int center = 0; center < n; center++) 415 { 416 memset(used, 0, n); 417 used[center] = true; 418 419 vector<pair<int, int>> layer; 420 int m = g[center].size(); 421 for (int i = 0; i < m; i++) 422 { 423 int y = g[center][i]; 424 layer.emplace_back(y, i); 425 cnt[i] = 1; 426 used[y] = true; 427 } 428 while (!layer.empty()) 429 { 430 ans = add(ans, rundp(m, k)); 431 vector<pair<int, int>> newlayer; 432 for (auto p : layer) 433 { 434 cnt[p.second]--; 435 for (auto y : g[p.first]) 436 if (!used[y]) 437 { 438 newlayer.emplace_back(y, p.second); 439 used[y] = true; 440 cnt[p.second]++; 441 } 442 } 443 layer = newlayer; 444 } 445 } 446 cout << ans << '\n'; 447 } 448 449 int main() 450 { 451 int t; 452 cin >> t; 453 while (t--) solve(); 454 return 0; 455 } 456 ```