codeforces-scrape

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

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