codeforces-scrape

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

1015.md (9262B)


      1 Source: https://codeforces.com/blog/entry/60949
      2 
      3 [1015A - Points in Segments](/contest/1015/problem/A "Codeforces Round 501 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh, O(n + m))**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17 #ifdef _DEBUG
     18 	freopen("input.txt", "r", stdin);
     19 //	freopen("output.txt", "w", stdout);
     20 #endif
     21 	
     22 	int n, m;
     23 	cin >> n >> m;
     24 	vector<int> cnt(m + 2);
     25 	for (int i = 0; i < n; ++i) {
     26 		int l, r;
     27 		cin >> l >> r;
     28 		++cnt[l];
     29 		--cnt[r + 1];
     30 	}
     31 	for (int i = 1; i <= m; ++i)
     32 		cnt[i] += cnt[i - 1];
     33 	
     34 	vector<int> ans;
     35 	for (int i = 1; i <= m; ++i) {
     36 		if (cnt[i] == 0)
     37 			ans.push_back(i);
     38 	}
     39 	
     40 	cout << ans.size() << endl;
     41 	for (auto it : ans) cout << it << " ";
     42 	cout << endl;
     43 	
     44 	return 0;
     45 }
     46 ```
     47 
     48 **Solution (Vovuh, O(n * m))**
     49 
     50 ```
     51 n, m = map(int, input().split())
     52 seg = [list(map(int, input().split())) for i in range(n)]
     53 def bad(x):
     54 	for i in range(n):
     55 		if (seg[i][0] <= x and x <= seg[i][1]): return False
     56 	return True
     57 ans = list(filter(bad, [i for i in range(1, m + 1)]))
     58 print(len(ans))
     59 print(' '.join([str(x) for x in ans]))
     60 ```
     61 
     62 [1015B - Obtaining the String](/contest/1015/problem/B "Codeforces Round 501 (Div. 3)")
     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 n;
     82 	string s, t;
     83 	cin >> n >> s >> t;
     84 	
     85 	vector<int> ans;
     86 	for (int i = 0; i < n; ++i) {
     87 		if (s[i] == t[i]) continue;
     88 		int pos = -1;
     89 		for (int j = i + 1; j < n; ++j) {
     90 			if (s[j] == t[i]) {
     91 			        pos = j;
     92 			        break;
     93 			}
     94 		}
     95 		if (pos == -1) {
     96 			cout << -1 << endl;
     97 			return 0;
     98 		}
     99 		for (int j = pos - 1; j >= i; --j) {
    100 			swap(s[j], s[j + 1]);
    101 			ans.push_back(j);
    102 		}
    103 	}
    104 	
    105 	assert(s == t);
    106 	
    107 	cout << ans.size() << endl;
    108 	for (auto it : ans) cout << it + 1 << " ";
    109 	cout << endl;
    110 	
    111 	return 0;
    112 }
    113 ```
    114 
    115 [1015C - Songs Compression](/contest/1015/problem/C "Codeforces Round 501 (Div. 3)")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution (Vovuh)**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 int main() {
    129 #ifdef _DEBUG
    130 	freopen("input.txt", "r", stdin);
    131 //	freopen("output.txt", "w", stdout);
    132 #endif
    133 	
    134 	int n, m;
    135 	cin >> n >> m;
    136 	vector<pair<int, int>> a(n);
    137 	long long sum = 0;
    138 	for (int i = 0; i < n; ++i) {
    139 		cin >> a[i].first >> a[i].second;
    140 		sum += a[i].first;
    141 	}
    142 	
    143 	sort(a.begin(), a.end(), [&](pair<int, int> a, pair<int, int> b) { return a.first - a.second > b.first - b.second; });
    144 	
    145 	for (int i = 0; i < n; ++i) {
    146 		if (sum <= m) {
    147 			cout << i << endl;
    148 			return 0;
    149 		}
    150 		sum -= a[i].first - a[i].second;
    151 	}
    152 	
    153 	if (sum <= m)
    154 		cout << n << endl;
    155 	else
    156 		cout << -1 << endl;
    157 	
    158 	return 0;
    159 }
    160 ```
    161 
    162 [1015D - Walking Between Houses](/contest/1015/problem/D "Codeforces Round 501 (Div. 3)")
    163 
    164 **Tutorial**
    165 
    166 Tutorial is loading...
    167 
    168 **Solution (BledDest)**
    169 
    170 ```
    171 def step(cur, x):
    172     if(cur - x > 0):
    173         return cur - x
    174     else:
    175         return cur + x
    176 
    177 n, k, s = map(int, input().split())
    178 cur = 1
    179 
    180 if(k > s or k * (n - 1) < s):
    181     print('NO')
    182 else:
    183     print('YES')
    184     while(k > 0):
    185         l = min(n - 1, s - (k - 1))
    186         cur = step(cur, l)
    187         print(cur, end = ' ')
    188         s -= l
    189         k -= 1
    190 ```
    191 
    192 [1015E1 - Stars Drawing (Easy Edition)](/contest/1015/problem/E1 "Codeforces Round 501 (Div. 3)")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution (MikeMirzayanov, O(n^3))**
    199 
    200 ```
    201 #include <bits/stdc++.h>
    202 
    203 using namespace std;
    204 
    205 #define forn(i, n) for (int i = 0; i < int(n); i++)
    206 
    207 const int dx[] = {1, 0, -1,  0};
    208 const int dy[] = {0, 1,  0, -1};
    209 const int N = 1001;
    210 
    211 int n, m;
    212 vector<string> f;
    213 int d[N][N][4];
    214 int r[N][N], a[N][N], b[N][N];
    215 
    216 int getd(int i, int j, int k) {
    217     int dxk = dx[k];
    218     int dyk = dy[k];
    219     int result = 0;
    220     while (i >= 0 && i < n && j >= 0 && j < m && f[i][j] == '*')
    221         result++, i += dxk, j += dyk;
    222     return result;
    223 }
    224 
    225 int main() {
    226     cin >> n >> m;
    227     f = vector<string>(n);
    228     forn(i, n)
    229         cin >> f[i];
    230     
    231     memset(d, -1, sizeof(d));
    232     int result = 0;
    233     for (int i = 1; i + 1 < n; i++)
    234         for (int j = 1; j + 1 < m; j++)
    235             if (f[i][j] == '*') {
    236                 bool around = true;
    237                 forn(k, 4)
    238                     around = around && (f[i + dx[k]][j + dy[k]] == '*');
    239                 if (around) {
    240                     r[i][j] = INT_MAX;
    241                     forn(k, 4)
    242                         r[i][j] = min(r[i][j], getd(i, j, k) - 1);
    243                     result++;
    244                     a[i][j - r[i][j]] = max(a[i][j - r[i][j]], 2 * r[i][j] + 1);
    245                     b[i - r[i][j]][j] = max(b[i - r[i][j]][j], 2 * r[i][j] + 1);
    246                 }
    247             }
    248 
    249     vector<string> g(n, string(m, '.'));
    250     forn(i, n) {
    251         int v = 0;
    252         forn(j, m) {
    253             v = max(v - 1, a[i][j]);
    254             if (v > 0)
    255                 g[i][j] = '*';
    256         }
    257     }
    258     forn(j, m) {
    259         int v = 0;
    260         forn(i, n) {
    261             v = max(v - 1, b[i][j]);
    262             if (v > 0)
    263                 g[i][j] = '*';
    264         }
    265     }
    266     
    267     if (f == g) {
    268         cout << result << endl;
    269         forn(i, n)
    270             forn(j, m)
    271                 if (r[i][j] > 0)
    272                     cout << i + 1 << " " << j + 1 << " " << r[i][j] << endl;
    273     } else
    274         cout << -1 << endl;
    275 }
    276 ```
    277 
    278 [1015E2 - Stars Drawing (Hard Edition)](/contest/1015/problem/E2 "Codeforces Round 501 (Div. 3)")
    279 
    280 **Tutorial**
    281 
    282 Tutorial is loading...
    283 
    284 **Solution (Vovuh, O(n^2))**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 
    289 using namespace std;
    290 
    291 int n, m;
    292 vector<string> s;
    293 
    294 vector<string> draw(const vector<pair<pair<int, int>, int>> &r) {
    295 	vector<string> f(n, string(m, '.'));
    296 	vector<vector<int>> h(n, vector<int>(m));
    297 	vector<vector<int>> v(n, vector<int>(m));
    298 	for (auto it : r) {
    299 		int x = it.first.first;
    300 		int y = it.first.second;
    301 		int len = it.second;
    302 		++v[x - len][y];
    303 		if (x + len + 1 < n)
    304 			--v[x + len + 1][y];
    305 		++h[x][y - len];
    306 		if (y + len + 1 < m)
    307 			--h[x][y + len + 1];	
    308 	}
    309 	for (int i = 0; i < n; ++i) {
    310 		for (int j = 0; j < m; ++j) {
    311 			if (i > 0) v[i][j] += v[i - 1][j];
    312 			if (j > 0) h[i][j] += h[i][j - 1];
    313 			if (v[i][j] > 0 || h[i][j] > 0)
    314 				f[i][j] = '*';
    315 		}
    316 	}
    317 	return f;
    318 }
    319 
    320 int main() {
    321 #ifdef _DEBUG
    322 	freopen("input.txt", "r", stdin);
    323 //	freopen("output.txt", "w", stdout);
    324 #endif
    325 	
    326 	cin >> n >> m;
    327 	s = vector<string>(n);
    328 	for (int i = 0; i < n; ++i) {
    329 		cin >> s[i];
    330 	}
    331 	
    332 	vector<vector<int>> l(n, vector<int>(m));
    333 	vector<vector<int>> r(n, vector<int>(m));
    334 	vector<vector<int>> u(n, vector<int>(m));
    335 	vector<vector<int>> d(n, vector<int>(m));
    336 	
    337 	for (int i = 0; i < n; ++i) {
    338 		for (int j = 0; j < m; ++j) {
    339 			if (i > 0) {
    340 				if (s[i][j] != '.')
    341 					u[i][j] = u[i - 1][j] + 1;
    342 			} else {
    343 				u[i][j] = s[i][j] != '.';
    344 			}
    345 			if (j > 0) {
    346 				if (s[i][j] != '.')
    347 					l[i][j] = l[i][j - 1] + 1;
    348 			} else {
    349 				l[i][j] = s[i][j] != '.';
    350 			}
    351 		}
    352 	}
    353 	for (int i = n - 1; i >= 0; --i) {
    354 		for (int j = m - 1; j >= 0; --j) {
    355 			if (i < n - 1) {
    356 				if (s[i][j] != '.')
    357 					d[i][j] = d[i + 1][j] + 1;
    358 			} else {
    359 				d[i][j] = s[i][j] != '.';
    360 			}
    361 			if (j < m - 1) {
    362 				if (s[i][j] != '.')
    363 					r[i][j] = r[i][j + 1] + 1;
    364 			} else {
    365 				r[i][j] = s[i][j] != '.';
    366 			}
    367 		}
    368 	}
    369 	
    370 	vector<pair<pair<int, int>, int>> ans;
    371 	for (int i = 0; i < n; ++i) {
    372 		for (int j = 0; j < m; ++j) {
    373 			if (s[i][j] == '*') {
    374 				int len = min(min(u[i][j], l[i][j]), min(d[i][j], r[i][j])) - 1;
    375 				if (len != 0) {
    376 					ans.push_back(make_pair(make_pair(i, j), len));
    377 				}
    378 			}
    379 		}
    380 	}
    381 	
    382 	if (draw(ans) != s) {
    383 		cout << -1 << endl;
    384 	} else {
    385 		cout << ans.size() << endl;
    386 		for (auto it : ans) {
    387 			cout << it.first.first + 1 << " " << it.first.second + 1 << " " << it.second << endl; 
    388 		}
    389 	}
    390 	
    391 	return 0;
    392 }
    393 ```
    394 
    395 [1015F - Bracket Substring](/contest/1015/problem/F "Codeforces Round 501 (Div. 3)")
    396 
    397 **Tutorial**
    398 
    399 Tutorial is loading...
    400 
    401 **Solution (Vovuh)**
    402 
    403 ```
    404 #include <bits/stdc++.h>
    405 
    406 using namespace std;
    407 
    408 const int N = 203;
    409 const int MOD = 1e9 + 7;
    410 
    411 int n, ssz;
    412 string s;
    413 int len[N][2];
    414 int dp[N][N][N][2];
    415 
    416 int calc(const string &t) {
    417 	int tsz = t.size();
    418 	for (int i = tsz; i > 0; --i) {
    419 		if (s.substr(0, i) == t.substr(tsz - i, i))
    420 			return i;
    421 	}
    422 	return 0;
    423 }
    424 
    425 void add(int &a, int b) {
    426 	a += b;
    427 	if (a >= MOD)
    428 		a -= MOD;
    429 	if (a < 0)
    430 		a += MOD;
    431 }
    432 
    433 int main() {
    434 #ifdef _DEBUG
    435 	freopen("input.txt", "r", stdin);
    436 //	freopen("output.txt", "w", stdout);
    437 #endif
    438 	
    439 	cin >> n >> s;
    440 	ssz = s.size();
    441 	
    442 	if (s[0] == '(')
    443 		len[0][0] = 1;
    444 	else
    445 		len[0][1] = 1;
    446 	
    447 	string pref;
    448 	for (int i = 0; i < ssz; ++i) {
    449 		pref += s[i];
    450 		pref += '(';
    451 		len[i + 1][0] = calc(pref);
    452 		pref.pop_back();
    453 		pref += ')';
    454 		len[i + 1][1] = calc(pref);
    455 		pref.pop_back();
    456 	}
    457 	
    458 	dp[0][0][0][0] = 1;
    459 	for (int i = 0; i < 2 * n; ++i) {
    460 		for (int j = 0; j <= n; ++j) {
    461 			for (int pos = 0; pos <= ssz; ++pos) {
    462 				for (int f = 0; f < 2; ++f) {
    463 					if (dp[i][j][pos][f] == 0) continue;
    464 					if (j + 1 <= n)
    465 						add(dp[i + 1][j + 1][len[pos][0]][f | (len[pos][0] == ssz)], dp[i][j][pos][f]);
    466 					if (j > 0)
    467 						add(dp[i + 1][j - 1][len[pos][1]][f | (len[pos][1] == ssz)], dp[i][j][pos][f]);
    468 				}
    469 			}
    470 		}
    471 	}
    472 	
    473 	int ans = 0;
    474 	for (int i = 0; i <= ssz; ++i)
    475 		add(ans, dp[2 * n][0][i][1]);
    476 		
    477 	cout << ans << endl;
    478 	
    479 	return 0;
    480 }
    481 ```