codeforces-scrape

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

1203.md (7282B)


      1 Source: https://codeforces.com/blog/entry/69108
      2 
      3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      4 
      5 [1203A - Circle of Students](/contest/1203/problem/A "Codeforces Round 579 (Div. 3)")
      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 q;
     25 	cin >> q;
     26 	for (int i = 0; i < q; ++i) {
     27 		int n;
     28 		cin >> n;
     29 		vector<int> a(n);
     30 		int pos = -1;
     31 		for (int j = 0; j < n; ++j) {
     32 			cin >> a[j];
     33 			if (a[j] == 1) pos = j;
     34 		}
     35 		bool okl = true, okr = true;
     36 		for (int j = 1; j < n; ++j) {
     37 			okl &= (a[(pos - j + n) % n] == j + 1);
     38 			okr &= (a[(pos + j + n) % n] == j + 1);
     39 		}
     40 		if (okl || okr) cout << "YES" << endl;
     41 		else cout << "NO" << endl;
     42 	}
     43 	
     44 	return 0;
     45 }
     46 ```
     47 
     48 [1203B - Equal Rectangles](/contest/1203/problem/B "Codeforces Round 579 (Div. 3)")
     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 q;
     68 	cin >> q;
     69 	for (int i = 0; i < q; ++i) {
     70 		int n;
     71 		cin >> n;
     72 		vector<int> a(4 * n);
     73 		for (int j = 0; j < 4 * n; ++j) {
     74 			cin >> a[j];
     75 		}
     76 		sort(a.begin(), a.end());
     77 		int area = a[0] * a.back();
     78 		bool ok = true;
     79 		for (int i = 0; i < n; ++i) {
     80 			int lf = i * 2, rg = 4 * n - (i * 2) - 1;
     81 			if (a[lf] != a[lf + 1] || a[rg] != a[rg - 1] || a[lf] * 1ll * a[rg] != area) {
     82 				ok = false;
     83 			}
     84 		}
     85 		if (ok) cout << "YES" << endl;
     86 		else cout << "NO" << endl;
     87 	}
     88 	
     89 	return 0;
     90 }
     91 ```
     92 
     93 [1203C - Common Divisors](/contest/1203/problem/C "Codeforces Round 579 (Div. 3)")
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Solution**
    100 
    101 ```
    102 #include <bits/stdc++.h>
    103 
    104 using namespace std;
    105 
    106 int main() {
    107 #ifdef _DEBUG
    108 	freopen("input.txt", "r", stdin);
    109 //	freopen("output.txt", "w", stdout);
    110 #endif
    111 	
    112 	int n;
    113 	cin >> n;
    114 	long long g = 0;
    115 	for (int i = 0; i < n; ++i) {
    116 		long long x;
    117 		cin >> x;
    118 		g = __gcd(g, x);
    119 	}
    120 	
    121 	int ans = 0;
    122 	for (int i = 1; i * 1ll * i <= g; ++i) {
    123 		if (g % i == 0) {
    124 			++ans;
    125 			if (i != g / i) {
    126 				++ans;
    127 			}
    128 		}
    129 	}
    130 	
    131 	cout << ans << endl;
    132 	
    133 	return 0;
    134 }
    135 ```
    136 
    137 [1203D1 - Remove the Substring (easy version)](/contest/1203/problem/D1 "Codeforces Round 579 (Div. 3)")
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution**
    144 
    145 ```
    146 #include <bits/stdc++.h>
    147 
    148 using namespace std;
    149 
    150 int main() {
    151 #ifdef _DEBUG
    152 	freopen("input.txt", "r", stdin);
    153 //	freopen("output.txt", "w", stdout);
    154 #endif
    155 	
    156 	string s, t;
    157 	cin >> s >> t;
    158 	int ans = 0;
    159 	for (int i = 0; i < int(s.size()); ++i) {
    160 		for (int j = i; j < int(s.size()); ++j) {
    161 			int pos = 0;
    162 			for (int p = 0; p < int(s.size()); ++p) {
    163 				if (i <= p && p <= j) continue;
    164 				if (pos < int(t.size()) && t[pos] == s[p]) ++pos;
    165 			}
    166 			if (pos == int(t.size())) ans = max(ans, j - i + 1);
    167 		}
    168 	}
    169 	cout << ans << endl;
    170 	
    171 	return 0;
    172 }
    173 ```
    174 
    175 [1203D2 - Remove the Substring (hard version)](/contest/1203/problem/D2 "Codeforces Round 579 (Div. 3)")
    176 
    177 **Tutorial**
    178 
    179 Tutorial is loading...
    180 
    181 **Solution**
    182 
    183 ```
    184 #include <bits/stdc++.h>
    185 
    186 using namespace std;
    187 
    188 int main() {
    189 #ifdef _DEBUG
    190 	freopen("input.txt", "r", stdin);
    191 //	freopen("output.txt", "w", stdout);
    192 #endif
    193 	
    194 	string s, t;
    195 	cin >> s >> t;
    196 	vector<int> rg(t.size());
    197 	
    198 	for (int i = int(t.size()) - 1; i >= 0; --i) {
    199 		int pos = int(s.size()) - 1;
    200 		if (i + 1 < int(t.size())) pos = rg[i + 1] - 1;
    201 		while (s[pos] != t[i]) --pos;
    202 		rg[i] = pos;
    203 	}
    204 	
    205 	int ans = 0;
    206 	int pos = 0;
    207 	for (int i = 0; i < int(s.size()); ++i) {
    208 		int rpos = int(s.size()) - 1;
    209 		if (pos < int(t.size())) rpos = rg[pos] - 1;
    210 		ans = max(ans, rpos - i + 1);
    211 		if (pos < int(t.size()) && t[pos] == s[i]) ++pos;
    212 	}
    213 	
    214 	cout << ans << endl;
    215 	
    216 	return 0;
    217 }
    218 ```
    219 
    220 [1203E - Boxers](/contest/1203/problem/E "Codeforces Round 579 (Div. 3)")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution**
    227 
    228 ```
    229 #include <bits/stdc++.h>
    230 
    231 using namespace std;
    232 
    233 int main() {
    234 	int n;
    235 	cin >> n;
    236 	vector<int> a(n);
    237 	for (int i = 0; i < n; ++i) {
    238 		cin >> a[i];
    239 	}
    240 	sort(a.rbegin(), a.rend());
    241 	int lst = a[0] + 2;
    242 	int ans = 0;
    243 	for (int i = 0; i < n; ++i) {
    244 		int cur = -1;
    245 		for (int dx = 1; dx >= -1; --dx) {
    246 			if (a[i] + dx > 0 && a[i] + dx < lst) {
    247 				cur = a[i] + dx;
    248 				break;
    249 			}
    250 		}
    251 		if (cur == -1) continue;
    252 		++ans;
    253 		lst = cur;
    254 	}
    255 	cout << ans << endl;
    256 }
    257 ```
    258 
    259 [1203F1 - Complete the Projects (easy version)](/contest/1203/problem/F1 "Codeforces Round 579 (Div. 3)")
    260 
    261 **Tutorial**
    262 
    263 Tutorial is loading...
    264 
    265 **Solution**
    266 
    267 ```
    268 #include <bits/stdc++.h>
    269 
    270 using namespace std;
    271 
    272 bool comp(const pair<int, int>& a, const pair<int, int>& b) {
    273     return a.first + a.second > b.first + b.second;
    274 }
    275 
    276 int main() {
    277 #ifdef _DEBUG
    278 	freopen("input.txt", "r", stdin);
    279 //	freopen("output.txt", "w", stdout);
    280 #endif
    281 	
    282 	int n, r;
    283 	cin >> n >> r;
    284 	vector<pair<int, int>> pos, neg;
    285 	for (int i = 0; i < n; ++i) {
    286 		pair<int, int> cur;
    287 		cin >> cur.first >> cur.second;
    288 		if (cur.second >= 0) pos.push_back(cur);
    289 		else {
    290 		    cur.first = max(cur.first, abs(cur.second));
    291 		    neg.push_back(cur);
    292 		}
    293 	}
    294 	
    295 	sort(pos.begin(), pos.end());
    296 	sort(neg.begin(), neg.end(), comp);
    297 	
    298 	int taken = 0;
    299 	for (int i = 0; i < int(pos.size()); ++i) {
    300 		if (r >= pos[i].first) {
    301 			r += pos[i].second;
    302 			++taken;
    303 		}
    304 	}
    305 	
    306 	vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0));
    307 	dp[0][r] = taken;
    308 	for (int i = 0; i < int(neg.size()); ++i) {
    309 		for (int cr = 0; cr <= r; ++cr) {
    310 			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
    311 				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
    312 			}
    313 			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
    314 		}
    315 	}
    316 	
    317 	int ans = 0;
    318 	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
    319 	cout << (ans == n ? "YES" : "NO") << endl;
    320 	
    321 	return 0;
    322 }
    323 ```
    324 
    325 [1203F2 - Complete the Projects (hard version)](/contest/1203/problem/F2 "Codeforces Round 579 (Div. 3)")
    326 
    327 **Tutorial**
    328 
    329 Tutorial is loading...
    330 
    331 **Solution**
    332 
    333 ```
    334 #include <bits/stdc++.h>
    335 
    336 using namespace std;
    337 
    338 bool comp(const pair<int, int>& a, const pair<int, int>& b) {
    339     return a.first + a.second > b.first + b.second;
    340 }
    341 
    342 int main() {
    343 #ifdef _DEBUG
    344 	freopen("input.txt", "r", stdin);
    345 //	freopen("output.txt", "w", stdout);
    346 #endif
    347 	
    348 	int n, r;
    349 	cin >> n >> r;
    350 	vector<pair<int, int>> pos, neg;
    351 	for (int i = 0; i < n; ++i) {
    352 		pair<int, int> cur;
    353 		cin >> cur.first >> cur.second;
    354 		if (cur.second >= 0) pos.push_back(cur);
    355 		else {
    356 		    cur.first = max(cur.first, abs(cur.second));
    357 		    neg.push_back(cur);
    358 		}
    359 	}
    360 	
    361 	sort(pos.begin(), pos.end());
    362 	sort(neg.begin(), neg.end(), comp);
    363 	
    364 	int taken = 0;
    365 	for (int i = 0; i < int(pos.size()); ++i) {
    366 		if (r >= pos[i].first) {
    367 			r += pos[i].second;
    368 			++taken;
    369 		}
    370 	}
    371 	
    372 	vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0));
    373 	dp[0][r] = taken;
    374 	for (int i = 0; i < int(neg.size()); ++i) {
    375 		for (int cr = 0; cr <= r; ++cr) {
    376 			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
    377 				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
    378 			}
    379 			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
    380 		}
    381 	}
    382 	
    383 	int ans = 0;
    384 	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
    385 	cout << ans << endl;
    386 	
    387 	return 0;
    388 }
    389 ```