codeforces-scrape

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

1525.md (8036B)


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