codeforces-scrape

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

1829.md (7748B)


      1 Source: https://codeforces.com/blog/entry/116108
      2 
      3 We hope you enjoyed the contest!
      4 
      5 [1829A - Love Story](/contest/1829/problem/A "Codeforces Round 871 (Div. 4)")
      6 
      7 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
      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 void solve()
     21 {
     22     string s, c = "codeforces";
     23     cin >> s;
     24     int ans = 0;
     25     for(int i = 0; i < 10; i++)
     26     {
     27         if(s[i] != c[i])
     28         {
     29             ans++;
     30         }
     31     }
     32     cout << ans << endl;
     33 }
     34 
     35 int32_t main(){
     36     int t = 1;
     37     cin >> t;
     38     while (t--) {
     39         solve();
     40     }
     41 }
     42 ```
     43 
     44 [1829B - Blank Space](/contest/1829/problem/B "Codeforces Round 871 (Div. 4)")
     45 
     46 Idea: [mesanu](/profile/mesanu "Expert mesanu")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 using namespace std;
     57 
     58 void solve()
     59 {
     60     int n;
     61     cin >> n;
     62     int a[n];
     63     int cnt = 0, ans = 0;
     64     for(int i = 0; i < n; i++)
     65     {
     66         cin >> a[i];
     67         if(a[i] == 0)
     68         {
     69             cnt++;
     70         }
     71         else
     72         {
     73             ans = max(ans, cnt);
     74             cnt = 0;
     75         }
     76     }
     77     cout << max(ans, cnt) << endl;
     78 }
     79 
     80 int32_t main(){
     81     int t = 1;
     82     cin >> t;
     83     while (t--) {
     84         solve();
     85     }
     86 }
     87 ```
     88 
     89 [1829C - Mr. Perfectly Fine](/contest/1829/problem/C "Codeforces Round 871 (Div. 4)")
     90 
     91 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 #include "bits/stdc++.h"
    101 using namespace std;
    102 
    103 #define ll long long
    104 
    105 #define          all(v)              v.begin(), v.end()
    106 #define         rall(v)              v.rbegin(),v.rend()
    107 
    108 #define            pb                push_back
    109 #define          sz(a)               (int)a.size()
    110 
    111 void solve() {
    112     int n; cin >> n;
    113     map<string, int> mp;
    114     mp["00"] = mp["01"] = mp["10"] = mp["11"] = 1e9;
    115     int ans = 1e9;
    116     for(int i = 0; i < n; ++i) {
    117         int x; cin >> x; string s; cin >> s;
    118         mp[s] = min(mp[s], x);
    119     }
    120     if(min(mp["11"], mp["10"] + mp["01"]) > (int)1e6) {
    121         cout << "-1\n";
    122     } else {
    123         cout << min(mp["11"], mp["10"] + mp["01"]) << "\n";
    124     }
    125 }
    126 
    127 int32_t main() {
    128     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    129     int t = 1;
    130     cin >> t;
    131     while(t--) {
    132         solve();
    133     }
    134 }
    135 ```
    136 
    137 [1829D - Gold Rush](/contest/1829/problem/D "Codeforces Round 871 (Div. 4)")
    138 
    139 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149 
    150 using namespace std;
    151 
    152 bool ok(int n, int m) {
    153 	if (n == m) {return true;}
    154 	else if (n % 3 != 0) {return false;}
    155 	else {return (ok(n / 3, m) || ok(2 * n / 3, m));}
    156 }
    157 
    158 void solve() {
    159 	int n, m;
    160 	cin >> n >> m;
    161 	cout << (ok(n, m) ? "YES" : "NO") << '\n';
    162 }
    163 
    164 int main() {
    165 	ios::sync_with_stdio(false);
    166 	cin.tie(nullptr);
    167 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    168 	// solve();
    169 }
    170 ```
    171 
    172 [1829E - The Lakes](/contest/1829/problem/E "Codeforces Round 871 (Div. 4)")
    173 
    174 Idea: [mesanu](/profile/mesanu "Expert mesanu")
    175 
    176 **Tutorial**
    177 
    178 Tutorial is loading...
    179 
    180 **Solution**
    181 
    182 ```
    183 #include <bits/stdc++.h>
    184 #define startt ios_base::sync_with_stdio(false);cin.tie(0);
    185 typedef long long  ll;
    186 using namespace std;
    187 #define vint vector<int>
    188 #define all(v) v.begin(), v.end()
    189 #define MOD 1000000007
    190 #define MOD2 998244353
    191 #define MX 1000000000
    192 #define MXL 1000000000000000000
    193 #define PI (ld)2*acos(0.0)
    194 #define pb push_back
    195 #define sc second
    196 #define fr first
    197 #define endl '\n'
    198 #define ld long double
    199 #define NO cout << "NO" << endl
    200 #define YES cout << "YES" << endl
    201 
    202 int n, m;
    203 bool vis[1005][1005];
    204 int a[1005][1005];
    205 
    206 int dfs(int i, int j)
    207 {
    208     vis[i][j] = true;
    209     int ans = a[i][j];
    210     if(i != 0 && a[i-1][j] != 0 && !vis[i-1][j])
    211     {
    212         ans+=dfs(i-1, j);
    213     }
    214     if(i != n-1 && a[i+1][j] != 0 && !vis[i+1][j])
    215     {
    216         ans+=dfs(i+1, j);
    217     }
    218     if(j != 0 && a[i][j-1] != 0 && !vis[i][j-1])
    219     {
    220         ans+=dfs(i, j-1);
    221     }
    222     if(j != m-1 && a[i][j+1] != 0 && !vis[i][j+1])
    223     {
    224         ans+=dfs(i, j+1);
    225     }
    226     return ans;
    227 }
    228 
    229 void solve()
    230 {
    231     cin >> n >> m;
    232     for(int i = 0; i < n; i++)
    233     {
    234         for(int j = 0; j < m; j++)
    235         {
    236             vis[i][j] = false;
    237             cin >> a[i][j];
    238         }
    239     }
    240     int ans = 0;
    241     for(int i = 0; i < n; i++)
    242     {
    243         for(int j = 0; j < m; j++)
    244         {
    245             if(!vis[i][j] && a[i][j] != 0)
    246             {
    247                 ans = max(ans, dfs(i, j));
    248             }
    249         }
    250     }
    251     cout << ans << endl;
    252 }
    253 
    254 int32_t main(){
    255     startt
    256     int t = 1;
    257     cin >> t;
    258     while (t--) {
    259         solve();
    260     }
    261 }
    262 ```
    263 
    264 [1829F - Forever Winter](/contest/1829/problem/F "Codeforces Round 871 (Div. 4)")
    265 
    266 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution**
    273 
    274 ```
    275 #include <bits/stdc++.h>
    276 
    277 using namespace std;
    278 
    279 const int MAX = 200007;
    280 const int MOD = 1000000007;
    281 
    282 void solve() {
    283 	int n, m;
    284 	cin >> n >> m;
    285 	int cnt[n + 1];
    286 	for (int i = 1; i <= n; i++) {
    287 		cnt[i] = 0;
    288 	}
    289 	for (int i = 0; i < m; i++) {
    290 		int u, v;
    291 		cin >> u >> v;
    292 		cnt[u]++;
    293 		cnt[v]++;
    294 	}
    295 	map<int, int> cnts;
    296 	for (int i = 1; i <= n; i++) {
    297 		cnts[cnt[i]]++;
    298 	}
    299 	vector<int> v;
    300 	for (auto p : cnts) {
    301 		v.push_back(p.second);
    302 	}
    303 	sort(v.begin(), v.end());
    304 	if (v.size() == 3) {
    305 		cout << v[1] << ' ' << v[2] / v[1] << '\n';
    306 	}
    307 	else {
    308 		cout << v[0] - 1 << ' ' << v[1] / (v[0] - 1) << '\n';
    309 	}
    310 }
    311 
    312 int main() {
    313 	ios::sync_with_stdio(false);
    314 	cin.tie(nullptr);
    315 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    316 	// solve();
    317 }
    318 ```
    319 
    320 [1829G - Hits Different](/contest/1829/problem/G "Codeforces Round 871 (Div. 4)")
    321 
    322 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    323 
    324 **Tutorial**
    325 
    326 Tutorial is loading...
    327 
    328 **Solution**
    329 
    330 ```
    331 #include <bits/stdc++.h>
    332 
    333 using namespace std;
    334 
    335 long long ans[2000007];
    336 long long a[1500][1500] = {}, curr = 1;
    337 
    338 void solve() {
    339 	int n;
    340 	cin >> n;
    341 	cout << ans[n] << '\n';
    342 }
    343 
    344 int main() {
    345 	ios::sync_with_stdio(false);
    346 	cin.tie(nullptr);
    347 
    348 	for (int i = 1; i < 1500; i++) {
    349 		for (int j = i - 1; j >= 1; j--) {
    350 			a[j][i - j] = a[j - 1][i - j] + a[j][i - j - 1] - a[j - 1][i - j - 1] + curr * curr;
    351 			ans[curr] = a[j][i - j];
    352 			curr++;
    353 		}
    354 	}
    355 	
    356 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    357 	// solve();
    358 }
    359 ```
    360 
    361 [1829H - Don't Blame Me](/contest/1829/problem/H "Codeforces Round 871 (Div. 4)")
    362 
    363 Idea: [SlavicG](/profile/SlavicG "Candidate Master SlavicG")
    364 
    365 **Tutorial**
    366 
    367 Tutorial is loading...
    368 
    369 **Solution**
    370 
    371 ```
    372 #include "bits/stdc++.h"
    373 using namespace std;
    374 
    375 #define ll long long
    376  
    377 #define          all(v)              v.begin(), v.end()
    378 #define         rall(v)              v.rbegin(),v.rend()
    379  
    380 #define            pb                push_back
    381 #define          sz(a)               (int)a.size()
    382 
    383 const int mod = 1e9 + 7;
    384 void solve() {
    385     int n, x; cin >> n >> x;
    386     vector<int> a(n + 1);
    387     vector<vector<int>> dp(n + 1, vector<int>(1 << 6, 0));
    388     for(int i = 1; i <= n; ++i) {
    389         cin >> a[i];
    390         for(int mask = 0; mask < (1 << 6); ++mask) {
    391             dp[i][mask] += dp[i - 1][mask];
    392             if(dp[i][mask] >= mod) dp[i][mask] -= mod;
    393             dp[i][mask & a[i]] += dp[i - 1][mask];
    394             if(dp[i][mask & a[i]] >= mod) dp[i][mask & a[i]] -= mod;
    395         }
    396         dp[i][a[i]] = (dp[i][a[i]] + 1) % mod;
    397     }
    398     int ans = 0;
    399     for(int mask = 0; mask < (1 << 6); ++mask) {
    400         if(__builtin_popcount(mask) == x) {
    401             ans = (ans + dp[n][mask]) % mod;
    402         }
    403     }
    404     cout << ans << "\n";
    405 }   
    406  
    407 int32_t main() {
    408     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    409     int t = 1;
    410     cin >> t;
    411     while(t--) {
    412         solve();
    413     }
    414 }
    415 ```