codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```