1760.md (6996B)
1 Source: https://codeforces.com/blog/entry/109348 2 3 We hope you enjoyed the contest! Sorry for the late editorial. 4 5 [1760A - Medium Number](/contest/1760/problem/A "Codeforces Round 835 (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[3]; 25 cin >> a[0] >> a[1] >> a[2]; 26 sort(a, a + 3); 27 cout << a[1] << '\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 [1760B - Atilla's Favorite Problem](/contest/1760/problem/B "Codeforces Round 835 (Div. 4)") 39 40 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution** 47 48 ``` 49 #include "bits/stdc++.h" 50 using namespace std; 51 52 using ll = long long; 53 54 #define forn(i,n) for(int i=0;i<n;i++) 55 #define all(v) v.begin(), v.end() 56 #define rall(v) v.rbegin(),v.rend() 57 58 #define pb push_back 59 #define sz(a) (int)a.size() 60 61 void solve() { 62 int n; string s; cin >> n >> s; 63 sort(all(s)); 64 cout << s.back() - 'a' + 1 << "\n"; 65 } 66 67 int32_t main() { 68 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 69 int t = 1; 70 cin >> t; 71 while(t--) { 72 solve(); 73 } 74 } 75 ``` 76 77 [1760C - Advantage](/contest/1760/problem/C "Codeforces Round 835 (Div. 4)") 78 79 Idea: [Errichto](/profile/Errichto "International Grandmaster Errichto") 80 81 **Tutorial** 82 83 Tutorial is loading... 84 85 **Solution** 86 87 ``` 88 #include <bits/stdc++.h> 89 90 using namespace std; 91 92 #define forn(i, n) for (int i = 0; i < int(n); i++) 93 94 int main() { 95 int t; 96 cin >> t; 97 forn(tt, t) { 98 int n; 99 cin >> n; 100 vector<int> a(n); 101 forn(i, n) 102 cin >> a[i]; 103 vector<int> b(a); 104 sort(b.begin(), b.end()); 105 forn(i, n) { 106 if (a[i] == b[n - 1]) 107 cout << a[i] - b[n - 2] << " "; 108 else 109 cout << a[i] - b[n - 1] << " "; 110 } 111 cout << endl; 112 } 113 } 114 ``` 115 116 [1760D - Challenging Valleys](/contest/1760/problem/D "Codeforces Round 835 (Div. 4)") 117 118 Idea: [mesanu](/profile/mesanu "Expert mesanu") 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution** 125 126 ``` 127 #include <bits/stdc++.h> 128 using namespace std; 129 void solve() 130 { 131 int n; 132 cin >> n; 133 vector<int> a; 134 for(int i = 0; i < n; i++) 135 { 136 int x; 137 cin >> x; 138 if(i == 0 || x != a.back()) 139 { 140 a.push_back(x); 141 } 142 } 143 int num_valley = 0; 144 for(int i = 0; i < a.size(); i++) 145 { 146 if((i == 0 || a[i-1] > a[i]) && (i == a.size()-1 || a[i] < a[i+1])) 147 { 148 num_valley++; 149 } 150 } 151 if(num_valley == 1) 152 { 153 cout << "YES" << endl; 154 } 155 else 156 { 157 cout << "NO" << endl; 158 } 159 } 160 161 int32_t main(){ 162 int t = 1; 163 cin >> t; 164 while (t--) { 165 solve(); 166 } 167 } 168 ``` 169 170 [1760E - Binary Inversions](/contest/1760/problem/E "Codeforces Round 835 (Div. 4)") 171 172 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution** 179 180 ``` 181 #include "bits/stdc++.h" 182 using namespace std; 183 184 using ll = long long; 185 186 #define forn(i,n) for(int i=0;i<n;i++) 187 #define all(v) v.begin(), v.end() 188 #define rall(v) v.rbegin(),v.rend() 189 190 #define pb push_back 191 #define sz(a) (int)a.size() 192 193 ll calc(vector<int>& a) { 194 ll zeroes = 0, ans = 0; 195 for(int i = sz(a) - 1; i >= 0; --i) { 196 if(a[i] == 0) ++zeroes; 197 else ans += zeroes; 198 } 199 return ans; 200 } 201 void solve() { 202 int n; cin >> n; 203 vector<int> a(n); 204 forn(i, n) cin >> a[i]; 205 ll ans = calc(a); 206 forn(i, n) { 207 if(a[i] == 0) { 208 a[i] = 1; 209 ans = max(ans, calc(a)); 210 a[i] = 0; 211 break; 212 } 213 } 214 for(int i = n - 1; i >= 0; --i) { 215 if(a[i] == 1) { 216 a[i] = 0; 217 ans = max(ans, calc(a)); 218 a[i] = 1; 219 break; 220 } 221 } 222 cout << ans << "\n"; 223 } 224 225 int32_t main() { 226 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 227 int t = 1; 228 cin >> t; 229 while(t--) { 230 solve(); 231 } 232 } 233 ``` 234 235 [1760F - Quests](/contest/1760/problem/F "Codeforces Round 835 (Div. 4)") 236 237 Idea: [flamestorm](/profile/flamestorm "Expert flamestorm") 238 239 **Tutorial** 240 241 Tutorial is loading... 242 243 **Solution** 244 245 ``` 246 #include <bits/stdc++.h> 247 248 using namespace std; 249 250 const int MAX = 200007; 251 const int MOD = 1000000007; 252 253 void solve() { 254 int n, d; 255 long long c; 256 cin >> n >> c >> d; 257 long long a[n]; 258 for (int i = 0; i < n; i++) { 259 cin >> a[i]; 260 } 261 sort(a, a + n, greater<long long>()); 262 int l = 0, r = d + 2; 263 while (l < r) { 264 int m = l + (r - l + 1) / 2; 265 long long tot = 0; 266 int curr = 0; 267 for (int i = 0; i < d; i++) { 268 if (i % m < n) {tot += a[i % m];} 269 } 270 if (tot >= c) { 271 l = m; 272 } 273 else { 274 r = m - 1; 275 } 276 } 277 if (l == d + 2) {cout << "Infinity\n"; return;} 278 if (l == 0) {cout << "Impossible\n"; return;} 279 cout << l - 1 << '\n'; 280 } 281 282 int main() { 283 ios::sync_with_stdio(false); 284 cin.tie(nullptr); 285 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 286 // solve(); 287 } 288 ``` 289 290 [1760G - SlavicG's Favorite Problem](/contest/1760/problem/G "Codeforces Round 835 (Div. 4)") 291 292 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG") 293 294 **Tutorial** 295 296 Tutorial is loading... 297 298 **Solution** 299 300 ``` 301 #include "bits/stdc++.h" 302 using namespace std; 303 304 using ll = long long; 305 306 #define forn(i,n) for(int i=0;i<n;i++) 307 #define all(v) v.begin(), v.end() 308 #define rall(v) v.rbegin(),v.rend() 309 310 #define pb push_back 311 #define sz(a) (int)a.size() 312 313 const int N = 1e5 + 10; 314 vector<pair<int, int>> adj[N]; 315 set<int> s; 316 bool ok = true; 317 int n, a, b; 318 void dfs1(int u, int par, int x) { 319 if(u == b) return; 320 s.insert(x); 321 for(auto e: adj[u]) { 322 int v = e.first, w = e.second; 323 if(v == par) continue; 324 dfs1(v, u, x ^ w); 325 } 326 } 327 328 bool dfs2(int u, int par, int x) { 329 if(u != b && s.count(x)) return true; 330 for(auto e: adj[u]) { 331 int v = e.first, w = e.second; 332 if(v == par) continue; 333 if(dfs2(v, u, w ^ x)) return true; 334 } 335 return false; 336 } 337 338 void solve() { 339 s.clear(); 340 cin >> n >> a >> b; --a, --b; 341 forn(i, n) adj[i].clear(); 342 for(int i = 0; i < n - 1; ++i) { 343 int u, v, w; cin >> u >> v >> w; --u, --v; 344 adj[u].pb({v, w}); 345 adj[v].pb({u, w}); 346 } 347 dfs1(a, -1, 0); 348 if(dfs2(b, -1, 0)) cout << "YES\n"; 349 else cout << "NO\n"; 350 } 351 352 int32_t main() { 353 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 354 int t = 1; 355 cin >> t; 356 while(t--) { 357 solve(); 358 } 359 } 360 ```