codeforces-scrape

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

1728.md (8929B)


      1 Source: https://codeforces.com/blog/entry/106805
      2 
      3 [1728A - Colored Balls: Revisited](/contest/1728/problem/A "Educational Codeforces Round 135 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int n;
     23     cin >> n;
     24     vector<int> a(n);
     25     for (int &x : a) cin >> x;
     26     cout << max_element(a.begin(), a.end()) - a.begin() + 1 << '\n';
     27   }
     28 }
     29 ```
     30 
     31 [1728B - Best Permutation](/contest/1728/problem/B "Educational Codeforces Round 135 (Rated for Div. 2)")
     32 
     33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (Neon)**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 
     44 using namespace std;
     45 
     46 int main() {
     47   int t;
     48   cin >> t;
     49   while (t--) {
     50     int n;
     51     cin >> n;
     52     vector<int> p(n);
     53     iota(p.begin(), p.end(), 1);
     54     for (int i = n & 1; i < n - 2; i += 2) swap(p[i], p[i + 1]);
     55     for (int &x : p) cout << x << ' ';
     56     cout << '\n';
     57   }
     58 }
     59 ```
     60 
     61 [1728C - Digital Logarithm](/contest/1728/problem/C "Educational Codeforces Round 135 (Rated for Div. 2)")
     62 
     63 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution (awoo)**
     70 
     71 ```
     72 #include <bits/stdc++.h>
     73 
     74 #define forn(i, n) for (int i = 0; i < int(n); i++)
     75 
     76 using namespace std;
     77 
     78 int main() {
     79 	int t;
     80 	scanf("%d", &t);
     81 	forn(_, t){
     82 		int n;
     83 		scanf("%d", &n);
     84 		vector<int> a(n), b(n);
     85 		forn(i, n) scanf("%d", &a[i]);
     86 		forn(i, n) scanf("%d", &b[i]);
     87 		priority_queue<int> qa(a.begin(), a.end());
     88 		priority_queue<int> qb(b.begin(), b.end());
     89 		int ans = 0;
     90 		while (!qa.empty()){
     91 			if (qa.top() == qb.top()){
     92 				qa.pop();
     93 				qb.pop();
     94 				continue;
     95 			}
     96 			++ans;
     97 			if (qa.top() > qb.top()){
     98 				qa.push(to_string(qa.top()).size());
     99 				qa.pop();
    100 			}
    101 			else{
    102 				qb.push(to_string(qb.top()).size());
    103 				qb.pop();
    104 			}
    105 		}
    106 		printf("%d\n", ans);
    107 	}
    108 	return 0;
    109 }
    110 ```
    111 
    112 [1728D - Letter Picking](/contest/1728/problem/D "Educational Codeforces Round 135 (Rated for Div. 2)")
    113 
    114 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    115 
    116 **Tutorial**
    117 
    118 Tutorial is loading...
    119 
    120 **Solution (awoo)**
    121 
    122 ```
    123 #include <bits/stdc++.h>
    124 
    125 #define forn(i, n) for (int i = 0; i < int(n); i++)
    126 
    127 using namespace std;
    128 
    129 int comp(char c, char d){
    130 	return c < d ? -1 : (c > d ? 1 : 0);
    131 }
    132 
    133 int main() {
    134 	int t;
    135 	cin >> t;
    136 	forn(_, t){
    137 		string s;
    138 		cin >> s;
    139 		int n = s.size();
    140 		vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    141 		for (int len = 2; len <= n; len += 2) forn(l, n - len + 1){
    142 			int r = l + len;
    143 			dp[l][r] = 1;
    144 			{
    145 				int res = -1;
    146 				if (dp[l + 1][r - 1] != 0)
    147 					res = max(res, dp[l + 1][r - 1]);
    148 				else
    149 					res = max(res, comp(s[l], s[r - 1]));
    150 				if (dp[l + 2][r] != 0)
    151 					res = max(res, dp[l + 2][r]);
    152 				else
    153 					res = max(res, comp(s[l], s[l + 1]));
    154 				dp[l][r] = min(dp[l][r], res);
    155 			}
    156 			{
    157 				int res = -1;
    158 				if (dp[l + 1][r - 1] != 0)
    159 					res = max(res, dp[l + 1][r - 1]);
    160 				else
    161 					res = max(res, comp(s[r - 1], s[l]));
    162 				if (dp[l][r - 2] != 0)
    163 					res = max(res, dp[l][r - 2]);
    164 				else
    165 					res = max(res, comp(s[r - 1], s[r - 2]));
    166 				dp[l][r] = min(dp[l][r], res);
    167 			}
    168 		}
    169 		if (dp[0][n] == -1)
    170 			cout << "Alice\n";
    171 		else if (dp[0][n] == 0)
    172 			cout << "Draw\n";
    173 		else
    174 			cout << "Bob\n";
    175 	}
    176 	return 0;
    177 }
    178 ```
    179 
    180 [1728E - Red-Black Pepper](/contest/1728/problem/E "Educational Codeforces Round 135 (Rated for Div. 2)")
    181 
    182 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    183 
    184 **Tutorial**
    185 
    186 Tutorial is loading...
    187 
    188 **Solution (awoo)**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 
    193 #define forn(i, n) for (int i = 0; i < int(n); i++)
    194 
    195 using namespace std;
    196 
    197 long long gcd(long long a, long long b, long long& x, long long& y) {
    198 	if (b == 0) {
    199 		x = 1;
    200 		y = 0;
    201 		return a;
    202 	}
    203 	long long x1, y1;
    204 	long long d = gcd(b, a % b, x1, y1);
    205 	x = y1;
    206 	y = x1 - y1 * (a / b);
    207 	return d;
    208 }
    209 
    210 bool find_any_solution(long long a, long long b, long long c, long long &x0, long long &y0, long long &g) {
    211 	g = gcd(abs(a), abs(b), x0, y0);
    212 	if (c % g) {
    213 		return false;
    214 	}
    215 	x0 *= c / g;
    216 	y0 *= c / g;
    217 	if (a < 0) x0 = -x0;
    218 	if (b < 0) y0 = -y0;
    219 	return true;
    220 }
    221 
    222 int main() {
    223 	int n;
    224 	scanf("%d", &n);
    225 	vector<int> a(n), b(n);
    226 	forn(i, n) scanf("%d%d", &a[i], &b[i]);
    227 	long long cur = accumulate(b.begin(), b.end(), 0ll);
    228 	vector<int> difs(n);
    229 	forn(i, n) difs[i] = a[i] - b[i];
    230 	sort(difs.begin(), difs.end(), greater<int>());
    231 	vector<long long> bst(n + 1);
    232 	forn(i, n + 1){
    233 		bst[i] = cur;
    234 		if (i < n)
    235 			cur += difs[i];
    236 	}
    237 	int mx = max_element(bst.begin(), bst.end()) - bst.begin();
    238 	int m;
    239 	scanf("%d", &m);
    240 	forn(_, m){
    241 		int x, y;
    242 		scanf("%d%d", &x, &y);
    243 		long long x0, y0, g;
    244 		if (!find_any_solution(x, y, n, x0, y0, g)){
    245 			puts("-1");
    246 			continue;
    247 		}
    248 		long long l = x * 1ll * y / g;
    249 		long long red = x0 * 1ll * x;
    250 		red = red + (max(0ll, mx - red) + l - 1) / l * l;
    251 		red = red - max(0ll, red - mx) / l * l;
    252 		long long ans = -1;
    253 		if (red <= n) ans = max(ans, bst[red]);
    254 		red -= l;
    255 		if (red >= 0) ans = max(ans, bst[red]);
    256 		printf("%lld\n", ans);
    257 	}
    258 	return 0;
    259 }
    260 ```
    261 
    262 [1728F - Fishermen](/contest/1728/problem/F "Educational Codeforces Round 135 (Rated for Div. 2)")
    263 
    264 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    265 
    266 **Tutorial**
    267 
    268 Tutorial is loading...
    269 
    270 **Solution (BledDest)**
    271 
    272 ```
    273 #include <bits/stdc++.h>     
    274 
    275 using namespace std;
    276 
    277 const int N = 1003;
    278 
    279 int n;
    280 int a[N];
    281 vector<int> g[N * N];
    282 int mt[N];
    283 bool used[N * N];
    284 vector<int> val;
    285 
    286 bool kuhn(int x)
    287 {
    288     if(used[x]) return false;
    289     used[x] = true;
    290     for(auto y : g[x])
    291         if(mt[y] == -1 || kuhn(mt[y]))
    292         {
    293             mt[y] = x;
    294             return true;
    295         }
    296     return false;
    297 }
    298 
    299 int main()
    300 {
    301     cin >> n;
    302     for(int i = 0; i < n; i++) cin >> a[i];
    303     for(int i = 0; i < n; i++)
    304         for(int j = 1; j <= n; j++)
    305             val.push_back(a[i] * j);
    306     sort(val.begin(), val.end());
    307     val.erase(unique(val.begin(), val.end()), val.end());
    308     int v = val.size();
    309     long long ans = 0;
    310     for(int i = 0; i < n; i++)
    311         for(int j = 1; j <= n; j++)
    312         {
    313             int k = lower_bound(val.begin(), val.end(), a[i] * j) - val.begin();
    314             g[k].push_back(i);
    315         }
    316     for(int i = 0; i < n; i++) mt[i] = -1;
    317     for(int i = 0; i < v; i++)
    318     {
    319         if(kuhn(i))
    320         {
    321             ans += val[i];
    322             for(int j = 0; j < v; j++) used[j] = false;
    323         }
    324     }
    325     cout << ans << endl;
    326 }
    327 ```
    328 
    329 [1728G - Illumination](/contest/1728/problem/G "Educational Codeforces Round 135 (Rated for Div. 2)")
    330 
    331 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    332 
    333 **Tutorial**
    334 
    335 Tutorial is loading...
    336 
    337 **Solution (awoo)**
    338 
    339 ```
    340 #include <bits/stdc++.h>
    341 
    342 #define forn(i, n) for (int i = 0; i < int(n); i++)
    343 
    344 using namespace std;
    345 
    346 const int MOD = 998244353;
    347 
    348 int add(int a, int b){
    349 	a += b;
    350 	if (a >= MOD)
    351 		a -= MOD;
    352 	if (a < 0)
    353 		a += MOD;
    354 	return a;
    355 }
    356 
    357 int mul(int a, int b){
    358 	return a * 1ll * b % MOD;
    359 }
    360 
    361 int binpow(int a, int b){
    362 	int res = 1;
    363 	while (b){
    364 		if (b & 1)
    365 			res = mul(res, a);
    366 		a = mul(a, a);
    367 		b >>= 1;
    368 	}
    369 	return res;
    370 }
    371 
    372 int main() {
    373 	int D, n, m;
    374 	
    375 	scanf("%d%d%d", &D, &n, &m);
    376 	
    377 	vector<int> inv(D + 1);
    378 	forn(i, D + 1) inv[i] = binpow(i, MOD - 2);
    379 	
    380 	vector<int> b(n);
    381 	forn(i, n) scanf("%d", &b[i]);
    382 	
    383 	vector<int> a(m);
    384 	forn(i, m) scanf("%d", &a[i]);
    385 	sort(a.begin(), a.end());
    386 	
    387 	int fl = (1 << m) - 1;
    388 	vector<int> ways(1 << m, 1);
    389 	forn(i, m) forn(j, n){
    390 		int d = abs(b[j] - a[i]);
    391 		int mask;
    392 		if (b[j] > a[i]){
    393 			int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
    394 			mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
    395 		}
    396 		else{
    397 			int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
    398 			mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
    399 		}
    400 		ways[mask] = mul(ways[mask], d);
    401 		mask ^= (1 << i);
    402 		ways[mask] = mul(ways[mask], inv[d]);
    403 	}
    404 	
    405 	forn(i, m) for (int mask = fl; mask >= 0; --mask) if ((mask >> i) & 1){
    406 		ways[mask ^ (1 << i)] = mul(ways[mask ^ (1 << i)], ways[mask]);
    407 	}
    408 	
    409 	ways[0] = binpow(D + 1, n);
    410 	forn(mask, 1 << m){
    411 		ways[mask] = mul(ways[mask], __builtin_popcount(mask) & 1 ? MOD - 1 : 1);
    412 	}
    413 	forn(i, m) forn(mask, 1 << m) if (!((mask >> i) & 1)){
    414 		ways[mask ^ (1 << i)] = add(ways[mask ^ (1 << i)], ways[mask]);
    415 	}
    416 	
    417 	int q;
    418 	scanf("%d", &q);
    419 	forn(_, q){
    420 		int x;
    421 		scanf("%d", &x);
    422 		int ans = binpow(D + 1, n + 1);
    423 		forn(i, m){
    424 			int d = abs(x - a[i]);
    425 			int mask;
    426 			if (x > a[i]){
    427 				int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
    428 				mask = fl ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);
    429 			}
    430 			else{
    431 				int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
    432 				mask = fl ^ ((1 << i) - 1) ^ ((1 << l) - 1);
    433 			}
    434 			ans = add(ans, mul(add(ways[mask], -ways[mask ^ (1 << i)]), d));
    435 		}
    436 		printf("%d\n", ans);
    437 	}
    438 	
    439 	return 0;
    440 }
    441 ```