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