codeforces-scrape

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

1657.md (7055B)


      1 Source: https://codeforces.com/blog/entry/101161
      2 
      3 [1657A - Integer Moves](/contest/1657/problem/A "Educational Codeforces Round 125 (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 x, y;
     23     cin >> x >> y;
     24     int d = x * x + y * y;
     25     int r = 0;
     26     while (r * r < d) ++r;
     27     int ans = 2;
     28     if (r * r == d) ans = 1;
     29     if (x == 0 && y == 0) ans = 0; 
     30     cout << ans << '\n';
     31   }
     32 }
     33 ```
     34 
     35 [1657B - XY Sequence](/contest/1657/problem/B "Educational Codeforces Round 125 (Rated for Div. 2)")
     36 
     37 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (adedalic)**
     44 
     45 ```
     46 fun main() {
     47     repeat(readLine()!!.toInt()) {
     48         val (n, B, x, y) = readLine()!!.split(' ').map { it.toInt() }
     49         var cur = 0L
     50         var ans = 0L
     51         for (i in 1..n) {
     52             cur += if (cur + x <= B) x else -y
     53             ans += cur
     54         }
     55         println(ans)
     56     }
     57 }
     58 ```
     59 
     60 [1657C - Bracket Sequence Deletion](/contest/1657/problem/C "Educational Codeforces Round 125 (Rated for Div. 2)")
     61 
     62 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (vovuh)**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72 
     73 using namespace std;
     74 
     75 int main() {
     76 #ifdef _DEBUG
     77     freopen("input.txt", "r", stdin);
     78 //  freopen("output.txt", "w", stdout);
     79 #endif
     80     
     81     int t;
     82     cin >> t;
     83     while (t--) {
     84         int n;
     85         string s;
     86         cin >> n >> s;
     87         int l = 0;
     88         int cnt = 0;
     89         while (l + 1 < n) {
     90             if (s[l] == '(' || (s[l] == ')' && s[l + 1] == ')')) {
     91                 l += 2;
     92             } else {
     93                 int r = l + 1;
     94                 while (r < n && s[r] != ')') {
     95                     ++r;
     96                 }
     97                 if (r == n) {
     98                     break;
     99                 }
    100                 l = r + 1;
    101             }
    102             ++cnt;
    103         }
    104         cout << cnt << ' ' << n - l << '\n';
    105     }
    106     
    107     return 0;
    108 }
    109 ```
    110 
    111 [1657D - For Gamers. By Gamers.](/contest/1657/problem/D "Educational Codeforces Round 125 (Rated for Div. 2)")
    112 
    113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (awoo)**
    120 
    121 ```
    122 #include <bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    127 
    128 int main(){
    129 	int n, C;
    130 	scanf("%d%d", &n, &C);
    131 	vector<long long> bst(C + 1);
    132 	forn(i, n){
    133 		int c, d, h;
    134 		scanf("%d%d%d", &c, &d, &h);
    135 		bst[c] = max(bst[c], d * 1ll * h);
    136 	}
    137 	for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c)
    138 		bst[xc] = max(bst[xc], bst[c] * (xc / c));
    139 	forn(c, C)
    140 		bst[c + 1] = max(bst[c + 1], bst[c]);
    141 	int m;
    142 	scanf("%d", &m);
    143 	forn(j, m){
    144 		int D;
    145 		long long H;
    146 		scanf("%d%lld", &D, &H);
    147 		int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin();
    148 		if (mn > C) mn = -1;
    149 		printf("%d ", mn);
    150 	}
    151 	puts("");
    152 }
    153 ```
    154 
    155 [1657E - Star MST](/contest/1657/problem/E "Educational Codeforces Round 125 (Rated for Div. 2)")
    156 
    157 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    158 
    159 **Tutorial**
    160 
    161 Tutorial is loading...
    162 
    163 **Solution (awoo)**
    164 
    165 ```
    166 #include <bits/stdc++.h>
    167 
    168 using namespace std;
    169 
    170 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    171 
    172 const int MOD = 998244353;
    173 
    174 int add(int a, int b){
    175 	a += b;
    176 	if (a >= MOD)
    177 		a -= MOD;
    178 	return a;
    179 }
    180 
    181 int mul(int a, int b){
    182 	return a * 1ll * b % MOD;
    183 }
    184 
    185 int binpow(int a, int b){
    186 	int res = 1;
    187 	while (b){
    188 		if (b & 1)
    189 			res = mul(res, a);
    190 		a = mul(a, a);
    191 		b >>= 1;
    192 	}
    193 	return res;
    194 }
    195 
    196 int main(){
    197 	int n, k;
    198 	scanf("%d%d", &n, &k);
    199 	--n;
    200 	vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    201 	vector<vector<int>> C(n + 1);
    202 	forn(i, n + 1){
    203 		C[i].resize(i + 1);
    204 		C[i][0] = C[i][i] = 1;
    205 		for (int j = 1; j < i; ++j)
    206 			C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    207 	}
    208 	dp[0][0] = 1;
    209 	forn(i, k) forn(t, n + 1) {
    210 		int pw = binpow(k - i, t * (t - 1) / 2);
    211 		int step = binpow(k - i, t);
    212 		forn(j, n - t + 1){
    213 			dp[i + 1][j + t] = add(dp[i + 1][j + t], mul(dp[i][j], mul(C[n - j][t], pw)));
    214 			pw = mul(pw, step);
    215 		}
    216 	}
    217 	printf("%d\n", dp[k][n]);
    218 }
    219 ```
    220 
    221 [1657F - Words on Tree](/contest/1657/problem/F "Educational Codeforces Round 125 (Rated for Div. 2)")
    222 
    223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    224 
    225 **Tutorial**
    226 
    227 Tutorial is loading...
    228 
    229 **Solution (awoo)**
    230 
    231 ```
    232 #include <bits/stdc++.h>
    233  
    234 using namespace std;
    235  
    236 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    237  
    238 vector<vector<int>> t;
    239 vector<int> p, h;
    240  
    241 void init(int v){
    242 	for (int u : t[v]) if (u != p[v]){
    243 		p[u] = v;
    244 		h[u] = h[v] + 1;
    245 		init(u);
    246 	}
    247 }
    248  
    249 vector<int> get_path(int v, int u){
    250 	vector<int> l, r;
    251 	while (v != u){
    252 		if (h[v] > h[u]){
    253 			l.push_back(v);
    254 			v = p[v];
    255 		}
    256 		else{
    257 			r.push_back(u);
    258 			u = p[u];
    259 		}
    260 	}
    261 	l.push_back(v);
    262 	while (!r.empty()){
    263 		l.push_back(r.back());
    264 		r.pop_back();
    265 	}
    266 	return l;
    267 }
    268  
    269 vector<vector<int>> g, tg;
    270  
    271 void add_edge(int v, bool vx, int u, bool vy){
    272 	// (val[v] == vx) -> (val[u] == vy)
    273 	g[v * 2 + vx].push_back(u * 2 + vy);
    274 	tg[u * 2 + vy].push_back(v * 2 + vx);
    275 	g[u * 2 + !vy].push_back(v * 2 + !vx);
    276 	tg[v * 2 + !vx].push_back(u * 2 + !vy);
    277 }
    278  
    279 vector<int> ord;
    280 vector<char> used;
    281  
    282 void ts(int v){
    283 	used[v] = true;
    284 	for (int u : g[v]) if (!used[u])
    285 		ts(u);
    286 	ord.push_back(v);
    287 }
    288  
    289 vector<int> clr;
    290 int k;
    291  
    292 void dfs(int v){
    293 	clr[v] = k;
    294 	for (int u : tg[v]) if (clr[u] == -1)
    295 		dfs(u);
    296 }
    297  
    298 int main(){
    299 	cin.tie(0);
    300 	iostream::sync_with_stdio(false);
    301 	
    302 	int n, m;
    303 	cin >> n >> m;
    304 	t.resize(n);
    305 	p.resize(n);
    306 	h.resize(n);
    307 	p[0] = -1;
    308 	forn(i, n - 1){
    309 		int v, u;
    310 		cin >> v >> u;
    311 		--v, --u;
    312 		t[v].push_back(u);
    313 		t[u].push_back(v);
    314 	}
    315 	init(0);
    316 	
    317 	vector<vector<int>> paths(m);
    318 	vector<string> s(m);
    319 	
    320 	vector<pair<char, char>> opts(n, make_pair(-1, -1));
    321 	forn(i, m){
    322 		int v, u;
    323 		cin >> v >> u >> s[i];
    324 		--v, --u;
    325 		paths[i] = get_path(v, u);
    326 		int k = s[i].size();
    327 		assert(int(paths[i].size()) == k);
    328 		forn(j, k) opts[paths[i][j]] = {s[i][j], s[i][k - j - 1]};
    329 	}
    330 	
    331 	int nm = (n + m) * 2;
    332 	g.resize(nm);
    333 	tg.resize(nm);
    334 	forn(i, m){
    335 		int k = s[i].size();
    336 		forn(j, k){
    337 			int v = paths[i][j];
    338 			char c = s[i][j], rc = s[i][k - j - 1];
    339 			char d = opts[v].first, rd = opts[v].second;
    340 			if (d != c) add_edge(v, false, n + i, true);
    341 			if (d != rc) add_edge(v, false, n + i, false);
    342 			if (rd != c) add_edge(v, true, n + i, true);
    343 			if (rd != rc) add_edge(v, true, n + i, false);
    344 		}
    345 	}
    346 	
    347 	used.resize(nm);
    348 	forn(i, nm) if (!used[i]) ts(i);
    349 	clr.resize(nm, -1);
    350 	reverse(ord.begin(), ord.end());
    351 	for (int v : ord) if (clr[v] == -1){
    352 		dfs(v);
    353 		++k;
    354 	}
    355 	forn(i, nm) if (clr[i] == clr[i ^ 1]){
    356 		cout << "NO\n";
    357 		return 0;
    358 	}
    359 	
    360 	cout << "YES\n";
    361 	for (int i = 0; i < 2 * n; i += 2){
    362 		if (opts[i / 2].first == -1)
    363 			cout << 'a';
    364 		else if (clr[i] > clr[i ^ 1])
    365 			cout << opts[i / 2].first;
    366 		else
    367 			cout << opts[i / 2].second;
    368 	}
    369 	cout << "\n";
    370 }
    371 ```