codeforces-scrape

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

1873.md (8025B)


      1 Source: https://codeforces.com/blog/entry/120634
      2 
      3 Thank you for participating!
      4 
      5 [1873A - Short Sort](/contest/1873/problem/A "Codeforces Round 898 (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 string alph = "abc";
     24  
     25 void solve() {
     26 	string s;
     27 	cin >> s;
     28 	int cnt = 0;
     29 	for (int i = 0; i < 3; i++) {
     30 		cnt += (s[i] != alph[i]);
     31 	}
     32 	cout << (cnt <= 2 ? "YES\n" : "NO\n");
     33 }
     34  
     35 int main() {
     36 	ios::sync_with_stdio(false);
     37 	cin.tie(nullptr);
     38 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     39 	// solve();
     40 }
     41 ```
     42 
     43 [1873B - Good Kid](/contest/1873/problem/B "Codeforces Round 898 (Div. 4)")
     44 
     45 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 using namespace std;
     56  
     57 void solve()
     58 {
     59     int n;
     60     cin >> n;
     61     vector<int> a(n);
     62     int ans = 1;
     63     for(int i = 0; i < n; i++)
     64     {
     65         cin >> a[i];
     66     }
     67     sort(a.begin(), a.end());
     68     a[0]++;
     69     for(int i = 0; i < n; i++)
     70     {
     71         ans*=a[i];
     72     }
     73     cout << ans << endl;
     74 }
     75  
     76 int32_t main(){
     77     int t = 1;
     78     cin >> t;
     79     while (t--) {
     80         solve();
     81     }
     82 }
     83 ```
     84 
     85 [1873C - Target Practice](/contest/1873/problem/C "Codeforces Round 898 (Div. 4)")
     86 
     87 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97  
     98 using namespace std;
     99  
    100 const int MAX = 200007;
    101 const int MOD = 1000000007;
    102  
    103 int score[10][10] = {
    104 	{1,1,1,1,1,1,1,1,1,1},
    105 	{1,2,2,2,2,2,2,2,2,1},
    106 	{1,2,3,3,3,3,3,3,2,1},
    107 	{1,2,3,4,4,4,4,3,2,1},
    108 	{1,2,3,4,5,5,4,3,2,1},
    109 	{1,2,3,4,5,5,4,3,2,1},
    110 	{1,2,3,4,4,4,4,3,2,1},
    111 	{1,2,3,3,3,3,3,3,2,1},
    112 	{1,2,2,2,2,2,2,2,2,1},
    113 	{1,1,1,1,1,1,1,1,1,1}
    114 };
    115  
    116 void solve() {
    117 	int ans = 0;
    118 	for (int i = 0; i < 10; i++) {
    119 		for (int j = 0; j < 10; j++) {
    120 			char c;
    121 			cin >> c;
    122 			if (c == 'X') {ans += score[i][j];}
    123 		}
    124 	}
    125 	cout << ans << '\n';
    126 }
    127  
    128 int main() {
    129 	ios::sync_with_stdio(false);
    130 	cin.tie(nullptr);
    131 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    132 	// solve();
    133 }
    134 ```
    135 
    136 [1873D - 1D Eraser](/contest/1873/problem/D "Codeforces Round 898 (Div. 4)")
    137 
    138 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    139 
    140 **Tutorial**
    141 
    142 Tutorial is loading...
    143 
    144 **Solution**
    145 
    146 ```
    147 #include <bits/stdc++.h>
    148  
    149 using namespace std;
    150  
    151 const int MAX = 200'007;
    152 const int MOD = 1'000'000'007;
    153  
    154 void solve() {
    155 	int n, k;
    156 	cin >> n >> k;
    157 	string s;
    158 	cin >> s;
    159 	int res = 0;
    160 	for (int i = 0; i < n; i++) {
    161 		if (s[i] == 'B') {
    162 			res++; i += k - 1;
    163 		}
    164 	}
    165 	cout << res << '\n';
    166 }
    167  
    168 int main() {
    169 	ios::sync_with_stdio(false);
    170 	cin.tie(nullptr);
    171 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    172 	// solve();
    173 }
    174 ```
    175 
    176 [1873E - Building an Aquarium](/contest/1873/problem/E "Codeforces Round 898 (Div. 4)")
    177 
    178 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    179 
    180 **Tutorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188  
    189 using namespace std;
    190  
    191 const int MAX = 200'007;
    192 const int MOD = 1'000'000'007;
    193  
    194 void solve() {
    195 	int n;
    196 	long long x;
    197 	cin >> n >> x;
    198 	long long a[n];
    199 	for (int i = 0; i < n; i++) {
    200 		cin >> a[i];
    201 	}
    202 	long long lo = 0, hi = 2'000'000'007;
    203 	while (lo < hi) {
    204 		long long mid = lo + (hi - lo + 1) / 2;
    205 		long long tot = 0;
    206 		for (int i = 0; i < n; i++) {
    207 			tot += max(mid - a[i], 0LL);
    208 		}
    209 		if (tot <= x) {lo = mid;} 
    210 		else {hi = mid - 1;}
    211 	}
    212 	cout << lo << endl;
    213 }
    214  
    215 int main() {
    216 	ios::sync_with_stdio(false);
    217 	cin.tie(nullptr);
    218 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    219 	// solve();
    220 }
    221 ```
    222 
    223 [1873F - Money Trees](/contest/1873/problem/F "Codeforces Round 898 (Div. 4)")
    224 
    225 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235 using namespace std;
    236  
    237 const int N = 200'000;
    238  
    239 int n, k;
    240 int a[N+5], h[N+5], pref[N+5], length[N+5];
    241  
    242 bool get(int dist)
    243 {
    244     bool found = false;
    245     for(int i = 0; i < n-dist+1; i++)
    246     {
    247         if(length[i] < dist){continue;}
    248         int sum = pref[i+dist]-pref[i];
    249         if(sum <= k)
    250         {
    251             found = true;
    252             break;
    253         }
    254     }
    255     return found;
    256 }
    257  
    258 void solve()
    259 {
    260     pref[0] = 0;
    261     cin >> n >> k;
    262     for(int i = 0; i < n; i++)
    263     {
    264         cin >> a[i];
    265         pref[i+1] = pref[i]+a[i];
    266     }
    267     for(int i = 0; i < n; i++)
    268     {
    269         cin >> h[i];
    270     }
    271     length[n-1] = 1;
    272     for(int i = n-2; i >= 0; i--)
    273     {
    274         if(h[i]%h[i+1] == 0)
    275         {
    276             length[i] = length[i+1]+1;
    277         }
    278         else
    279         {
    280             length[i] = 1;
    281         }
    282     }
    283     int l = 1, r = N;
    284     while(l <= r)
    285     {
    286         int mid = (l+r)/2;
    287         if(get(mid))
    288         {
    289             l = mid+1;
    290         }
    291         else
    292         {
    293             r = mid-1;
    294         }
    295     }
    296     cout << r << endl;
    297 }
    298  
    299 int main() {
    300     int t = 1;
    301     cin >> t;
    302     while (t--)
    303     {
    304         solve();
    305     }
    306 }
    307 ```
    308 
    309 [1873G - ABBC or BACB](/contest/1873/problem/G "Codeforces Round 898 (Div. 4)")
    310 
    311 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    312 
    313 **Tutorial**
    314 
    315 Tutorial is loading...
    316 
    317 **Solution**
    318 
    319 ```
    320 #include <bits/stdc++.h>
    321  
    322 using namespace std;
    323  
    324 const int MAX = 200'007;
    325 const int MOD = 1'000'000'007;
    326  
    327 void solve() {
    328 	string s;
    329 	cin >> s;
    330 	int n = s.length(), cnt = 0;
    331 	bool all = (s[0] == 'B' || s[n - 1] == 'B');
    332 	for (int i = 0; i < n - 1; i++) {
    333 		if (s[i] == s[i + 1] && s[i] == 'B') {all = true;}
    334 	}
    335 	vector<int> lens;
    336 	int curr = 0;
    337 	for (int i = 0; i < n; i++) {
    338 		if (s[i] == 'A') {curr++;}
    339 		else {
    340 			if (curr != 0) {lens.push_back(curr);}
    341 			curr = 0;
    342 		}
    343 	}
    344 	if (curr != 0) {lens.push_back(curr);}
    345 	sort(lens.begin(), lens.end());
    346 	
    347 	if (lens.empty()) {cout << 0 << '\n'; return;}
    348 	
    349 	int tot = 0;
    350 	if (all) {tot += lens[0];}
    351 	for (int i = 1; i < lens.size(); i++) {
    352 		tot += lens[i];
    353 	}
    354 	cout << tot << '\n';
    355 }
    356  
    357 int main() {
    358 	ios::sync_with_stdio(false);
    359 	cin.tie(nullptr);
    360 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    361 	// solve();
    362 }
    363 ```
    364 
    365 [1873H - Mad City](/contest/1873/problem/H "Codeforces Round 898 (Div. 4)")
    366 
    367 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    368 
    369 **Tutorial**
    370 
    371 Tutorial is loading...
    372 
    373 **Solution**
    374 
    375 ```
    376 #include <bits/stdc++.h>
    377  
    378 using namespace std;
    379  
    380 const int N = 200005;
    381  
    382 vector<int> adj[N];
    383 vector<bool> vis(N);
    384  
    385 int entry_node = -1;
    386 vector<int> path;
    387  
    388 bool dfs1(int u, int p)
    389 {
    390     vis[u] = true;
    391     for(auto v : adj[u])
    392     {
    393         if(v != p && vis[v])
    394         {
    395             entry_node = v;
    396             return true;
    397         }
    398         else if(v != p && !vis[v])
    399         {
    400             if(dfs1(v, u))
    401             {
    402                 return true;
    403             }
    404         }
    405     }
    406     return false;
    407 }
    408  
    409 int dfs2(int u)
    410 {
    411     vis[u] = true;
    412     int distbruh = N;
    413     for(auto v : adj[u])
    414     {
    415         if(v == entry_node)
    416         {
    417             return 1;
    418         }
    419         if(!vis[v])
    420         {
    421             int dist = dfs2(v)+1;
    422             distbruh = min(dist, distbruh);
    423         }
    424     }
    425     return distbruh;
    426 }
    427  
    428 void solve()
    429 {
    430     int n, a, b;
    431     cin >> n >> a >> b;
    432     for(int i = 0; i < n; i++)
    433     {
    434         int u, v;
    435         cin >> u >> v;
    436         adj[u].push_back(v);
    437         adj[v].push_back(u);
    438     }
    439     dfs1(b, -1);
    440     vis.assign(n+1, false);
    441     int distMarcel = N, distValeriu = 0;
    442     if(entry_node == a)
    443     {
    444         distMarcel = 0;
    445     }
    446     else
    447     {
    448         distMarcel = dfs2(a);
    449     }
    450     vis.assign(n+1, false);
    451     if(entry_node == b)
    452     {
    453         distValeriu = 0;
    454     }
    455     else
    456     {
    457         distValeriu = dfs2(b);
    458     }
    459     if(distValeriu < distMarcel)
    460     {
    461         cout << "YES" << endl;
    462     }
    463     else
    464     {
    465         cout << "NO" << endl;
    466     }
    467     for(int i = 1; i <= n; i++)
    468     {
    469         adj[i].clear();
    470         vis[i] = false;
    471     }
    472 }
    473  
    474 int32_t main(){
    475     int t = 1;
    476     cin >> t;
    477     while (t--) {
    478         solve();
    479     }
    480 }
    481 ```