codeforces-scrape

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

1409.md (8339B)


      1 Source: https://codeforces.com/blog/entry/82284
      2 
      3 I'm so thankful to all testers, especially to [Gassa](/profile/Gassa "Grandmaster Gassa") and [Rox](/profile/Rox "Candidate Master Rox") for their invaluable help!
      4 
      5 [1409A - Yet Another Two Integers Problem](/contest/1409/problem/A "Codeforces Round 667 (Div. 3)")
      6 
      7 Idea: [vovuh](/profile/vovuh "Master vovuh")
      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 int main() {
     21 #ifdef _DEBUG
     22 	freopen("input.txt", "r", stdin);
     23 //	freopen("output.txt", "w", stdout);
     24 #endif
     25 	
     26 	int t;
     27 	cin >> t;
     28 	while (t--) {
     29 		int a, b;
     30 		cin >> a >> b;
     31 		cout << (abs(a - b) + 9) / 10 << endl;
     32 	}
     33 	
     34 	return 0;
     35 }
     36 ```
     37 
     38 [1409B - Minimum Product](/contest/1409/problem/B "Codeforces Round 667 (Div. 3)")
     39 
     40 Idea: [vovuh](/profile/vovuh "Master vovuh")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int main() {
     54 #ifdef _DEBUG
     55 	freopen("input.txt", "r", stdin);
     56 //	freopen("output.txt", "w", stdout);
     57 #endif
     58 	
     59 	int t;
     60 	cin >> t;
     61 	while (t--) {
     62 		int a, b, x, y, n;
     63 		cin >> a >> b >> x >> y >> n;
     64 		long long ans = 1e18;
     65 		for (int i = 0; i < 2; ++i) {
     66 			int da = min(n, a - x);
     67 			int db = min(n - da, b - y);
     68 			ans = min(ans, (a - da) * 1ll * (b - db));
     69 			swap(a, b);
     70 			swap(x, y);
     71 		}
     72 		cout << ans << endl;
     73 	}
     74 	
     75 	return 0;
     76 }
     77 ```
     78 
     79 [1409C - Yet Another Array Restoration](/contest/1409/problem/C "Codeforces Round 667 (Div. 3)")
     80 
     81 Idea: [vovuh](/profile/vovuh "Master vovuh")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution (Gassa)**
     88 
     89 ```
     90 // Author: Ivan Kazmenko ([email protected])
     91 module solution;
     92 import std.algorithm;
     93 import std.conv;
     94 import std.range;
     95 import std.stdio;
     96 import std.string;
     97 
     98 void main ()
     99 {
    100 	auto tests = readln.strip.to !(int);
    101 	foreach (test; 0..tests)
    102 	{
    103 		int n, x, y;
    104 		readf !(" %s %s %s") (n, x, y);
    105 		auto answer = int.max.repeat (n).array;
    106 		foreach (start; 1..51)
    107 		{
    108 			foreach (d; 1..51)
    109 			{
    110 				auto a = iota (start, start + d * n, d).array;
    111 				if (a.canFind (x) && a.canFind (y))
    112 				{
    113 					if (answer.back > a.back)
    114 					{
    115 						answer = a;
    116 					}
    117 				}
    118 			}
    119 		}
    120 		writefln !("%(%s %)") (answer);
    121 	}
    122 }
    123 ```
    124 
    125 **Solution (vovuh)**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 
    130 using namespace std;
    131 
    132 int main() {
    133 #ifdef _DEBUG
    134 	freopen("input.txt", "r", stdin);
    135 //	freopen("output.txt", "w", stdout);
    136 #endif
    137 	
    138 	int t;
    139 	cin >> t;
    140 	while (t--) {
    141 		int n, x, y;
    142 		cin >> n >> x >> y;
    143 		vector<int> ans;
    144 		for (int d = 1; d <= y - x; ++d) {
    145 			if ((y - x) % d != 0) continue;
    146 			vector<int> res;
    147 			bool foundx = false;
    148 			int cur = y;
    149 			int need = n;
    150 			while (cur >= 1 && need > 0) {
    151 				res.push_back(cur);
    152 				foundx |= cur == x;
    153 				--need;
    154 				cur -= d;
    155 			}
    156 			cur = y;
    157 			while (need > 0) {
    158 				cur += d;
    159 				res.push_back(cur);
    160 				--need;
    161 			}
    162 			sort(res.begin(), res.end());
    163 			if (need == 0 && foundx) {
    164 				if (ans.empty() || ans.back() > res.back()) {
    165 					ans = res;
    166 				}
    167 			}
    168 		}
    169 		assert(!ans.empty());
    170 		for (auto it : ans) cout << it << " ";
    171 		cout << endl;
    172 		
    173 	}
    174 	
    175 	return 0;
    176 }
    177 ```
    178 
    179 **Solution (Rox)**
    180 
    181 ```
    182 #include <bits/stdc++.h>
    183 
    184 using namespace std;
    185 
    186 int main() {
    187     int tcs;
    188     cin >> tcs;
    189 
    190     while (tcs--) {
    191         int n, x, y;
    192         cin >> n >> x >> y;
    193         int diff = y - x;
    194         for (int delta = 1; delta <= diff; ++delta) {
    195             if (diff % delta) continue;
    196             if (diff / delta + 1 > n) continue;
    197             int k = min((y - 1) / delta, n - 1);
    198             int a0 = y - k * delta;
    199             for (int i = 0; i < n; ++i) {
    200                 cout << (a0 + i * delta) << ' ';
    201             }
    202             cout << endl;
    203             break;
    204         }
    205     }
    206 }
    207 ```
    208 
    209 [1409D - Decrease the Sum of Digits](/contest/1409/problem/D "Codeforces Round 667 (Div. 3)")
    210 
    211 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 
    222 using namespace std;
    223 
    224 int sum(long long n) {
    225 	int res = 0;
    226 	while (n > 0) {
    227 		res += n % 10;
    228 		n /= 10;
    229 	}
    230 	return res;
    231 }
    232 
    233 int main() {
    234 #ifdef _DEBUG
    235 	freopen("input.txt", "r", stdin);
    236 //	freopen("output.txt", "w", stdout);
    237 #endif
    238 	
    239 	int t;
    240 	cin >> t;
    241 	while (t--) {
    242 		long long n;
    243 		int s;
    244 		cin >> n >> s;
    245 		long long ans = 0;
    246 		if (sum(n) <= s) {
    247 			cout << 0 << endl;
    248 			continue;
    249 		}
    250 		long long pw = 1;
    251 		for (int i = 0; i < 18; ++i) {
    252 			int digit = (n / pw) % 10;
    253 			long long add = pw * ((10 - digit) % 10);
    254 			n += add;
    255 			ans += add;
    256 			if (sum(n) <= s) {
    257 				break;
    258 			}
    259 			pw *= 10;
    260 		}
    261 		cout << ans << endl;
    262 	}
    263 	
    264 	return 0;
    265 }
    266 ```
    267 
    268 [1409E - Two Platforms](/contest/1409/problem/E "Codeforces Round 667 (Div. 3)")
    269 
    270 Idea: [vovuh](/profile/vovuh "Master vovuh")
    271 
    272 **Tutorial**
    273 
    274 Tutorial is loading...
    275 
    276 **Solution**
    277 
    278 ```
    279 #include <bits/stdc++.h>
    280 
    281 using namespace std;
    282 
    283 int main() {
    284 #ifdef _DEBUG
    285 	freopen("input.txt", "r", stdin);
    286 //	freopen("output.txt", "w", stdout);
    287 #endif
    288 	
    289 	int t;
    290 	cin >> t;
    291 	while (t--) {
    292 		int n, k;
    293 		cin >> n >> k;
    294 		vector<int> x(n), y(n);
    295 		for (auto &it : x) cin >> it;
    296 		for (auto &it : y) cin >> it;
    297 		sort(x.begin(), x.end());
    298 		int j = n - 1;
    299 		vector<int> l(n), r(n);
    300 		for (int i = n - 1; i >= 0; --i) {
    301 			while (x[j] - x[i] > k) --j;
    302 			r[i] = j - i + 1;
    303 			if (i + 1 < n) r[i] = max(r[i], r[i + 1]);
    304 		}
    305 		j = 0;
    306 		for (int i = 0; i < n; ++i) {
    307 			while (x[i] - x[j] > k) ++j;
    308 			l[i] = i - j + 1;
    309 			if (i > 0) l[i] = max(l[i], l[i - 1]);
    310 		}
    311 		int ans = 1;
    312 		for (int i = 0; i < n - 1; ++i) {
    313 			ans = max(ans, r[i + 1] + l[i]);
    314 		}
    315 		cout << ans << endl;
    316 	}
    317 	
    318 	return 0;
    319 }
    320 ```
    321 
    322 [1409F - Subsequences of Length Two](/contest/1409/problem/F "Codeforces Round 667 (Div. 3)")
    323 
    324 Idea: [vovuh](/profile/vovuh "Master vovuh")
    325 
    326 **Tutorial**
    327 
    328 Tutorial is loading...
    329 
    330 **Solution**
    331 
    332 ```
    333 #include <bits/stdc++.h>
    334 
    335 using namespace std;
    336 
    337 const int INF = 1e9;
    338 
    339 int main() {
    340 #ifdef _DEBUG
    341 	freopen("input.txt", "r", stdin);
    342 //	freopen("output.txt", "w", stdout);
    343 #endif
    344 	
    345 	int n, k;
    346 	string s, t;
    347 	cin >> n >> k >> s >> t;
    348 	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, -INF)));
    349 	dp[0][0][0] = 0;
    350 	for (int i = 0; i < n; ++i) {
    351 		for (int ck = 0; ck <= k; ++ck) {
    352 			for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
    353 				if (dp[i][ck][cnt0] == -INF) continue;
    354 				int e0 = s[i] == t[0];
    355 				int e1 = s[i] == t[1];
    356 				int e01 = t[0] == t[1];
    357 				
    358 				dp[i + 1][ck][cnt0 + e0] = max(dp[i + 1][ck][cnt0 + e0], dp[i][ck][cnt0] + (e1 ? cnt0 : 0));
    359 				
    360 				if (ck < k) {
    361 					dp[i + 1][ck + 1][cnt0 + 1] = max(dp[i + 1][ck + 1][cnt0 + 1], dp[i][ck][cnt0] + (e01 ? cnt0 : 0));
    362 					dp[i + 1][ck + 1][cnt0 + e01] = max(dp[i + 1][ck + 1][cnt0 + e01], dp[i][ck][cnt0] + cnt0);
    363 				}
    364 			}
    365 		}
    366 	}
    367 	
    368 	int ans = 0;
    369 	for (int ck = 0; ck <= k; ++ck) {
    370 		for (int cnt0 = 0; cnt0 <= n; ++cnt0) {
    371 			ans = max(ans, dp[n][ck][cnt0]);
    372 		}
    373 	}
    374 	
    375 	cout << ans << endl;
    376 	
    377 	return 0;
    378 }
    379 ```
    380 
    381 **Solution (Gassa, greedy, O(n^4))**
    382 
    383 ```
    384 // Author: Ivan Kazmenko ([email protected])
    385 module solution;
    386 import std.algorithm;
    387 import std.conv;
    388 import std.range;
    389 import std.stdio;
    390 import std.string;
    391 
    392 void main ()
    393 {
    394 	int n, k;
    395 	while (readf !(" %s %s") (n, k) > 0)
    396 	{
    397 		readln;
    398 		auto s0 = readln.strip;
    399 		auto t = readln.strip;
    400 		auto s = s0.dup;
    401 		int res = 0;
    402 		foreach (b0; 0..k + 1)
    403 		{
    404 			auto e0 = k - b0;
    405 loop_x0:
    406 			foreach (x0; 0..b0 + 1)
    407 			{
    408 loop_y0:
    409 				foreach (y0; 0..e0 + 1)
    410 				{
    411 					int b = b0;
    412 					int e = e0;
    413 					int x = x0;
    414 					int y = y0;
    415 					s[] = s0[];
    416 					for (int i = 0; i < n && b; i++)
    417 					{
    418 						if (s[i] == t[0])
    419 						{
    420 						}
    421 						else if (s[i] != t[1])
    422 						{
    423 							s[i] = t[0];
    424 							b -= 1;
    425 						}
    426 						else if (x > 0)
    427 						{
    428 							s[i] = t[0];
    429 							x -= 1;
    430 							b -= 1;
    431 						}
    432 					}
    433 
    434 					for (int j = n - 1; j >= 0 && e; j--)
    435 					{
    436 						if (s[j] == t[1])
    437 						{
    438 						}
    439 						else if (s[j] != t[0])
    440 						{
    441 							s[j] = t[1];
    442 							e -= 1;
    443 						}
    444 						else if (y > 0)
    445 						{
    446 							s[j] = t[1];
    447 							y -= 1;
    448 							e -= 1;
    449 						}
    450 					}
    451 
    452 					int cur = 0;
    453 					int add = 0;
    454 					for (int i = 0; i < n; i++)
    455 					{
    456 						if (s[i] == t[1])
    457 						{
    458 							cur += add;
    459 						}
    460 						if (s[i] == t[0])
    461 						{
    462 							add += 1;
    463 						}
    464 					}
    465 					res = max (res, cur);
    466 
    467 					if (x > 0)
    468 					{
    469 						break loop_x0;
    470 					}
    471 					if (y > 0)
    472 					{
    473 						break loop_y0;
    474 					}
    475 				}
    476 			}
    477 		}
    478 
    479 		writeln (res);
    480 	}
    481 }
    482 ```