codeforces-scrape

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

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