codeforces-scrape

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

1469.md (8345B)


      1 Source: https://codeforces.com/blog/entry/86082
      2 
      3 [1469A - Regular Bracket Sequence](/contest/1469/problem/A "Educational Codeforces Round 101 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     s = input()
     17     if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
     18         print('YES')
     19     else:
     20         print('NO')
     21 ```
     22 
     23 **Solution 2 (BledDest)**
     24 
     25 ```
     26 t = int(input())
     27 for i in range(t):
     28     s = input()
     29     n = len(s)
     30     a = [s[i] for i in range(n)]
     31     cnt = n // 2 - 1
     32     for j in range(n):
     33         if a[j] == '?':
     34             if cnt > 0:
     35                 cnt -= 1
     36                 a[j] = '('
     37             else:
     38                 a[j] = ')'
     39     bal = 0
     40     minbal = 0
     41     for j in range(n):
     42         if a[j] == '(':
     43             bal += 1
     44         else:
     45             bal -= 1
     46         minbal = min(bal, minbal)
     47     print('YES' if bal == 0 and minbal >= 0 else 'NO')
     48 ```
     49 
     50 [1469B - Red and Blue](/contest/1469/problem/B "Educational Codeforces Round 101 (Rated for Div. 2)")
     51 
     52 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [adedalic](/profile/adedalic "International Master adedalic")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution 1 (Ne0n25)**
     59 
     60 ```
     61 #include <bits/stdc++.h>
     62 
     63 using namespace std;
     64 
     65 void solve() {
     66 	int n;
     67 	cin >> n;
     68 	vector<int> r(n);
     69 	for (int &x : r) cin >> x;
     70 	int m;
     71 	cin >> m;
     72 	vector<int> b(m);
     73 	for (int &x : b) cin >> x;
     74 	partial_sum(r.begin(), r.end(), r.begin());
     75 	partial_sum(b.begin(), b.end(), b.begin());
     76 	cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
     77 }
     78 
     79 int main() {
     80 	int t;
     81 	cin >> t;
     82 	while (t--) solve();
     83 }
     84 ```
     85 
     86 **Solution 2 (pikmike)**
     87 
     88 ```
     89 for _ in range(int(input())):
     90 	n = int(input())
     91 	a = [int(x) for x in input().split()]
     92 	m = int(input())
     93 	b = [int(x) for x in input().split()]
     94 	dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
     95 	dp[0][0] = 0
     96 	ans = 0
     97 	for i in range(n + 1):
     98 		for j in range(m + 1):
     99 			if i < n:
    100 				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
    101 			if j < m:
    102 				dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
    103 			ans = max(ans, dp[i][j])
    104 	print(ans)
    105 ```
    106 
    107 [1469C - Building a Fence](/contest/1469/problem/C "Educational Codeforces Round 101 (Rated for Div. 2)")
    108 
    109 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution (adedalic)**
    116 
    117 ```
    118 fun main() {
    119     repeat(readLine()!!.toInt()) {
    120         val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    121         val h = readLine()!!.split(' ').map { it.toInt() }
    122 
    123         var mn = h[0]
    124         var mx = h[0]
    125         var ok = true
    126         for (i in 1 until n) {
    127             mn = maxOf(mn - k + 1, h[i])
    128             mx = minOf(mx + k - 1, h[i] + k - 1)
    129             if (mn > mx) {
    130                 ok = false
    131                 break
    132             }
    133         }
    134         if (h[n - 1] !in mn..mx)
    135             ok = false
    136         println(if (ok) "YES" else "NO")
    137     }
    138 }
    139 ```
    140 
    141 [1469D - Ceil Divisions](/contest/1469/problem/D "Educational Codeforces Round 101 (Rated for Div. 2)")
    142 
    143 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution (adedalic)**
    150 
    151 ```
    152 #include<bits/stdc++.h>
    153 
    154 using namespace std;
    155 
    156 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    157 #define sz(a) int((a).size())
    158 
    159 #define x first
    160 #define y second
    161 
    162 typedef long long li;
    163 typedef long double ld;
    164 typedef pair<int, int> pt;
    165 
    166 const int INF = int(1e9);
    167 const li INF64 = li(1e18);
    168 const ld EPS = 1e-9;
    169 
    170 int n;
    171 
    172 inline bool read() {
    173 	if(!(cin >> n))
    174 		return false;
    175 	return true;
    176 }
    177 
    178 void calc(int n, vector<pt> &ans) {
    179 	if (n == 2)
    180 		return;
    181 	
    182 	int y = max(1, (int)sqrt(n) - 1);
    183 	while (y < (n + y - 1) / y)
    184 		y++;
    185 	
    186 	fore (pos, y + 1, n)
    187 		ans.emplace_back(pos, n);
    188 	ans.emplace_back(n, y);
    189 	ans.emplace_back(n, y);
    190 	
    191 	calc(y, ans);
    192 }
    193 
    194 inline void solve() {
    195 	vector<pt> ans;
    196 	calc(n, ans);
    197 	
    198 	cout << sz(ans) << endl;
    199 	for(auto p : ans)
    200 		cout << p.first << " " << p.second << '\n';
    201 }
    202 
    203 int main() {
    204 #ifdef _DEBUG
    205 	freopen("input.txt", "r", stdin);
    206 	int tt = clock();
    207 #endif
    208 	ios_base::sync_with_stdio(false);
    209 	cin.tie(0), cout.tie(0);
    210 	cout << fixed << setprecision(15);
    211 	
    212 	int tc; cin >> tc;
    213 	while(tc--) {
    214 		read();
    215 		solve();
    216 		
    217 #ifdef _DEBUG
    218 		cerr << "TIME = " << clock() - tt << endl;
    219 		tt = clock();
    220 #endif
    221 	}
    222 	return 0;
    223 }
    224 ```
    225 
    226 [1469E - A Bit Similar](/contest/1469/problem/E "Educational Codeforces Round 101 (Rated for Div. 2)")
    227 
    228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Solution (BledDest)**
    235 
    236 ```
    237 #include<bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 const int N = 1000043;                 
    242 int q;
    243 char buf[N];
    244 int n, k;
    245 
    246 int ceilLog(int x)
    247 {
    248     int y = 0;
    249     while((1 << y) < x)
    250         y++;
    251     return y;
    252 }
    253 
    254 int main()
    255 {
    256     scanf("%d", &q);
    257     for(int i = 0; i < q; i++)
    258     {
    259         scanf("%d %d", &n, &k);
    260         scanf("%s", buf);
    261         string s = buf;
    262         int m = min(k, ceilLog(n - k + 2));
    263         vector<int> used(1 << m, 0);
    264         vector<int> next0(n, int(1e9));
    265         if(s[n - 1] == '0')
    266             next0[n - 1] = n - 1;
    267         for(int j = n - 2; j >= 0; j--)
    268             if(s[j] == '0')
    269                 next0[j] = j;
    270             else
    271                 next0[j] = next0[j + 1];
    272         int d = k - m;
    273         for(int j = 0; j < n - k + 1; j++)
    274         {
    275             if(next0[j] - j < d)
    276                 continue;
    277             int cur = 0;
    278             for(int x = j + d; x < j + k; x++)
    279                 cur = cur * 2 + (s[x] - '0');
    280             used[((1 << m) - 1) ^ cur] = 1;    
    281         }
    282         int ans = -1;
    283         for(int j = 0; j < (1 << m); j++)
    284             if(used[j] == 0)
    285             {
    286                 ans = j;
    287                 break;    
    288             }
    289         if(ans == -1)
    290             puts("NO");
    291         else
    292         {
    293             puts("YES");
    294             string res(d, '0');
    295             string res2;
    296             for(int j = 0; j < m; j++)
    297             {
    298                 res2.push_back('0' + (ans % 2));
    299                 ans /= 2;
    300             }
    301             reverse(res2.begin(), res2.end());
    302             res += res2;
    303             puts(res.c_str());
    304         }
    305     }
    306 }
    307 ```
    308 
    309 [1469F - Power Sockets](/contest/1469/problem/F "Educational Codeforces Round 101 (Rated for Div. 2)")
    310 
    311 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    312 
    313 **Tutorial**
    314 
    315 Tutorial is loading...
    316 
    317 **Solution (pikmike)**
    318 
    319 ```
    320 #include <bits/stdc++.h>
    321 
    322 #define forn(i, n) for (int i = 0; i < int(n); i++)
    323 
    324 using namespace std;
    325 
    326 const int INF = 1e9;
    327 
    328 int n, k, nn;
    329 
    330 vector<long long> t, ps;
    331 
    332 void push(int v, int l, int r){
    333 	if (l < r - 1){
    334 		ps[v * 2] += ps[v];
    335 		ps[v * 2 + 1] += ps[v];
    336 	}
    337 	t[v] += ps[v] * (r - l);
    338 	ps[v] = 0;
    339 }
    340 
    341 void upd(int v, int l, int r, int L, int R, int val){
    342 	push(v, l, r);
    343 	if (L >= R)
    344 		return;
    345 	if (l == L && r == R){
    346 		ps[v] = val;
    347 		push(v, l, r);
    348 		return;
    349 	}
    350 	int m = (l + r) / 2;
    351 	upd(v * 2, l, m, L, min(m, R), val);
    352 	upd(v * 2 + 1, m, r, max(m, L), R, val);
    353 	t[v] = t[v * 2] + t[v * 2 + 1];
    354 }
    355 
    356 long long get(int v, int l, int r, int L, int R){
    357 	push(v, l, r);
    358 	if (L >= R)
    359 		return 0;
    360 	if (l == L && r == R)
    361 		return t[v];
    362 	int m = (l + r) / 2;
    363 	long long res = get(v * 2, l, m, L, min(m, R)) + get(v * 2 + 1, m, r, max(m, L), R);
    364 	t[v] = t[v * 2] + t[v * 2 + 1];
    365 	return res;
    366 }
    367 
    368 int trav(int v, int l, int r, int cnt){
    369 	push(v, l, r);
    370 	if (l == r - 1)
    371 		return l;
    372 	int m = (l + r) / 2;
    373 	push(v * 2, l, m);
    374 	push(v * 2 + 1, m, r);
    375 	int res = INF;
    376 	if (t[v * 2] >= cnt)
    377 		res = trav(v * 2, l, m, cnt);
    378 	else if (t[v * 2 + 1] >= cnt - t[v * 2])
    379 		res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
    380 	t[v] = t[v * 2] + t[v * 2 + 1];
    381 	return res;
    382 }
    383 
    384 int main() {
    385 	scanf("%d%d", &n, &k);
    386 	vector<int> a(n);
    387 	forn(i, n) scanf("%d", &a[i]);
    388 	sort(a.begin(), a.end(), greater<int>());
    389 	nn = a[0] + 500;
    390 	t.resize(4 * nn);
    391 	ps.resize(4 * nn);
    392 	upd(1, 0, nn, 0, 1, 1);
    393 	int fst = 0;
    394 	int ans = INF;
    395 	forn(i, n){
    396 		while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
    397 		upd(1, 0, nn, fst, fst + 1, -1);
    398 		upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
    399 		upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
    400 		ans = min(ans, trav(1, 0, nn, k));
    401 	}
    402 	printf("%d\n", ans == INF ? -1 : ans);
    403 	return 0;
    404 }
    405 ```