1791.md (8531B)
1 Source: https://codeforces.com/blog/entry/112282 2 3 We hope you enjoyed the contest! 4 5 [1791A - Codeforces Checking](/contest/1791/problem/A "Codeforces Round 849 (Div. 4)") 6 7 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 const string s = "codeforces"; 21 22 void solve() { 23 char c; 24 cin >> c; 25 for (char i : s) { 26 if (i == c) {cout << "YES\n"; return;} 27 } 28 cout << "NO\n"; 29 } 30 31 int main() { 32 ios::sync_with_stdio(false); 33 cin.tie(nullptr); 34 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 35 // solve(); 36 } 37 ``` 38 39 [1791B - Following Directions](/contest/1791/problem/B "Codeforces Round 849 (Div. 4)") 40 41 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 **Solution** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 using namespace std; 53 54 const int MAX = 200007; 55 const int MOD = 1000000007; 56 57 void solve() { 58 int n; 59 cin >> n; 60 string s; 61 cin >> s; 62 int x = 0, y = 0; 63 for (int i = 0; i < n; i++) { 64 if (s[i] == 'L') {x--;} 65 if (s[i] == 'R') {x++;} 66 if (s[i] == 'D') {y--;} 67 if (s[i] == 'U') {y++;} 68 if (x == 1 && y == 1) {cout << "YES\n"; return;} 69 } 70 cout << "NO\n"; 71 } 72 73 int main() { 74 ios::sync_with_stdio(false); 75 cin.tie(nullptr); 76 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 77 // solve(); 78 } 79 ``` 80 81 [1791C - Prepend and Append](/contest/1791/problem/C "Codeforces Round 849 (Div. 4)") 82 83 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution** 90 91 ``` 92 #include <bits/stdc++.h> 93 94 using namespace std; 95 96 const int MAX = 200007; 97 const int MOD = 1000000007; 98 99 void solve() { 100 int n; 101 cin >> n; 102 string s; 103 cin >> s; 104 int l = 0, r = n - 1, ans = n; 105 while (s[l] != s[r] && ans > 0) {l++; r--; ans -= 2;} 106 cout << ans << '\n'; 107 } 108 109 int main() { 110 ios::sync_with_stdio(false); 111 cin.tie(nullptr); 112 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 113 // solve(); 114 } 115 ``` 116 117 [1791D - Distinct Split](/contest/1791/problem/D "Codeforces Round 849 (Div. 4)") 118 119 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution** 126 127 ``` 128 #include "bits/stdc++.h" 129 using namespace std; 130 131 #define ll long long 132 133 #define all(v) v.begin(), v.end() 134 #define rall(v) v.rbegin(),v.rend() 135 136 #define pb push_back 137 #define sz(a) (int)a.size() 138 139 void solve() { 140 int n; string s; cin >> n >> s; 141 vector<int> cnt(26, 0), p(26, 0); 142 for(auto x: s) cnt[x - 'a']++; 143 int ans = 0; 144 for(auto x: s) { 145 --cnt[x - 'a']; 146 ++p[x - 'a']; 147 int cur = 0; 148 for(int i = 0; i < 26; ++i) { 149 cur += min(1, cnt[i]) + min(1, p[i]); 150 } 151 ans = max(ans, cur); 152 } 153 cout << ans << "\n"; 154 } 155 156 int32_t main() { 157 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 158 int t = 1; 159 cin >> t; 160 while(t--) { 161 solve(); 162 } 163 } 164 ``` 165 166 [1791E - Negatives and Positives](/contest/1791/problem/E "Codeforces Round 849 (Div. 4)") 167 168 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 169 170 **Tutorial** 171 172 Tutorial is loading... 173 174 **Solution** 175 176 ``` 177 #include <bits/stdc++.h> 178 using namespace std; 179 180 int main() { 181 int t; cin >> t; 182 while(t--) { 183 int n; cin >> n; 184 vector<int> a(n); 185 long long sum = 0; 186 int negs = 0; 187 for(int i = 0; i < n; ++i) { 188 cin >> a[i]; 189 if(a[i] < 0) { 190 ++negs; 191 a[i] = -a[i]; 192 } 193 sum += a[i]; 194 } 195 sort(a.begin(), a.end()); 196 if(negs & 1) sum -= 2 * a[0]; 197 cout << sum << "\n"; 198 } 199 } 200 ``` 201 202 [1791F - Range Update Point Query](/contest/1791/problem/F "Codeforces Round 849 (Div. 4)") 203 204 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 205 206 **Tutorial** 207 208 Tutorial is loading... 209 210 **Solution** 211 212 ``` 213 #include <bits/stdc++.h> 214 using namespace std; 215 216 int digit_sum(int n) { 217 int ret = 0; 218 while(n) { 219 ret += n % 10; 220 n /= 10; 221 } 222 return ret; 223 } 224 void solve() { 225 int n, q; cin >> n >> q; 226 vector<int> a(n); 227 set<int> s; 228 for(int i = 0; i < n; ++i) { 229 cin >> a[i]; 230 if(a[i] > 9) s.insert(i); 231 } 232 while(q--) { 233 int type; cin >> type; 234 if(type == 1) { 235 int l, r; cin >> l >> r; --l, --r; 236 int lst = l; 237 while(!s.empty()) { 238 auto it = s.lower_bound(lst); 239 if(it == s.end() || *it > r) break; 240 a[*it] = digit_sum(a[*it]); 241 int paiu = *it; 242 s.erase(it); 243 if(a[paiu] > 9) s.insert(paiu); 244 lst = paiu + 1; 245 } 246 } else { 247 int x; cin >> x; --x; 248 cout << a[x] << "\n"; 249 } 250 } 251 } 252 253 int main() { 254 ios::sync_with_stdio(false); 255 cin.tie(nullptr); 256 cout.tie(0); 257 int t; cin >> t; 258 while(t--) { 259 solve(); 260 } 261 } 262 ``` 263 264 [1791G1 - Teleporters (Easy Version)](/contest/1791/problem/G1 "Codeforces Round 849 (Div. 4)") 265 266 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution** 273 274 ``` 275 #include "bits/stdc++.h" 276 using namespace std; 277 278 #define ll long long 279 280 #define all(v) v.begin(), v.end() 281 #define rall(v) v.rbegin(),v.rend() 282 283 #define pb push_back 284 #define sz(a) (int)a.size() 285 286 void solve() { 287 int n, c, ans = 0; cin >> n >> c; 288 priority_queue<int> q; 289 for(int i = 1, x; i <= n; ++i) { 290 cin >> x; 291 q.push(-x - i); 292 } 293 while(!q.empty()) { 294 int x = -q.top(); q.pop(); 295 if(x > c) break; 296 ++ans; 297 c -= x; 298 } 299 cout << ans << "\n"; 300 } 301 302 int32_t main() { 303 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 304 int t = 1; 305 cin >> t; 306 while(t--) { 307 solve(); 308 } 309 } 310 ``` 311 312 [1791G2 - Teleporters (Hard Version)](/contest/1791/problem/G2 "Codeforces Round 849 (Div. 4)") 313 314 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 315 316 **Tutorial** 317 318 Tutorial is loading... 319 320 **Solution** 321 322 ``` 323 #include <bits/stdc++.h> 324 #define startt ios_base::sync_with_stdio(false);cin.tie(0); 325 typedef long long ll; 326 using namespace std; 327 #define vint vector<int> 328 #define all(v) v.begin(), v.end() 329 #define MOD 1000000007 330 #define MOD2 998244353 331 #define MX 1000000000 332 #define MXL 1000000000000000000 333 #define PI (ld)2*acos(0.0) 334 #define pb push_back 335 #define sc second 336 #define fr first 337 #define int long long 338 #define endl '\n' 339 #define ld long double 340 #define NO cout << "NO" << endl 341 #define YES cout << "YES" << endl 342 int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu 343 344 void solve() 345 { 346 int n, c; 347 cin >> n >> c; 348 vector<pair<int, int>> a; 349 for(int i = 0; i < n; i++) 350 { 351 int x; 352 cin >> x; 353 a.pb({x+min(i+1, n-i), x+i+1}); 354 } 355 sort(all(a)); 356 vector<int> pref; 357 pref.pb(0); 358 for(int i = 0; i < n; i++) 359 { 360 pref.pb(pref.back()+a[i].fr); 361 } 362 int ans = 0; 363 for(int i = 0; i < n; i++) 364 { 365 int new_c = c-a[i].sc; 366 int l = 0, r = n; 367 int mx = 0; 368 while(l <= r) 369 { 370 int mid = l+r>>1; 371 // Calculate price 372 int price = pref[mid]; 373 int now = mid+1; 374 if(mid > i) 375 { 376 price-=a[i].fr; 377 now--; 378 } 379 if(price <= new_c) 380 { 381 mx = max(now, mx); 382 l = mid+1; 383 } 384 else 385 { 386 r = mid-1; 387 } 388 } 389 ans = max(ans, mx); 390 } 391 cout << ans << endl; 392 } 393 394 int32_t main(){ 395 startt 396 int t = 1; 397 cin >> t; 398 while (t--) { 399 solve(); 400 } 401 } 402 ```