codeforces-scrape

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

1807.md (7779B)


      1 Source: https://codeforces.com/blog/entry/114143
      2 
      3 Thank you for participating!
      4 
      5 [1807A - Plus or Minus](/contest/1807/problem/A "Codeforces Round 859 (Div. 4)")
      6 
      7 Idea: [flamestorm](/profile/flamestorm "Candidate Master 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 int MAX = 200007;
     21 const int MOD = 1000000007;
     22  
     23 void solve() {
     24 	int a, b, c;
     25 	cin >> a >> b >> c;
     26 	if (a + b == c) {cout << "+\n";}
     27 	else {cout << "-\n";}	
     28 }
     29  
     30 int main() {
     31 	ios::sync_with_stdio(false);
     32 	cin.tie(nullptr);
     33 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     34 	// solve();
     35 }
     36 ```
     37 
     38 [1807B - Grab the Candies](/contest/1807/problem/B "Codeforces Round 859 (Div. 4)")
     39 
     40 Idea: [mesanu](/profile/mesanu "Expert mesanu")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 using namespace std;
     51  
     52 void solve()
     53 {
     54     int n;
     55     cin >> n;
     56     int x, odd = 0, even = 0;
     57     for(int i = 0; i < n; i++)
     58     {
     59         cin >> x;
     60         if(x%2 == 0)
     61         {
     62             even+=x;
     63         }
     64         else
     65         {
     66             odd+=x;
     67         }
     68     }
     69     if(even > odd)
     70     {
     71         cout << "YES" << endl;
     72     }
     73     else
     74     {
     75         cout << "NO" << endl;
     76     }
     77 }
     78  
     79 int32_t main(){
     80     int t = 1;
     81     cin >> t;
     82     while (t--) {
     83         solve();
     84     }
     85 }
     86 ```
     87 
     88 [1807C - Find and Replace](/contest/1807/problem/C "Codeforces Round 859 (Div. 4)")
     89 
     90 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100  
    101 using namespace std;
    102  
    103 const int MAX = 200007;
    104 const int MOD = 1000000007;
    105  
    106 void solve() {
    107 	int n;
    108 	cin >> n;
    109 	string s;
    110 	cin >> s;
    111 	int mp[26];
    112 	for (int i = 0; i < 26; i++) {
    113 		mp[i] = -1;
    114 	}
    115 	for (int i = 0; i < n; i++) {
    116 		int curr = (s[i] - 'a');
    117 		if (mp[curr] == -1) {
    118 			mp[curr] = (i % 2);
    119 		}
    120 		else {
    121 			if (mp[curr] != (i % 2)) {cout << "NO\n"; return;}
    122 		}
    123 	}
    124 	cout << "YES\n";
    125 }
    126  
    127 int main() {
    128 	ios::sync_with_stdio(false);
    129 	cin.tie(nullptr);
    130 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    131 	// solve();
    132 }
    133 ```
    134 
    135 [1807D - Odd Queries](/contest/1807/problem/D "Codeforces Round 859 (Div. 4)")
    136 
    137 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
    138 
    139 **Tutorial**
    140 
    141 Tutorial is loading...
    142 
    143 **Solution**
    144 
    145 ```
    146 #include <iostream>
    147  
    148 using namespace std;
    149 long long n,a[200005],q,sum=0,pref[200005],t;
    150 int main() {
    151     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    152     cin>>t;
    153     while(t--)
    154     {
    155         sum = 0;
    156         cin >> n >> q;
    157         for(int i=1;i<=n;i++){
    158             cin >> a[i];
    159             sum+=a[i];
    160             pref[i]=pref[i-1];
    161             pref[i]+=a[i];
    162         }
    163         for(int i = 0; i < q; i++){
    164             long long l,r,k;
    165             cin >> l >> r >> k;
    166             long long ans = pref[n]-(pref[r]-pref[l-1])+k*(r-l+1);
    167             if(ans%2==1){
    168                 cout<<"YES"<<endl;
    169             }
    170             else
    171             {
    172                 cout<<"NO"<<endl;
    173             }
    174         }
    175     }
    176 }
    177 ```
    178 
    179 [1807E - Interview](/contest/1807/problem/E "Codeforces Round 859 (Div. 4)")
    180 
    181 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution**
    188 
    189 ```
    190 #include <bits/stdc++.h>
    191 using ll=long long;
    192 using ld=long double;
    193 int const INF=1000000005;
    194 ll const LINF=1000000000000000005;
    195 ll const mod=1000000007;
    196 ld const PI=3.14159265359;
    197 ll const MAX_N=3e5+5;
    198 ld const EPS=0.00000001;
    199 #pragma GCC optimize("O3")
    200 #pragma GCC optimize("Ofast")
    201 #define f first
    202 #define s second
    203 #define pb push_back
    204 #define mp make_pair
    205 #define endl '\n'
    206 #define sz(a) (int)a.size()
    207 #define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    208 using namespace std;
    209 ll t,n,a[2000005],pref[2000005];
    210 int32_t main(){
    211 //CODE_START;
    212 #ifdef LOCAL
    213 //ifstream cin("input.txt");
    214 #endif
    215 cin>>t;
    216 while(t--){
    217     cin>>n;
    218     for(ll i=1;i<=n;i++)
    219     {
    220         cin>>a[i];
    221         pref[i]=pref[i-1]+a[i];
    222     }
    223     ll l=1,r=n,ans=0;
    224     while(l<=r){
    225             ll mid=(l+r)/2;
    226         cout<<"? "<<(mid-l+1)<<' ';
    227         for(ll i=l;i<=mid;i++)
    228         {
    229             cout<<i<<' ';
    230         }
    231         cout<<endl<<flush;
    232         ll x=0;
    233         cin>>x;
    234         if(x==pref[mid]-pref[l-1]){
    235             l=mid+1;
    236         }else {
    237             r=mid-1;
    238             ans=mid;
    239         }
    240     }
    241     cout<<"! "<<ans<<endl<<flush;
    242 }
    243 }
    244 ```
    245 
    246 [1807F - Bouncy Ball](/contest/1807/problem/F "Codeforces Round 859 (Div. 4)")
    247 
    248 Idea: [mesanu](/profile/mesanu "Expert mesanu")
    249 
    250 **Tutorial**
    251 
    252 Tutorial is loading...
    253 
    254 **Solution**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258 using namespace std;
    259  
    260 void solve()
    261 {
    262     int n, m, x1, y1, x2, y2;
    263     string d_string;
    264     cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    265     x1--;x2--;y1--;y2--;
    266     cin >> d_string;
    267     int d = (d_string[0] == 'U' ? 1+(d_string[1] == 'R' ? 2 : 0) : 0+(d_string[1] == 'R' ? 2 : 0));
    268     bool vis[n][m][4];
    269     memset(vis, false, sizeof(vis));
    270     int i = x1, j = y1;
    271     int bounces = 0;
    272     while(!vis[i][j][d])
    273     {
    274         if(i == x2 && j == y2){cout << bounces << endl; return;}
    275         int na = 0;
    276         if(d%2 == 1 && i == 0){d-=1;na++;}
    277         if(d%2 == 0 && i == n-1){d+=1;na++;}
    278         if(d >= 2 && j == m-1){d-=2;na++;}
    279         if(d < 2 && j == 0){d+=2;na++;}
    280         bounces+=min(1, na);
    281         if(vis[i][j][d])
    282         {
    283             break;
    284         }
    285         vis[i][j][d] = true;
    286         if(d%2 == 1){i--;}else{i++;}
    287         if(d >= 2){j++;}else{j--;}
    288     }
    289     cout << -1 << endl;
    290 }
    291  
    292 int32_t main(){
    293     int t = 1;
    294     cin >> t;
    295     while (t--) {
    296         solve();
    297     }
    298 }
    299 ```
    300 
    301 [1807G1 - Subsequence Addition (Easy Version)](/contest/1807/problem/G1 "Codeforces Round 859 (Div. 4)")
    302 
    303 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm")
    304 
    305 **Tutorial**
    306 
    307 Tutorial is loading...
    308 
    309 **Solution**
    310 
    311 ```
    312 #include "bits/stdc++.h"
    313 using namespace std;
    314  
    315 #define ll long long
    316  
    317 #define          all(v)              v.begin(), v.end()
    318 #define         rall(v)              v.rbegin(),v.rend()
    319  
    320 #define            pb                push_back
    321 #define          sz(a)               (int)a.size()
    322  
    323 void solve() {
    324     int n; cin >> n;
    325     vector<int> a(n);
    326     for(int i = 0; i < n; ++i) {
    327         cin >> a[i];
    328     }
    329     sort(all(a));
    330     if(a[0] != 1) {
    331         cout << "NO\n";
    332         return;
    333     }
    334     vector<int> dp(5005, 0);
    335     dp[1] = 1;
    336     for(int i = 1; i < n; ++i) {
    337         if(!dp[a[i]]) {
    338             cout << "NO\n";
    339             return;
    340         }
    341         for(int j = 5000; j >= a[i]; --j) {
    342             dp[j] |= dp[j - a[i]];
    343         }
    344     }
    345     cout << "YES\n";
    346 }
    347  
    348 int32_t main() {
    349     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    350     int t = 1;
    351     cin >> t;
    352     while(t--) {
    353         solve();
    354     }
    355 }
    356 ```
    357 
    358 [1807G2 - Subsequence Addition (Hard Version)](/contest/1807/problem/G2 "Codeforces Round 859 (Div. 4)")
    359 
    360 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm")
    361 
    362 **Tutorial**
    363 
    364 Tutorial is loading...
    365 
    366 **Solution**
    367 
    368 ```
    369 #include "bits/stdc++.h"
    370 using namespace std;
    371  
    372 #define ll long long
    373  
    374 #define          all(v)              v.begin(), v.end()
    375 #define         rall(v)              v.rbegin(),v.rend()
    376  
    377 #define            pb                push_back
    378 #define          sz(a)               (int)a.size()
    379  
    380 void solve() {
    381     int n; cin >> n;
    382     vector<int> a(n);
    383     for(int i = 0; i < n; ++i) {
    384         cin >> a[i];
    385     }
    386     sort(all(a));
    387     if(a[0] != 1) {
    388         cout << "NO\n";
    389         return;
    390     }
    391     long long sum = a[0];
    392     for(int i = 1; i < n; ++i) {
    393         if(sum < a[i]) {
    394             cout << "NO\n";
    395             return;
    396         }
    397         sum += a[i];
    398     }
    399     cout << "YES\n";
    400 }
    401  
    402 int32_t main() {
    403     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    404     int t = 1;
    405     cin >> t;
    406     while(t--) {
    407         solve();
    408     }
    409 }
    410 ```