codeforces-scrape

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

1296.md (7765B)


      1 Source: https://codeforces.com/blog/entry/73627
      2 
      3 [1296A - Array with Odd Sum](/contest/1296/problem/A "Codeforces Round 617 (Div. 3)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20 	freopen("input.txt", "r", stdin);
     21 //	freopen("output.txt", "w", stdout);
     22 #endif
     23 	
     24 	int t;
     25 	cin >> t;
     26 	while (t--) {
     27 		int n;
     28 		cin >> n;
     29 		int sum = 0;
     30 		bool odd = false, even = false;
     31 		for (int i = 0; i < n; ++i) {
     32 			int x;
     33 			cin >> x;
     34 			sum += x;
     35 			odd |= x % 2 != 0;
     36 			even |= x % 2 == 0;
     37 		}
     38 		if (sum % 2 != 0 || (odd && even)) cout << "YES" << endl;
     39 		else cout << "NO" << endl;
     40 	}
     41 	
     42 	return 0;
     43 }
     44 ```
     45 
     46 [1296B - Food Buying](/contest/1296/problem/B "Codeforces Round 617 (Div. 3)")
     47 
     48 Idea: [vovuh](/profile/vovuh "Master vovuh")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58 
     59 using namespace std;
     60 
     61 int main() {
     62 #ifdef _DEBUG
     63 	freopen("input.txt", "r", stdin);
     64 //	freopen("output.txt", "w", stdout);
     65 #endif
     66 	
     67 	int t;
     68 	cin >> t;
     69 	while (t--) {
     70 		int s;
     71 		cin >> s;
     72 		int ans = 0;
     73 		int pw = 1000 * 1000 * 1000;
     74 		while (s > 0) {
     75 			while (s < pw) pw /= 10;
     76 			ans += pw;
     77 			s -= pw - pw / 10;
     78 		}
     79 		cout << ans << endl;
     80 	}
     81 	
     82 	return 0;
     83 }
     84 ```
     85 
     86 [1296C - Yet Another Walking Robot](/contest/1296/problem/C "Codeforces Round 617 (Div. 3)")
     87 
     88 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98 
     99 using namespace std;
    100 
    101 int main() {
    102 #ifdef _DEBUG
    103 	freopen("input.txt", "r", stdin);
    104 //	freopen("output.txt", "w", stdout);
    105 #endif
    106 	
    107 	int t;
    108 	cin >> t;
    109 	while (t--) {
    110 		int n;
    111 		string s;
    112 		cin >> n >> s;
    113 		int l = -1, r = n;
    114 		map<pair<int, int>, int> vis;
    115 		pair<int, int> cur = {0, 0};
    116 		vis[cur] = 0;
    117 		for (int i = 0; i < n; ++i) {
    118 			if (s[i] == 'L') --cur.first;
    119 			if (s[i] == 'R') ++cur.first;
    120 			if (s[i] == 'U') ++cur.second;
    121 			if (s[i] == 'D') --cur.second;
    122 			if (vis.count(cur)) {
    123 				if (i - vis[cur] + 1 < r - l + 1) {
    124 					l = vis[cur];
    125 					r = i;
    126 				}
    127 			}
    128 			vis[cur] = i + 1;
    129 		}
    130 		if (l == -1) {
    131 			cout << -1 << endl;
    132 		} else {
    133 			cout << l + 1 << " " << r + 1 << endl;
    134 		}
    135 	}
    136 	
    137 	return 0;
    138 }
    139 ```
    140 
    141 [1296D - Fight with Monsters](/contest/1296/problem/D "Codeforces Round 617 (Div. 3)")
    142 
    143 Inspiration: [300iq](/profile/300iq "Legendary Grandmaster 300iq"), idea: [vovuh](/profile/vovuh "Master vovuh")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153 
    154 using namespace std;
    155 
    156 int main() {
    157 #ifdef _DEBUG
    158 	freopen("input.txt", "r", stdin);
    159 //	freopen("output.txt", "w", stdout);
    160 #endif
    161 	
    162 	int n, a, b, k;
    163 	cin >> n >> a >> b >> k;
    164 	vector<int> h(n);
    165 	for (int i = 0; i < n; ++i) {
    166 		cin >> h[i];
    167 		h[i] %= a + b;
    168 		if (h[i] == 0) h[i] += a + b;
    169 		h[i] = ((h[i] + a - 1) / a) - 1;
    170 	}
    171 	sort(h.begin(), h.end());
    172 	int ans = 0;
    173 	for (int i = 0; i < n; ++i) {
    174 		if (k - h[i] < 0) break;
    175 		++ans;
    176 		k -= h[i];
    177 	}
    178 	
    179 	cout << ans << endl;
    180 	
    181 	return 0;
    182 }
    183 ```
    184 
    185 [1296E1 - String Coloring (easy version)](/contest/1296/problem/E1 "Codeforces Round 617 (Div. 3)")
    186 
    187 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    188 
    189 **Tutorial**
    190 
    191 Tutorial is loading...
    192 
    193 **Solution (dp)**
    194 
    195 ```
    196 #include <bits/stdc++.h>
    197 
    198 using namespace std;
    199 
    200 const int N = 222;
    201 const int AL = 26;
    202 
    203 bool dp[N][AL][AL];
    204 pair<pair<int, int>, int> p[N][AL][AL];
    205 
    206 int main() {
    207 #ifdef _DEBUG
    208 	freopen("input.txt", "r", stdin);
    209 //	freopen("output.txt", "w", stdout);
    210 #endif
    211 	
    212 	int n;
    213 	string s;
    214 	cin >> n >> s;
    215 	dp[0][0][0] = 1;
    216 	for (int i = 0; i < n; ++i) {
    217 		int c = s[i] - 'a';
    218 		for (int c1 = 0; c1 < AL; ++c1) {
    219 			for (int c2 = 0; c2 < AL; ++c2) {
    220 				if (!dp[i][c1][c2]) continue;
    221 				if (c >= c1) {
    222 					dp[i + 1][c][c2] = 1;
    223 					p[i + 1][c][c2] = make_pair(make_pair(c1, c2), 0);
    224 				}
    225 				if (c >= c2) {
    226 					dp[i + 1][c1][c] = 1;
    227 					p[i + 1][c1][c] = make_pair(make_pair(c1, c2), 1);	
    228 				}
    229 			}
    230 		}
    231 	}
    232 	
    233 	int x = -1, y = -1;
    234 	for (int c1 = 0; c1 < AL; ++c1) {
    235 		for (int c2 = 0; c2 < AL; ++c2) {
    236 			if (dp[n][c1][c2]) {
    237 				x = c1, y = c2;
    238 			}
    239 		}
    240 	}
    241 	
    242 	if (x == -1) {
    243 		cout << "NO" << endl;
    244 		return 0;
    245 	}
    246 	
    247 	string res;
    248 	for (int i = n; i > 0; --i) {
    249 		int prvx = p[i][x][y].first.first;
    250 		int prvy = p[i][x][y].first.second;
    251 		if (p[i][x][y].second) res += '1';
    252 		else res += '0';
    253 		x = prvx;
    254 		y = prvy;
    255 	}
    256 	
    257 	reverse(res.begin(), res.end());
    258 	cout << "YES" << endl << res << endl;
    259 	
    260 	return 0;
    261 }
    262 ```
    263 
    264 **Solution (greedy)**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 
    269 using namespace std;
    270 
    271 int main() {
    272 #ifdef _DEBUG
    273 	freopen("input.txt", "r", stdin);
    274 //	freopen("output.txt", "w", stdout);
    275 #endif
    276 	
    277 	int n;
    278 	string s;
    279 	cin >> n >> s;
    280 	string res;
    281 	char lst0 = 'a', lst1 = 'a';
    282 	for (int i = 0; i < n; ++i) {
    283 		if (s[i] >= lst0) {
    284 			res += '0';
    285 			lst0 = s[i];
    286 		} else if (s[i] >= lst1) {
    287 			res += '1';
    288 			lst1 = s[i];
    289 		} else {
    290 			cout << "NO" << endl;
    291 			return 0;
    292 		}
    293 	}
    294 	
    295 	cout << "YES" << endl << res << endl;
    296 	
    297 	return 0;
    298 }
    299 ```
    300 
    301 [1296E2 - String Coloring (hard version)](/contest/1296/problem/E2 "Codeforces Round 617 (Div. 3)")
    302 
    303 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    304 
    305 **Tutorial**
    306 
    307 Tutorial is loading...
    308 
    309 **Solution**
    310 
    311 ```
    312 #include <bits/stdc++.h>
    313 
    314 using namespace std;
    315 
    316 int main() {
    317 #ifdef _DEBUG
    318 	freopen("input.txt", "r", stdin);
    319 //	freopen("output.txt", "w", stdout);
    320 #endif
    321 	
    322 	int n;
    323 	string s;
    324 	cin >> n >> s;
    325 	
    326 	vector<int> maxdp(26);
    327 	vector<int> dp(n, 1);
    328 	for (int i = 0; i < n; ++i) {
    329 		for (int c = 25; c > s[i] - 'a'; --c) {
    330 			dp[i] = max(dp[i], maxdp[c] + 1);
    331 		}
    332 		maxdp[s[i] - 'a'] =  max(maxdp[s[i] - 'a'], dp[i]);
    333 	}
    334 	
    335 	cout << *max_element(maxdp.begin(), maxdp.end()) << endl;
    336 	for (int i = 0; i < n; ++i) cout << dp[i] << " ";
    337 	cout << endl;
    338 	
    339 	return 0;
    340 }
    341 ```
    342 
    343 [1296F - Berland Beauty](/contest/1296/problem/F "Codeforces Round 617 (Div. 3)")
    344 
    345 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    346 
    347 **Tutorial**
    348 
    349 Tutorial is loading...
    350 
    351 **Solution**
    352 
    353 ```
    354 #include <bits/stdc++.h>
    355 
    356 using namespace std;
    357 
    358 int n, m;
    359 vector<int> val;
    360 vector<vector<pair<int, int>>> g;
    361 
    362 void dfs(int v, int pv, int pe, vector<pair<int, int>> &p) {
    363 	p[v] = make_pair(pv, pe);
    364 	for (auto it : g[v]) {
    365 		int to = it.first;
    366 		int idx = it.second;
    367 		if (to == pv) continue;
    368 		dfs(to, v, idx, p);
    369 	}
    370 }
    371 
    372 int main() {
    373 #ifdef _DEBUG
    374 	freopen("input.txt", "r", stdin);
    375 //	freopen("output.txt", "w", stdout);
    376 #endif
    377 	
    378 	cin >> n;
    379 	g = vector<vector<pair<int, int>>>(n);
    380 	for (int i = 0; i < n - 1; ++i) {
    381 		int u, v;
    382 		cin >> u >> v;
    383 		--u, --v;
    384 		g[u].push_back(make_pair(v, i));
    385 		g[v].push_back(make_pair(u, i));
    386 	}
    387 	
    388 	vector<vector<pair<int, int>>> p(n, vector<pair<int, int>>(n));
    389 	for (int i = 0; i < n; ++i) {
    390 		dfs(i, -1, -1, p[i]);
    391 	}
    392 	
    393 	val = vector<int>(n - 1, 1000000);
    394 
    395     cin >> m;
    396 	vector<pair<pair<int, int>, int>> q(m);
    397 	for (int i = 0; i < m; ++i) {
    398 		cin >> q[i].first.first >> q[i].first.second >> q[i].second;
    399 		--q[i].first.first;
    400 		--q[i].first.second;
    401 	}
    402 	sort(q.begin(), q.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    403 		return a.second < b.second;
    404 	});
    405 	
    406 	for (int i = 0; i < m; ++i) {
    407 		int u = q[i].first.first;
    408 		int v = q[i].first.second;
    409 		while (v != u) {
    410 			int pv = p[u][v].first;
    411 			int pe = p[u][v].second;
    412 			val[pe] = q[i].second;
    413 			v = pv;
    414 		}
    415 	}
    416 	
    417 	for (int i = 0; i < m; ++i) {
    418 		int u = q[i].first.first;
    419 		int v = q[i].first.second;
    420 		int mx = 1000000;
    421 		while (v != u) {
    422 			int pv = p[u][v].first;
    423 			int pe = p[u][v].second;
    424 			mx = min(mx, val[pe]);
    425 			v = pv;
    426 		}
    427 		if (mx != q[i].second) {
    428 			cout << -1 << endl;
    429 			return 0;
    430 		}
    431 	}
    432 	
    433 	for (int i = 0; i < n - 1; ++i) {
    434 		cout << val[i] << " ";
    435 	}
    436 	cout << endl;
    437 	
    438 	return 0;
    439 }
    440 ```