1829.md (7748B)
1 Source: https://codeforces.com/blog/entry/116108 2 3 We hope you enjoyed the contest! 4 5 [1829A - Love Story](/contest/1829/problem/A "Codeforces Round 871 (Div. 4)") 6 7 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 void solve() 21 { 22 string s, c = "codeforces"; 23 cin >> s; 24 int ans = 0; 25 for(int i = 0; i < 10; i++) 26 { 27 if(s[i] != c[i]) 28 { 29 ans++; 30 } 31 } 32 cout << ans << endl; 33 } 34 35 int32_t main(){ 36 int t = 1; 37 cin >> t; 38 while (t--) { 39 solve(); 40 } 41 } 42 ``` 43 44 [1829B - Blank Space](/contest/1829/problem/B "Codeforces Round 871 (Div. 4)") 45 46 Idea: [mesanu](/profile/mesanu "Expert mesanu") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution** 53 54 ``` 55 #include <bits/stdc++.h> 56 using namespace std; 57 58 void solve() 59 { 60 int n; 61 cin >> n; 62 int a[n]; 63 int cnt = 0, ans = 0; 64 for(int i = 0; i < n; i++) 65 { 66 cin >> a[i]; 67 if(a[i] == 0) 68 { 69 cnt++; 70 } 71 else 72 { 73 ans = max(ans, cnt); 74 cnt = 0; 75 } 76 } 77 cout << max(ans, cnt) << endl; 78 } 79 80 int32_t main(){ 81 int t = 1; 82 cin >> t; 83 while (t--) { 84 solve(); 85 } 86 } 87 ``` 88 89 [1829C - Mr. Perfectly Fine](/contest/1829/problem/C "Codeforces Round 871 (Div. 4)") 90 91 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 #include "bits/stdc++.h" 101 using namespace std; 102 103 #define ll long long 104 105 #define all(v) v.begin(), v.end() 106 #define rall(v) v.rbegin(),v.rend() 107 108 #define pb push_back 109 #define sz(a) (int)a.size() 110 111 void solve() { 112 int n; cin >> n; 113 map<string, int> mp; 114 mp["00"] = mp["01"] = mp["10"] = mp["11"] = 1e9; 115 int ans = 1e9; 116 for(int i = 0; i < n; ++i) { 117 int x; cin >> x; string s; cin >> s; 118 mp[s] = min(mp[s], x); 119 } 120 if(min(mp["11"], mp["10"] + mp["01"]) > (int)1e6) { 121 cout << "-1\n"; 122 } else { 123 cout << min(mp["11"], mp["10"] + mp["01"]) << "\n"; 124 } 125 } 126 127 int32_t main() { 128 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 129 int t = 1; 130 cin >> t; 131 while(t--) { 132 solve(); 133 } 134 } 135 ``` 136 137 [1829D - Gold Rush](/contest/1829/problem/D "Codeforces Round 871 (Div. 4)") 138 139 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 using namespace std; 151 152 bool ok(int n, int m) { 153 if (n == m) {return true;} 154 else if (n % 3 != 0) {return false;} 155 else {return (ok(n / 3, m) || ok(2 * n / 3, m));} 156 } 157 158 void solve() { 159 int n, m; 160 cin >> n >> m; 161 cout << (ok(n, m) ? "YES" : "NO") << '\n'; 162 } 163 164 int main() { 165 ios::sync_with_stdio(false); 166 cin.tie(nullptr); 167 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 168 // solve(); 169 } 170 ``` 171 172 [1829E - The Lakes](/contest/1829/problem/E "Codeforces Round 871 (Div. 4)") 173 174 Idea: [mesanu](/profile/mesanu "Expert mesanu") 175 176 **Tutorial** 177 178 Tutorial is loading... 179 180 **Solution** 181 182 ``` 183 #include <bits/stdc++.h> 184 #define startt ios_base::sync_with_stdio(false);cin.tie(0); 185 typedef long long ll; 186 using namespace std; 187 #define vint vector<int> 188 #define all(v) v.begin(), v.end() 189 #define MOD 1000000007 190 #define MOD2 998244353 191 #define MX 1000000000 192 #define MXL 1000000000000000000 193 #define PI (ld)2*acos(0.0) 194 #define pb push_back 195 #define sc second 196 #define fr first 197 #define endl '\n' 198 #define ld long double 199 #define NO cout << "NO" << endl 200 #define YES cout << "YES" << endl 201 202 int n, m; 203 bool vis[1005][1005]; 204 int a[1005][1005]; 205 206 int dfs(int i, int j) 207 { 208 vis[i][j] = true; 209 int ans = a[i][j]; 210 if(i != 0 && a[i-1][j] != 0 && !vis[i-1][j]) 211 { 212 ans+=dfs(i-1, j); 213 } 214 if(i != n-1 && a[i+1][j] != 0 && !vis[i+1][j]) 215 { 216 ans+=dfs(i+1, j); 217 } 218 if(j != 0 && a[i][j-1] != 0 && !vis[i][j-1]) 219 { 220 ans+=dfs(i, j-1); 221 } 222 if(j != m-1 && a[i][j+1] != 0 && !vis[i][j+1]) 223 { 224 ans+=dfs(i, j+1); 225 } 226 return ans; 227 } 228 229 void solve() 230 { 231 cin >> n >> m; 232 for(int i = 0; i < n; i++) 233 { 234 for(int j = 0; j < m; j++) 235 { 236 vis[i][j] = false; 237 cin >> a[i][j]; 238 } 239 } 240 int ans = 0; 241 for(int i = 0; i < n; i++) 242 { 243 for(int j = 0; j < m; j++) 244 { 245 if(!vis[i][j] && a[i][j] != 0) 246 { 247 ans = max(ans, dfs(i, j)); 248 } 249 } 250 } 251 cout << ans << endl; 252 } 253 254 int32_t main(){ 255 startt 256 int t = 1; 257 cin >> t; 258 while (t--) { 259 solve(); 260 } 261 } 262 ``` 263 264 [1829F - Forever Winter](/contest/1829/problem/F "Codeforces Round 871 (Div. 4)") 265 266 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution** 273 274 ``` 275 #include <bits/stdc++.h> 276 277 using namespace std; 278 279 const int MAX = 200007; 280 const int MOD = 1000000007; 281 282 void solve() { 283 int n, m; 284 cin >> n >> m; 285 int cnt[n + 1]; 286 for (int i = 1; i <= n; i++) { 287 cnt[i] = 0; 288 } 289 for (int i = 0; i < m; i++) { 290 int u, v; 291 cin >> u >> v; 292 cnt[u]++; 293 cnt[v]++; 294 } 295 map<int, int> cnts; 296 for (int i = 1; i <= n; i++) { 297 cnts[cnt[i]]++; 298 } 299 vector<int> v; 300 for (auto p : cnts) { 301 v.push_back(p.second); 302 } 303 sort(v.begin(), v.end()); 304 if (v.size() == 3) { 305 cout << v[1] << ' ' << v[2] / v[1] << '\n'; 306 } 307 else { 308 cout << v[0] - 1 << ' ' << v[1] / (v[0] - 1) << '\n'; 309 } 310 } 311 312 int main() { 313 ios::sync_with_stdio(false); 314 cin.tie(nullptr); 315 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 316 // solve(); 317 } 318 ``` 319 320 [1829G - Hits Different](/contest/1829/problem/G "Codeforces Round 871 (Div. 4)") 321 322 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 323 324 **Tutorial** 325 326 Tutorial is loading... 327 328 **Solution** 329 330 ``` 331 #include <bits/stdc++.h> 332 333 using namespace std; 334 335 long long ans[2000007]; 336 long long a[1500][1500] = {}, curr = 1; 337 338 void solve() { 339 int n; 340 cin >> n; 341 cout << ans[n] << '\n'; 342 } 343 344 int main() { 345 ios::sync_with_stdio(false); 346 cin.tie(nullptr); 347 348 for (int i = 1; i < 1500; i++) { 349 for (int j = i - 1; j >= 1; j--) { 350 a[j][i - j] = a[j - 1][i - j] + a[j][i - j - 1] - a[j - 1][i - j - 1] + curr * curr; 351 ans[curr] = a[j][i - j]; 352 curr++; 353 } 354 } 355 356 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 357 // solve(); 358 } 359 ``` 360 361 [1829H - Don't Blame Me](/contest/1829/problem/H "Codeforces Round 871 (Div. 4)") 362 363 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 364 365 **Tutorial** 366 367 Tutorial is loading... 368 369 **Solution** 370 371 ``` 372 #include "bits/stdc++.h" 373 using namespace std; 374 375 #define ll long long 376 377 #define all(v) v.begin(), v.end() 378 #define rall(v) v.rbegin(),v.rend() 379 380 #define pb push_back 381 #define sz(a) (int)a.size() 382 383 const int mod = 1e9 + 7; 384 void solve() { 385 int n, x; cin >> n >> x; 386 vector<int> a(n + 1); 387 vector<vector<int>> dp(n + 1, vector<int>(1 << 6, 0)); 388 for(int i = 1; i <= n; ++i) { 389 cin >> a[i]; 390 for(int mask = 0; mask < (1 << 6); ++mask) { 391 dp[i][mask] += dp[i - 1][mask]; 392 if(dp[i][mask] >= mod) dp[i][mask] -= mod; 393 dp[i][mask & a[i]] += dp[i - 1][mask]; 394 if(dp[i][mask & a[i]] >= mod) dp[i][mask & a[i]] -= mod; 395 } 396 dp[i][a[i]] = (dp[i][a[i]] + 1) % mod; 397 } 398 int ans = 0; 399 for(int mask = 0; mask < (1 << 6); ++mask) { 400 if(__builtin_popcount(mask) == x) { 401 ans = (ans + dp[n][mask]) % mod; 402 } 403 } 404 cout << ans << "\n"; 405 } 406 407 int32_t main() { 408 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 409 int t = 1; 410 cin >> t; 411 while(t--) { 412 solve(); 413 } 414 } 415 ```