1848.md (7745B)
1 Source: https://codeforces.com/blog/entry/118333 2 3 [1848A - Vika and Her Friends](/contest/1848/problem/A "Codeforces Round 885 (Div. 2)") 4 5 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 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 int long long 19 20 int32_t main() { 21 int t; 22 cin >> t; 23 while (t--) { 24 int n, m, k; 25 cin >> n >> m >> k; 26 int x, y; 27 cin >> x >> y; 28 string ans = "YES\n"; 29 for (int i = 0; i < k; ++i) { 30 int xx, yy; 31 cin >> xx >> yy; 32 if ((x + y) % 2 == (xx + yy) % 2) { 33 ans = "NO\n"; 34 } 35 } 36 cout << ans; 37 } 38 return 0; 39 } 40 ``` 41 42 [1848B - Vika and the Bridge](/contest/1848/problem/B "Codeforces Round 885 (Div. 2)") 43 44 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 45 46 **Tutorial** 47 48 Tutorial is loading... 49 50 **Solution** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 int main() { 58 int t; 59 cin >> t; 60 while (t--) { 61 int n, k; 62 cin >> n >> k; 63 vector<int> c(n); 64 for (int i = 0; i < n; ++i) { 65 cin >> c[i]; 66 } 67 vector<int> last(k, -1); 68 vector<int> max_step(k), max2_step(k); 69 for (int i = 0; i < n; ++i) { 70 int step = i - last[c[i] - 1]; 71 if (step > max_step[c[i] - 1]) { 72 max2_step[c[i] - 1] = max_step[c[i] - 1]; 73 max_step[c[i] - 1] = step; 74 } else if (step > max2_step[c[i] - 1]) { 75 max2_step[c[i] - 1] = step; 76 } 77 last[c[i] - 1] = i; 78 } 79 for (int i = 0; i < k; ++i) { 80 int step = n - last[i]; 81 if (step > max_step[i]) { 82 max2_step[i] = max_step[i]; 83 max_step[i] = step; 84 } else if (step > max2_step[i]) { 85 max2_step[i] = step; 86 } 87 } 88 int ans = 1e9; 89 for (int i = 0; i < k; ++i) { 90 ans = min(ans, max((max_step[i] + 1) / 2, max2_step[i])); 91 } 92 cout << ans - 1 << "\n"; 93 } 94 return 0; 95 } 96 ``` 97 98 [1848C - Vika and Price Tags](/contest/1848/problem/C "Codeforces Round 885 (Div. 2)") 99 100 Idea: [pavlekn](/profile/pavlekn "Candidate Master pavlekn") 101 102 **Tutorial** 103 104 Tutorial is loading... 105 106 **Solution** 107 108 ``` 109 #include <bits/stdc++.h> 110 111 using namespace std; 112 113 #define int long long 114 115 int gcd(int a, int b) { 116 if (a == 0) { 117 return 0; 118 } 119 if (b == 0) { 120 return 1; 121 } 122 if (a >= b) { 123 int r = a % b; 124 int k = a / b; 125 if (k % 2 == 1) { 126 return gcd(b, r) + k + k / 2; 127 } else { 128 return gcd(r, b) + k + k / 2; 129 } 130 } 131 return 1 + gcd(b, abs(a - b)); 132 } 133 134 int calc(int a, int b) { 135 if (a == 0) { 136 return 0; 137 } 138 if (b == 0) { 139 return 1; 140 } 141 return 1 + calc(b, abs(a - b)); 142 } 143 144 int32_t main() { 145 ios_base::sync_with_stdio(false); 146 cin.tie(0); 147 int t; 148 cin >> t; 149 for (int _ = 0; _ < t; ++_) { 150 int n; 151 cin >> n; 152 vector<int> a(n); 153 vector<int> b(n); 154 for (int i = 0; i < n; ++i) { 155 cin >> a[i]; 156 } 157 for (int i = 0; i < n; ++i) { 158 cin >> b[i]; 159 } 160 set<int> cnt; 161 for (int i = 0; i < n; ++i) { 162 if (a[i] == 0 && b[i] == 0) { 163 continue; 164 } 165 cnt.insert(gcd(a[i], b[i]) % 3); 166 } 167 if (cnt.size() <= 1) { 168 cout << "YES" << endl; 169 } else { 170 cout << "NO" << endl; 171 } 172 } 173 return 0; 174 } 175 ``` 176 177 [1848D - Vika and Bonuses](/contest/1848/problem/D "Codeforces Round 885 (Div. 2)") 178 179 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 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 #define int long long 193 194 int f(int s, int k) { 195 // (s + 20x) * (k - 4x) 196 // (-80)x^2 + (20k - 4s)x + (sk) 197 // -b/2a = (5k-s)/40 198 int x = (5 * k - s) / 40; 199 x = min(x, k / 4); 200 int res = s * k; 201 if (x > 0) { 202 res = max(res, (s + 20 * x) * (k - 4 * x)); 203 } 204 x = min(x + 1, k / 4); 205 if (x > 0) { 206 res = max(res, (s + 20 * x) * (k - 4 * x)); 207 } 208 return res; 209 } 210 211 int32_t main() { 212 int t; 213 cin >> t; 214 while (t--) { 215 int s, k; 216 cin >> s >> k; 217 int ans = s * k; 218 if (s % 10 == 5) { 219 ans = max(ans, (s + 5) * (k - 1)); 220 } else if (s % 10) { 221 if (s % 2 == 1) { 222 s += s % 10; 223 --k; 224 } 225 for (int i = 0; i < 4; ++i) { 226 if (k > 0) { 227 ans = max(ans, f(s, k)); 228 } 229 s += s % 10; 230 --k; 231 } 232 } 233 cout << ans << "\n"; 234 } 235 return 0; 236 } 237 ``` 238 239 [1848E - Vika and Stone Skipping](/contest/1848/problem/E "Codeforces Round 885 (Div. 2)") 240 241 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka") 242 243 **Tutorial** 244 245 Tutorial is loading... 246 247 **Solution** 248 249 ``` 250 #include <bits/stdc++.h> 251 252 using namespace std; 253 254 const int K = 1e6; 255 256 #define int long long 257 258 int mod; 259 260 int dp[K + 1]; 261 int cnt[K + 1]; 262 263 const int MM = 3e6 + 7; 264 265 int inv[MM]; 266 267 int cc = 0; 268 269 int mul(int a, int b) { 270 int bb = b; 271 while (bb % mod == 0) { 272 ++cc; 273 bb /= mod; 274 } 275 return (a * (bb % mod)) % mod; 276 } 277 278 int dv(int a, int b) { 279 int bb = b; 280 while (bb % mod == 0) { 281 --cc; 282 bb /= mod; 283 } 284 return (a * inv[bb % mod]) % mod; 285 } 286 287 288 int32_t main() { 289 ios_base::sync_with_stdio(false); 290 cin.tie(0); 291 int x, q; 292 cin >> x >> q >> mod; 293 inv[1] = 1; 294 for (int i = 2; i < MM && i < mod; i++) { 295 inv[i] = mod - inv[mod % i] * (mod / i) % mod; 296 } 297 int y = x; 298 for (int i = 3; i <= K; i += 2) { 299 if (dp[i]) { 300 continue; 301 } 302 for (int j = i; j <= K; j += 2 * i) { 303 dp[j] = i; 304 } 305 } 306 int ans = 1; 307 while (x % 2 == 0) { 308 x /= 2; 309 } 310 for (int i = 3; i <= K; i += 2) { 311 while (x % i == 0) { 312 ans = dv(ans, cnt[i] + 1); 313 ++cnt[i]; 314 ans = mul(ans, cnt[i] + 1); 315 x /= i; 316 } 317 } 318 int f = 1; 319 if (x > 1) { 320 ans = mul(ans, 2); 321 } 322 x = y; 323 for (int i = 0; i < q; ++i) { 324 int d; 325 cin >> d; 326 while (d % 2 == 0) { 327 d /= 2; 328 } 329 int k = d; 330 while (dp[k]) { 331 ans = dv(ans, cnt[dp[k]] + 1); 332 ++cnt[dp[k]]; 333 ans = mul(ans, cnt[dp[k]] + 1); 334 k /= dp[k]; 335 } 336 if (cc) { 337 cout << 0 << '\n'; 338 } else { 339 cout << ans << '\n'; 340 } 341 } 342 return 0; 343 } 344 ``` 345 346 [1848F - Vika and Wiki](/contest/1848/problem/F "Codeforces Round 885 (Div. 2)") 347 348 Idea: [pavlekn](/profile/pavlekn "Candidate Master pavlekn") 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 int MAXN = (1 << 20); 362 363 int a[MAXN]; 364 365 int solve(int n) { 366 if (n == 1) { 367 if (a[0] == 0) { 368 return 0; 369 } else { 370 return 1; 371 } 372 } 373 int fl = true; 374 for (int i = 0; i < n / 2; ++i) { 375 if (a[i] != a[i + n / 2]) { 376 fl = false; 377 } 378 } 379 if (fl) { 380 return solve(n / 2); 381 } 382 for (int i = 0; i < n / 2; ++i) { 383 a[i] ^= a[i + n / 2]; 384 } 385 return n / 2 + solve(n / 2); 386 } 387 388 int32_t main() { 389 int n; 390 scanf("%d", &n); 391 for (int i = 0; i < n; ++i) { 392 scanf("%d", &a[i]); 393 } 394 cout << solve(n) << endl; 395 return 0; 396 } 397 ```