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 ```