1359.md (11392B)
1 Source: https://codeforces.com/blog/entry/78116 2 3 [1359A - Berland Poker](/contest/1359/problem/A "Educational Codeforces Round 88 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (BledDest)** 12 13 ``` 14 t = int(input()) 15 16 for i in range(t): 17 n, m, k = map(int, input().split()) 18 d = n // k 19 a1 = min(m, d) 20 a2 = (m - a1 + k - 2) // (k - 1) 21 print(a1 - a2) 22 ``` 23 24 **Solution 2 (BledDest)** 25 26 ``` 27 t = int(input()) 28 29 for i in range(t): 30 n, m, k = map(int, input().split()) 31 ans = 0 32 d = n // k 33 for a1 in range(m + 1): 34 for a2 in range(a1 + 1): 35 if(a1 > d): 36 continue 37 if(a1 + a2 > m): 38 continue 39 if(a1 + (k - 1) * a2 < m): 40 continue 41 ans = max(ans, a1 - a2) 42 print(ans) 43 ``` 44 45 [1359B - New Theatre Square](/contest/1359/problem/B "Educational Codeforces Round 88 (Rated for Div. 2)") 46 47 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution (pikmike)** 54 55 ``` 56 t = int(input()) 57 for _ in range(t): 58 n, m, x, y = map(int, input().split()) 59 ans = 0 60 y = min(y, 2 * x) 61 for __ in range(n): 62 s = input() 63 i = 0 64 while i < m: 65 if s[i] == '*': 66 i += 1 67 continue 68 j = i 69 while j + 1 < m and s[j + 1] == '.': 70 j += 1 71 l = j - i + 1 72 ans += l % 2 * x + l // 2 * y 73 i = j + 1 74 print(ans) 75 ``` 76 77 [1359C - Mixing Water](/contest/1359/problem/C "Educational Codeforces Round 88 (Rated for Div. 2)") 78 79 Idea: [adedalic](/profile/adedalic "International Master adedalic") 80 81 **Tutorial** 82 83 So there are two kinds of stops to consider: $k$ hot and $k$ cold cup and $(k + 1)$ hot and $k$ cold cups. 84 85 The first case is trivial: the temperature is always $\frac{h + c}{2}$. In the second case the temperature is always strictly greater than $\frac{h + c}{2}$. Thus, if $t \le \frac{h + c}{2}$, then the answer is $2$. 86 87 Let's show that otherwise the answer is always achieved through the second case. 88 89 The temperature after $(k + 1)$ hot cups and $k$ cold cups is $t_k = \frac{(k + 1) \cdot h + k \cdot c}{2k + 1}$. The claim is that $t_0 \gt t_1 \gt \dots$. Let's prove that by induction. 90 91 **Proof 1** 92 93 $t_0 = h, t_1 = \frac{2 \cdot h + c}{3}$. $c \lt h$, thus $t_0 \gt t_1$. 94 95 Now compare $t_k$ and $t_{k+1}$. 96 97 $t_k \gt t_{k+1}$ $\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} \gt \frac{(k + 2) \cdot h + (k + 1) \cdot c}{2k + 3}$ $\frac{k \cdot (h + c) + h}{2k + 1} \gt \frac{(k + 1) \cdot (h + c) + h}{2k + 3}$ $2k \cdot (k \cdot (h + c) + h) + 3k \cdot (h + c) + 3h \gt 2k \cdot ((k + 1) \cdot (h + c) + h) + (k + 1) \cdot (h + c) + h$ $2k \cdot (k \cdot (h + c) + h - (k + 1) \cdot (h + c) - h) \gt (k + 1) \cdot (h + c) + h - 3k \cdot (h + c) - 3h$ $2k \cdot (-(h + c)) \gt (-2k + 1) \cdot (h + c) - 2h$ $2h \gt (h + c)$ $h \gt c$ 98 99 We can also show that this series converges to $\frac{h + c}{2}$: 100 101 **Proof 2** 102 103 I'm sorry that I'm not proficient with any calculus but my intuition says that it's enough to show that $\forall k~t_k \gt \frac{h + c}{2}$ and $\forall \varepsilon \exists k~t_k \lt \frac{h + c}{2}$ with $k \ge 0$. 104 105 So the first part is: 106 107 $\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} \gt \frac{h + c}{2}$ $\frac{k \cdot (h + c) + h}{2k + 1} \gt \frac{h + c}{2}$ $2k \cdot (h + c) + 2h \gt (2k + 1) \cdot (h + c)$ $2h \gt h + c$ $h \gt c$ 108 109 And the second part is: 110 111 $\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} \lt \frac{h + c}{2} + \varepsilon$ $\frac{k \cdot (h + c) + h}{2k + 1} \lt \frac{h + c}{2} + \varepsilon$ $2k \cdot (h + c) + 2h \lt (2k + 1) \cdot (h + c) + (2k + 1) \cdot \varepsilon$ $2h \lt (h + c) + (2k + 1) \cdot \varepsilon$ $h \lt c + (2k + 1) \cdot \varepsilon$ $\frac{h - c}{\varepsilon} \lt 2k + 1$ 112 113 So that claim makes us see that for any $t$ greater than $\frac{h + c}{2}$ the answer is always achieved from the second case. 114 115 That allows us to find such $k$, that the value of $t_k$ is exactly $t$. However, such $k$ might not be integer. $\frac{(k + 1) \cdot h + k \cdot c}{2k + 1} = t \leftrightarrow$ $\frac{k \cdot (h + c) + h}{2k + 1} = t \leftrightarrow$ $k \cdot (h + c) + h = 2kt + t \leftrightarrow$ $k \cdot (h + c - 2t) = t - h \leftrightarrow$ $k = \frac{t - h}{h + c - 2t}$. 116 117 The only thing left is to compare which side is better to round $k$ to. It seems some implementations with float numbers might fail due to precision errors. However, it's possible to do these calculations completely in integers. 118 119 Let's actually rewrite that so that the denominator is always positive $k = \frac{h - t}{2t - h - c}$. Now we can round this value down and compare $k$ and $k + 1$. 120 121 So the optimal value is $k$ if $|\frac{k \cdot (h + c) + h}{2k + 1} - t| \le |\frac{(k + 1) \cdot (h + c) + h}{2k + 3} - t|$. So $|(k \cdot (h + c) + h) - t \cdot (2k + 1)| \cdot (2k + 3) \le |((k + 1) \cdot (h + c) + h) - t \cdot (2k + 3)| \cdot (2k + 1)$. Otherwise, the answer is $k + 1$. 122 123 You can also find the optimal $k$ with binary search but the formulas are exactly the same and you have to rely on monotonosity as well. Also, these formulas can get you the better understanding for the upper bound of the answer. 124 125 Overall complexity: $O(1)$ or $O(\log h)$ per testcase. 126 127 **Solution (pikmike)** 128 129 ``` 130 #include <bits/stdc++.h> 131 132 #define forn(i, n) for (int i = 0; i < int(n); i++) 133 134 using namespace std; 135 136 int main() { 137 int tc; 138 scanf("%d", &tc); 139 forn(_, tc){ 140 int h, c, t; 141 scanf("%d%d%d", &h, &c, &t); 142 if (h + c - 2 * t >= 0) 143 puts("2"); 144 else{ 145 int a = h - t; 146 int b = 2 * t - c - h; 147 int k = 2 * (a / b) + 1; 148 long long val1 = abs(k / 2 * 1ll * c + (k + 1) / 2 * 1ll * h - t * 1ll * k); 149 long long val2 = abs((k + 2) / 2 * 1ll * c + (k + 3) / 2 * 1ll * h - t * 1ll * (k + 2)); 150 printf("%d\n", val1 * (k + 2) <= val2 * k ? k : k + 2); 151 } 152 } 153 return 0; 154 } 155 ``` 156 157 [1359D - Yet Another Yet Another Task](/contest/1359/problem/D "Educational Codeforces Round 88 (Rated for Div. 2)") 158 159 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Solution (pikmike)** 166 167 ``` 168 #include <bits/stdc++.h> 169 170 #define forn(i, n) for (int i = 0; i < int(n); i++) 171 172 using namespace std; 173 174 const int INF = 1e9; 175 176 int main() { 177 int n; 178 scanf("%d", &n); 179 vector<int> a(n); 180 forn(i, n) scanf("%d", &a[i]); 181 long long ans = 0; 182 forn(mx, 31){ 183 long long cur = 0; 184 long long best = 0; 185 forn(i, n){ 186 int val = (a[i] > mx ? -INF : a[i]); 187 cur += val; 188 best = min(best, cur); 189 ans = max(ans, (cur - best) - mx); 190 } 191 } 192 printf("%lld\n", ans); 193 return 0; 194 } 195 ``` 196 197 [1359E - Modular Stability](/contest/1359/problem/E "Educational Codeforces Round 88 (Rated for Div. 2)") 198 199 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 200 201 **Tutorial** 202 203 Tutorial is loading... 204 205 **Solution (BledDest)** 206 207 ``` 208 #include<bits/stdc++.h> 209 210 using namespace std; 211 212 const int N = 500043; 213 const int MOD = 998244353; 214 215 int fact[N]; 216 217 int add(int x, int y) 218 { 219 x += y; 220 while(x >= MOD) x -= MOD; 221 while(x < 0) x += MOD; 222 return x; 223 } 224 225 int mul(int x, int y) 226 { 227 return (x * 1ll * y) % MOD; 228 } 229 230 int binpow(int x, int y) 231 { 232 int z = 1; 233 while(y > 0) 234 { 235 if(y % 2 == 1) 236 z = mul(z, x); 237 x = mul(x, x); 238 y /= 2; 239 } 240 return z; 241 } 242 243 int inv(int x) 244 { 245 return binpow(x, MOD - 2); 246 } 247 248 int divide(int x, int y) 249 { 250 return mul(x, inv(y)); 251 } 252 253 void precalc() 254 { 255 fact[0] = 1; 256 for(int i = 1; i < N; i++) 257 fact[i] = mul(i, fact[i - 1]); 258 } 259 260 int C(int n, int k) 261 { 262 if(k > n) return 0; 263 return divide(fact[n], mul(fact[n - k], fact[k])); 264 } 265 266 int main() 267 { 268 int n, k; 269 cin >> n >> k; 270 int ans = 0; 271 precalc(); 272 for(int i = 1; i <= n; i++) 273 { 274 int d = n / i; 275 ans = add(ans, C(d - 1, k - 1)); 276 } 277 cout << ans << endl; 278 } 279 ``` 280 281 [1359F - RC Kaboom Show](/contest/1359/problem/F "Educational Codeforces Round 88 (Rated for Div. 2)") 282 283 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 284 285 **Tutorial** 286 287 Tutorial is loading... 288 289 **Solution (pikmike)** 290 291 ``` 292 #include <bits/stdc++.h> 293 294 #define forn(i, n) for (int i = 0; i < int(n); i++) 295 #define x first 296 #define y second 297 298 using namespace std; 299 300 const double INF = 1e13; 301 302 struct line{ 303 int A, B, C; 304 line(){} 305 line(int x1, int y1, int x2, int y2){ 306 A = y1 - y2; 307 B = x2 - x1; 308 C = -A * x1 - B * y1; 309 // A is guaranteed to be non-zero 310 if (A < 0) A = -A, B = -B, C = -C; 311 int g = __gcd(A, __gcd(abs(B), abs(C))); 312 A /= g, B /= g, C /= g; 313 } 314 }; 315 316 bool operator ==(const line &a, const line &b){ 317 return a.A == b.A && a.B == b.B && a.C == b.C; 318 } 319 320 double x; 321 322 bool operator <(const line &a, const line &b){ 323 double val1 = (-a.A * x - a.C) / a.B; 324 double val2 = (-b.A * x - b.C) / b.B; 325 return val1 < val2; 326 } 327 328 struct car{ 329 int x, y, dx, dy, s; 330 line l; 331 double vx, vy; 332 }; 333 334 int n; 335 vector<car> a(n); 336 337 long long det(int a, int b, int c, int d){ 338 return a * 1ll * d - b * 1ll * c; 339 } 340 341 bool inter(const line &a, const line &b, long long &D, long long &Dx, long long &Dy){ 342 D = det(a.A, a.B, b.A, b.B); 343 if (D == 0) return false; 344 Dx = -det(a.C, a.B, b.C, b.B); 345 Dy = -det(a.A, a.C, b.A, b.C); 346 return true; 347 } 348 349 int sg(int x){ 350 return x < 0 ? -1 : 1; 351 } 352 353 int sg(long long a, long long b, int c){ 354 // sign of a/b-c 355 if (b < 0) a = -a, b = -b; 356 return a - c * b < 0 ? -1 : (a - c * b > 0); 357 } 358 359 bool inter(int i, int j, double &len){ 360 if (i == -1 || j == -1) 361 return false; 362 long long D, Dx, Dy; 363 if (!inter(a[i].l, a[j].l, D, Dx, Dy)) 364 return false; 365 if (sg(Dx, D, a[i].x) != 0 && sg(a[i].dx) != sg(Dx, D, a[i].x)) 366 return false; 367 if (sg(Dx, D, a[j].x) != 0 && sg(a[j].dx) != sg(Dx, D, a[j].x)) 368 return false; 369 double x = Dx / double(D); 370 double y = Dy / double(D); 371 double di = (a[i].x - x) * (a[i].x - x) + (a[i].y - y) * (a[i].y - y); 372 double dj = (a[j].x - x) * (a[j].x - x) + (a[j].y - y) * (a[j].y - y); 373 return len * len >= di / a[i].s && len * len >= dj / a[j].s; 374 } 375 376 vector<set<pair<line, int>>::iterator> del; 377 set<pair<line, int>> q; 378 379 void get_neighbours(int i, int &l, int &r){ 380 l = r = -1; 381 auto it = q.lower_bound({a[i].l, -1}); 382 if (it != q.end()) 383 r = it->y; 384 if (!q.empty() && it != q.begin()){ 385 --it; 386 l = it->y; 387 } 388 } 389 390 bool check(double t){ 391 vector<pair<double, pair<int, int>>> cur; 392 del.resize(n); 393 forn(i, n){ 394 double x1 = a[i].x; 395 double x2 = a[i].x + a[i].vx * t; 396 if (x1 > x2) swap(x1, x2); 397 cur.push_back({x1, {i, 0}}); 398 cur.push_back({x2, {i, 1}}); 399 } 400 q.clear(); 401 402 sort(cur.begin(), cur.end()); 403 for (auto &qr : cur){ 404 x = qr.x; 405 int i = qr.y.x; 406 int l, r; 407 408 if (qr.y.y == 0){ 409 get_neighbours(i, l, r); 410 411 if (r != -1 && a[i].l == a[r].l) 412 return true; 413 if (inter(i, l, t)) 414 return true; 415 if (inter(i, r, t)) 416 return true; 417 418 del[i] = q.insert({a[i].l, i}).x; 419 } 420 else{ 421 q.erase(del[i]); 422 get_neighbours(i, l, r); 423 424 if (inter(l, r, t)) 425 return true; 426 } 427 } 428 return false; 429 } 430 431 int main() { 432 scanf("%d", &n); 433 a.resize(n); 434 forn(i, n){ 435 scanf("%d%d%d%d%d", &a[i].x, &a[i].y, &a[i].dx, &a[i].dy, &a[i].s); 436 a[i].l = line(a[i].x, a[i].y, a[i].x + a[i].dx, a[i].y + a[i].dy); 437 double d = sqrt(a[i].dx * a[i].dx + a[i].dy * a[i].dy); 438 a[i].vx = a[i].dx / d * a[i].s; 439 a[i].vy = a[i].dy / d * a[i].s; 440 a[i].s *= a[i].s; 441 } 442 double l = 0, r = INF; 443 bool ok = false; 444 forn(_, 100){ 445 double m = (l + r) / 2; 446 if (check(m)){ 447 ok = true; 448 r = m; 449 } 450 else{ 451 l = m; 452 } 453 } 454 if (!ok) 455 puts("No show :("); 456 else 457 printf("%.15lf\n", l); 458 return 0; 459 } 460 ```