1742.md (7045B)
1 Source: https://codeforces.com/blog/entry/107962 2 3 Thanks for participating! 4 5 [1742A - Sum](/contest/1742/problem/A "Codeforces Round 827 (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 int MAX = 200007; 21 const int MOD = 1000000007; 22 23 void solve() { 24 int a, b, c; 25 cin >> a >> b >> c; 26 cout << ((a + b == c || c + a == b || b + c == a) ? "YES\n" : "NO\n"); 27 } 28 29 int main() { 30 ios::sync_with_stdio(false); 31 cin.tie(nullptr); 32 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 33 // solve(); 34 } 35 ``` 36 37 [1742B - Increasing](/contest/1742/problem/B "Codeforces Round 827 (Div. 4)") 38 39 Idea: [mesanu](/profile/mesanu "Expert mesanu") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 using namespace std; 50 51 void solve() 52 { 53 int n; 54 cin >> n; 55 int x[n]; 56 set<int> a; 57 for(int i = 0; i < n; i++) 58 { 59 cin >> x[i]; 60 } 61 for(int i = 0; i < n; i++) 62 { 63 if(a.find(x[i]) != a.end()) 64 { 65 cout << "NO" << endl; 66 return; 67 } 68 a.insert(x[i]); 69 } 70 cout << "YES" << endl; 71 } 72 73 int main() 74 { 75 int t; 76 cin >> t; 77 while(t--) 78 { 79 solve(); 80 } 81 } 82 ``` 83 84 [1742C - Stripes](/contest/1742/problem/C "Codeforces Round 827 (Div. 4)") 85 86 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Bonus** 93 94 How do you write a validator for this problem? (Given a grid, check if it is a valid input.) 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 char g[8][8]; 108 vector<int> r; 109 for (int i = 0; i < 8; i++) { 110 for (int j = 0; j < 8; j++) { 111 cin >> g[i][j]; 112 if (g[i][j] == 'R') {r.push_back(i);} 113 } 114 } 115 for (int i : r) { 116 bool ok = true; 117 for (int j = 0; j < 8; j++) { 118 if (g[i][j] != 'R') {ok = false; break;} 119 } 120 if (ok) {cout << "R\n"; return;} 121 } 122 cout << "B\n"; 123 } 124 125 int main() { 126 ios::sync_with_stdio(false); 127 cin.tie(nullptr); 128 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 129 // solve(); 130 } 131 ``` 132 133 [1742D - Coprime](/contest/1742/problem/D "Codeforces Round 827 (Div. 4)") 134 135 Idea: [badlad](/profile/badlad "Expert badlad"), [SlavicG](/profile/SlavicG "Expert SlavicG") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution** 142 143 ``` 144 #include "bits/stdc++.h" 145 using namespace std; 146 147 #define ll long long 148 149 #define forn(i,n) for(int i=0;i<n;i++) 150 #define all(v) v.begin(), v.end() 151 #define rall(v) v.rbegin(),v.rend() 152 153 #define pb push_back 154 #define sz(a) (int)a.size() 155 156 vector<int> pairs[1001]; 157 void solve() { 158 int n; cin >> n; 159 vector<int> id[1001]; 160 for(int i = 1; i <= n; ++i) { 161 int x; cin >> x; 162 id[x].push_back(i); 163 } 164 int ans = -1; 165 for(int i = 1; i <= 1000; ++i) { 166 for(int j: pairs[i]) { 167 if(!id[i].empty() && !id[j].empty()) { 168 ans = max(ans, id[i].back() + id[j].back()); 169 } 170 } 171 } 172 cout << ans << "\n"; 173 } 174 175 int32_t main() { 176 for(int i = 1; i <= 1000; ++i) { 177 for(int j = 1; j <= 1000; ++j) { 178 if(__gcd(i, j) == 1) { 179 pairs[i].push_back(j); 180 } 181 } 182 } 183 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 184 int t = 1; 185 cin >> t; 186 while(t--) { 187 solve(); 188 } 189 } 190 ``` 191 192 [1742E - Scuza](/contest/1742/problem/E "Codeforces Round 827 (Div. 4)") 193 194 Idea: [mesanu](/profile/mesanu "Expert mesanu") 195 196 **Tutorial** 197 198 Tutorial is loading... 199 200 **Solution** 201 202 ``` 203 #include <bits/stdc++.h> 204 205 using namespace std; 206 207 void solve() 208 { 209 int n, q; 210 cin >> n >> q; 211 vector<long long> pref; 212 pref.push_back(0); 213 vector<int> prefmax; 214 for(int i = 0; i < n; i++) 215 { 216 int x; 217 cin >> x; 218 pref.push_back(pref.back()+x); 219 if(i == 0) 220 { 221 prefmax.push_back(x); 222 } 223 else 224 { 225 prefmax.push_back(max(prefmax.back(), x)); 226 } 227 } 228 for(int i = 0; i < q; i++) 229 { 230 int k; 231 cin >> k; 232 int ind = upper_bound(prefmax.begin(), prefmax.end(), k)-prefmax.begin(); 233 cout << pref[ind] << " "; 234 } 235 cout << endl; 236 } 237 238 int main() 239 { 240 int t; 241 cin >> t; 242 while(t--) 243 { 244 solve(); 245 } 246 } 247 ``` 248 249 [1742F - Smaller](/contest/1742/problem/F "Codeforces Round 827 (Div. 4)") 250 251 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG") 252 253 **Tutorial** 254 255 Tutorial is loading... 256 257 **Solution** 258 259 ``` 260 #include "bits/stdc++.h" 261 using namespace std; 262 263 #define ll long long 264 265 #define forn(i,n) for(int i=0;i<n;i++) 266 #define all(v) v.begin(), v.end() 267 #define rall(v) v.rbegin(),v.rend() 268 269 #define pb push_back 270 #define sz(a) (int)a.size() 271 272 void solve() { 273 int q; cin >> q; 274 bool otherA = false, otherB = false; 275 ll cntA = 0, cntB = 0; 276 while(q--) { 277 ll d, k; string x; cin >> d >> k >> x; 278 for(auto c: x) { 279 if(d == 1) { 280 if(c != 'a') otherA = 1; 281 else cntA += k; 282 } else { 283 if(c != 'a') otherB = 1; 284 else cntB += k; 285 } 286 } 287 if(otherB) { 288 cout << "YES\n"; 289 } else if(!otherA && cntA < cntB) { 290 cout << "YES\n"; 291 } else { 292 cout << "NO\n"; 293 } 294 } 295 } 296 297 int32_t main() { 298 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 299 int t = 1; 300 cin >> t; 301 while(t--) { 302 solve(); 303 } 304 } 305 ``` 306 307 [1742G - Orray](/contest/1742/problem/G "Codeforces Round 827 (Div. 4)") 308 309 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG") 310 311 **Tutorial** 312 313 Tutorial is loading... 314 315 **Solution** 316 317 ``` 318 #include "bits/stdc++.h" 319 using namespace std; 320 321 #define ll long long 322 323 #define forn(i,n) for(int i=0;i<n;i++) 324 #define all(v) v.begin(), v.end() 325 #define rall(v) v.rbegin(),v.rend() 326 327 #define pb push_back 328 #define sz(a) (int)a.size() 329 330 void solve() { 331 int n; cin >> n; 332 vector<int> a(n); 333 forn(i, n) cin >> a[i]; 334 //we care at most about first log2(a) values 335 int cur_or = 0; 336 vector<bool> vis(n, false); 337 for(int i = 0; i < min(31, n); ++i) { 338 int mx = 0, idx = -1; 339 for(int j = 0; j < n; ++j) { 340 if(vis[j]) continue; 341 if((cur_or | a[j]) > mx) { 342 mx = (cur_or | a[j]); 343 idx = j; 344 } 345 } 346 vis[idx] = true; 347 cout << a[idx] << " "; 348 cur_or |= a[idx]; 349 } 350 forn(i, n) if(!vis[i]) cout << a[i] << " "; 351 cout << '\n'; 352 } 353 354 int32_t main() { 355 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 356 int t = 1; 357 cin >> t; 358 while(t--) { 359 solve(); 360 } 361 } 362 ```