1850.md (7715B)
1 Source: https://codeforces.com/blog/entry/118466 2 3 Thank you for participating! 4 5 [1850A - To My Critics](/contest/1850/problem/A "Codeforces Round 886 (Div. 4)") 6 7 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 void solve() 20 { 21 int a, b, c; 22 cin >> a >> b >> c; 23 cout << (a+b+c-min({a,b,c}) >= 10 ? "YES\n" : "NO\n"); 24 25 } 26 27 int main() 28 { 29 int t; 30 cin >> t; 31 while(t--) 32 { 33 solve(); 34 } 35 } 36 ``` 37 38 [1850B - Ten Words of Wisdom](/contest/1850/problem/B "Codeforces Round 886 (Div. 4)") 39 40 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 const int MAX = 200007; 54 const int MOD = 1000000007; 55 56 void solve() { 57 int n; 58 cin >> n; 59 int winner = -1, best_score = 0; 60 for (int i = 1; i <= n; i++) { 61 int a, b; 62 cin >> a >> b; 63 if (b > best_score && a <= 10) {winner = i; best_score = b;} 64 } 65 cout << winner << '\n'; 66 } 67 68 int main() { 69 ios::sync_with_stdio(false); 70 cin.tie(nullptr); 71 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 72 // solve(); 73 } 74 ``` 75 76 [1850C - Word on the Paper](/contest/1850/problem/C "Codeforces Round 886 (Div. 4)") 77 78 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution** 85 86 ``` 87 #include <bits/stdc++.h> 88 89 using namespace std; 90 91 const int MAX = 200007; 92 const int MOD = 1000000007; 93 94 void solve() { 95 for (int r = 0; r < 8; r++) { 96 for (int c = 0; c < 8; c++) { 97 char x; 98 cin >> x; 99 if (x != '.') {cout << x;} 100 } 101 } 102 cout << '\n'; 103 } 104 105 int main() { 106 ios::sync_with_stdio(false); 107 cin.tie(nullptr); 108 int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} 109 // solve(); 110 } 111 ``` 112 113 [1850D - Balanced Round](/contest/1850/problem/D "Codeforces Round 886 (Div. 4)") 114 115 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution** 122 123 ``` 124 #include "bits/stdc++.h" 125 using namespace std; 126 127 #define ll long long 128 129 #define all(v) v.begin(), v.end() 130 #define rall(v) v.rbegin(),v.rend() 131 132 #define pb push_back 133 #define sz(a) (int)a.size() 134 135 void solve() { 136 int n, k; cin >> n >> k; 137 vector<int> a(n); 138 for(int i = 0; i < n; ++i) cin >> a[i]; 139 sort(all(a)); 140 int cnt = 1, ans = 1; 141 for(int i = 1; i < n; ++i) { 142 if(a[i] - a[i - 1] > k) { 143 cnt = 1; 144 } else { 145 ++cnt; 146 } 147 ans = max(ans, cnt); 148 } 149 cout << n - ans << '\n'; 150 } 151 152 int32_t main() { 153 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 154 int t = 1; 155 cin >> t; 156 while(t--) { 157 solve(); 158 } 159 } 160 ``` 161 162 [1850E - Cardboard for Pictures](/contest/1850/problem/E "Codeforces Round 886 (Div. 4)") 163 164 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 165 166 **Tutorial** 167 168 Tutorial is loading... 169 170 **Solution** 171 172 ``` 173 #include "bits/stdc++.h" 174 using namespace std; 175 176 #define ll long long 177 178 #define all(v) v.begin(), v.end() 179 #define rall(v) v.rbegin(),v.rend() 180 181 #define pb push_back 182 #define sz(a) (int)a.size() 183 184 #define int long long 185 186 void solve() { 187 int n, c; cin >> n >> c; 188 vector<int> a(n); 189 for(int i = 0; i < n; ++i) cin >> a[i]; 190 int l = 1, r = 1e9; 191 while(l <= r) { 192 int mid = l + (r - l) / 2; 193 int sumall = 0; 194 for(int i = 0; i < n; ++i) { 195 sumall += (a[i] + 2 * mid) * (a[i] + 2 * mid); 196 if(sumall > c) break; 197 } 198 if(sumall == c) { 199 cout << mid << "\n"; 200 return; 201 } 202 if(sumall > c) { 203 r = mid - 1; 204 } else { 205 l = mid + 1; 206 } 207 } 208 } 209 210 int32_t main() { 211 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 212 int t = 1; 213 cin >> t; 214 while(t--) { 215 solve(); 216 } 217 } 218 ``` 219 220 [1850F - We Were Both Children](/contest/1850/problem/F "Codeforces Round 886 (Div. 4)") 221 222 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu") & [SlavicG](/profile/SlavicG "Expert SlavicG") 223 224 **Tutorial** 225 226 Tutorial is loading... 227 228 **Solution** 229 230 ``` 231 #include "bits/stdc++.h" 232 using namespace std; 233 234 #define ll long long 235 236 #define all(v) v.begin(), v.end() 237 #define rall(v) v.rbegin(),v.rend() 238 239 #define pb push_back 240 #define sz(a) (int)a.size() 241 242 void solve() { 243 int n; cin >> n; 244 vector<ll> cnt(n + 1, 0), mx(n + 1, 0); 245 for(int i = 0; i < n; ++i) { 246 int x; cin >> x; 247 if(x <= n) ++cnt[x]; 248 } 249 for(int i = 1; i <= n; ++i) { 250 for(int j = i; j <= n; j += i) mx[j] += cnt[i]; 251 } 252 cout << *max_element(all(mx)) << "\n"; 253 } 254 255 int32_t main() { 256 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 257 int t = 1; 258 cin >> t; 259 while(t--) { 260 solve(); 261 } 262 } 263 ``` 264 265 [1850G - The Morning Star](/contest/1850/problem/G "Codeforces Round 886 (Div. 4)") 266 267 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm") 268 269 **Tutorial** 270 271 Tutorial is loading... 272 273 **Solution** 274 275 ``` 276 #include <bits/stdc++.h> 277 #define startt ios_base::sync_with_stdio(false);cin.tie(0); 278 typedef long long ll; 279 using namespace std; 280 #define vint vector<int> 281 #define all(v) v.begin(), v.end() 282 #define int long long 283 284 void solve() 285 { 286 int n; 287 cin >> n; 288 map<int, int> up, side, diag1, diag2; 289 int ans = 0; 290 for(int i = 0; i < n; i++) 291 { 292 int x, y; 293 cin >> x >> y; 294 up[x]++; 295 side[y]++; 296 diag1[x-y]++; 297 diag2[x+y]++; 298 } 299 for(auto x : up) 300 { 301 ans+=x.second*(x.second-1); 302 } 303 for(auto x : side) 304 { 305 ans+=x.second*(x.second-1); 306 } 307 for(auto x : diag1) 308 { 309 ans+=x.second*(x.second-1); 310 }for(auto x : diag2) 311 { 312 ans+=x.second*(x.second-1); 313 } 314 cout << ans << endl; 315 } 316 317 int32_t main(){ 318 startt 319 int t = 1; 320 cin >> t; 321 while (t--) { 322 solve(); 323 } 324 } 325 ``` 326 327 [1850H - The Third Letter](/contest/1850/problem/H "Codeforces Round 886 (Div. 4)") 328 329 Idea: [SlavicG](/profile/SlavicG "Expert SlavicG") 330 331 **Tutorial** 332 333 Tutorial is loading... 334 335 **Solution** 336 337 ``` 338 #include "bits/stdc++.h" 339 using namespace std; 340 341 #define ll long long 342 343 #define all(v) v.begin(), v.end() 344 #define rall(v) v.rbegin(),v.rend() 345 346 #define pb push_back 347 #define sz(a) (int)a.size() 348 349 #define int long long 350 const int N = 2e5 + 5; 351 vector<pair<int, int>> adj[N]; 352 int val[N], vis[N]; 353 void dfs(int u) { 354 vis[u] = 1; 355 for(auto x: adj[u]) { 356 int v = x.first, w = x.second; 357 if(!vis[v]) { 358 val[v] = val[u] + w; 359 dfs(v); 360 } 361 } 362 } 363 void solve() { 364 int n, m; cin >> n >> m; 365 for(int i = 1; i <= n; ++i) { 366 adj[i].clear(); 367 vis[i] = 0, val[i] = 0; 368 } 369 vector<array<int, 3>> c; 370 for(int i = 1; i <= m; ++i) { 371 int a, b, d; cin >> a >> b >> d; 372 adj[a].pb({b, d}); 373 adj[b].pb({a, -d}); 374 c.pb({a, b, d}); 375 } 376 for(int i = 1; i <= n; ++i) { 377 if(!vis[i]) dfs(i); 378 } 379 for(int i = 1; i <= m; ++i) { 380 int a = c[i - 1][0], b = c[i - 1][1], d = c[i - 1][2]; 381 if(val[a] + d != val[b]) { 382 cout << "NO\n"; 383 return; 384 } 385 } 386 cout << "YES\n"; 387 } 388 389 int32_t main() { 390 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 391 int t = 1; 392 cin >> t; 393 while(t--) { 394 solve(); 395 } 396 } 397 ```