codeforces-scrape

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

1926.md (7808B)


      1 Source: https://codeforces.com/blog/entry/126132
      2 
      3 Thank you for participating!
      4 
      5 [1926A - Vlad and the Best of Five](/contest/1926/problem/A "Codeforces Round 928 (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 = 200'007;
     21 const int MOD = 1'000'000'007;
     22  
     23 void solve() {
     24 	string s;
     25 	cin >> s;
     26 	int a = 0, b = 0;
     27 	for (char c : s) {
     28 		if (c == 'A') {a++;}
     29 		else {b++;}
     30 	}	
     31 	cout << (a > b ? 'A' : 'B') << '\n';
     32 }
     33  
     34 int main() {
     35 	ios::sync_with_stdio(false);
     36 	cin.tie(nullptr);
     37 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     38 	// solve();
     39 }
     40 ```
     41 
     42 [1926B - Vlad and Shapes](/contest/1926/problem/B "Codeforces Round 928 (Div. 4)")
     43 
     44 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution**
     51 
     52 ```
     53  #include <iostream>
     54 #include <algorithm>
     55 #include <vector>
     56 #include <array>
     57 #include <set>
     58 #include <map>
     59 #include <queue>
     60 #include <stack>
     61 #include <list>
     62 #include <chrono>
     63 #include <random>
     64 #include <cstdlib>
     65 #include <cmath>
     66 #include <ctime>
     67 #include <cstring>
     68 #include <iomanip>
     69 #include <bitset>
     70 #include <cassert>
     71  
     72 using namespace std;
     73  
     74 void solve()
     75 {
     76     int n;
     77     cin >> n;
     78     vector<string> g;
     79     for(int i = 0; i < n; i++)
     80     {
     81         string s;
     82         cin >> s;
     83         g.push_back(s);
     84     }
     85     bool triangle = false;
     86     for(int i = 0; i < n; i++)
     87     {
     88         int cnt = 0;
     89         for(int j = 0; j < n; j++)
     90         {
     91             if(g[i][j] == '1')
     92             {
     93                 cnt++;
     94             }
     95         }
     96         if(cnt == 1)
     97         {
     98             triangle = true;
     99         }
    100         else if(cnt > 1)
    101         {
    102             break;
    103         }
    104     }
    105     reverse(g.begin(), g.end());
    106     for(int i = 0; i < n; i++)
    107     {
    108         int cnt = 0;
    109         for(int j = 0; j < n; j++)
    110         {
    111             if(g[i][j] == '1')
    112             {
    113                 cnt++;
    114             }
    115         }
    116         if(cnt == 1)
    117         {
    118             triangle = true;
    119         }
    120         else if(cnt > 1)
    121         {
    122             break;
    123         }
    124     }
    125     if(triangle)
    126     {
    127         cout << "TRIANGLE" << endl;
    128     }
    129     else
    130     {
    131         cout << "SQUARE" << endl;
    132     }
    133 }
    134  
    135 int32_t main(){
    136     int t = 1;
    137     cin >> t;
    138     while (t--) {
    139         solve();
    140     }
    141 }
    142 ```
    143 
    144 [1926C - Vlad and a Sum of Sum of Digits](/contest/1926/problem/C "Codeforces Round 928 (Div. 4)")
    145 
    146 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution**
    153 
    154 ```
    155 #include <bits/stdc++.h>
    156  
    157 using namespace std;
    158  
    159 const int MAX = 200'007;
    160 const int MOD = 1'000'000'007;
    161  
    162 int res[MAX];
    163  
    164 int S(int x) {
    165 	int res = 0;
    166 	while (x) {
    167 		res += (x % 10);
    168 		x /= 10;
    169 	}
    170 	return res;
    171 }
    172  
    173 void solve() {
    174 	int x;
    175 	cin >> x;
    176 	cout << res[x] << '\n';
    177 }
    178  
    179 int main() {
    180 	res[0] = 0;
    181 	for (int i = 1; i < MAX; i++) {
    182 		res[i] = res[i - 1] + S(i);
    183 	}
    184 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    185 	// solve();
    186 }
    187 ```
    188 
    189 [1926D - Vlad and Division](/contest/1926/problem/D "Codeforces Round 928 (Div. 4)")
    190 
    191 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    192 
    193 **Tutorial**
    194 
    195 Tutorial is loading...
    196 
    197 **Solution**
    198 
    199 ```
    200 #include "bits/stdc++.h"
    201 using namespace std;
    202  
    203 void solve() {
    204     int n; cin >> n;
    205     map<int, int> cnt;
    206     int ans = 0;
    207     for(int i = 0, x; i < n; ++i) {
    208         cin >> x;
    209         if(!cnt[x]) ++ans, ++cnt[((1 << 31) - 1) ^ x];
    210         else --cnt[x];
    211     }
    212     cout << ans << "\n";
    213 }   
    214  
    215 main() {
    216     int t = 1; cin >> t;
    217     while(t--) {
    218         solve();
    219     }
    220 }
    221 ```
    222 
    223 [1926E - Vlad and an Odd Ordering](/contest/1926/problem/E "Codeforces Round 928 (Div. 4)")
    224 
    225 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    226 
    227 **Tutorial**
    228 
    229 Tutorial is loading...
    230 
    231 **Solution**
    232 
    233 ```
    234 #include <bits/stdc++.h>
    235  
    236 using namespace std;
    237  
    238 const int MAX = 200'007;
    239 const int MOD = 1'000'000'007;
    240  
    241 void solve() {
    242 	int n, k;
    243 	cin >> n >> k;
    244 	vector<int> v;
    245 	while (n) {
    246 		v.push_back((n + 1) / 2);
    247 		n /= 2;
    248 	}
    249 	int tot = 0, pow2 = 1;
    250 	for (int x : v) {
    251 		if (tot < k && k <= tot + x) {
    252 			cout << pow2 * (2 * (k - tot) - 1) << '\n';
    253 			return;
    254 		}
    255 		tot += x;
    256 		pow2 *= 2;
    257 	}
    258 }
    259  
    260 int main() {
    261 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    262 	// solve();
    263 }
    264 ```
    265 
    266 [1926F - Vlad and Avoiding X](/contest/1926/problem/F "Codeforces Round 928 (Div. 4)")
    267 
    268 Idea: [flamestorm](/profile/flamestorm "Candidate Master flamestorm")
    269 
    270 **Tutorial**
    271 
    272 Tutorial is loading...
    273 
    274 **Solution**
    275 
    276 ```
    277 #include <bits/stdc++.h>
    278  
    279 using namespace std;
    280  
    281 const int MAX = 200'007;
    282 const int MOD = 1'000'000'007;
    283  
    284 vector<pair<int, int>> odd, even;
    285  
    286 bool valid(int gc[7][7], bool odd) {
    287 	for (int r = 1; r < 6; r++) {
    288 		for (int c = 1; c < 6; c++) {
    289 			if (gc[r][c] && ((r + c) % 2 == odd)) {
    290 				if (gc[r - 1][c - 1] && gc[r - 1][c + 1] && gc[r + 1][c - 1] && gc[r + 1][c + 1]) {
    291 					return false;
    292 				}
    293 			}
    294 		}
    295 	}
    296 	return true;
    297 }
    298  
    299 bool check(int g[7][7], int flips_left, int idx, vector<pair<int, int>>& vec, int valid_val) {
    300     if (flips_left == 0) {
    301         return valid(g, valid_val);
    302     }
    303     if (idx == vec.size()) {
    304         return false;
    305     }
    306     bool ok = false;
    307     ok |= check(g, flips_left, idx + 1, vec, valid_val);
    308     g[vec[idx].first][vec[idx].second] ^= 1;
    309     ok |= check(g, flips_left - 1, idx + 1, vec, valid_val);
    310     g[vec[idx].first][vec[idx].second] ^= 1;
    311     return ok;
    312 }
    313  
    314 void solve() {
    315     int g[7][7];
    316     for (int i = 0; i < 7; i++) {
    317         for (int j = 0; j < 7; j++) {
    318             char c;
    319             cin >> c;
    320             g[i][j] = (c == 'B');
    321         }
    322     }   
    323     int res = 0;
    324     for (int i = 0; i <= 4; i++) {
    325         if (check(g, i, 0, odd, 1)) {res += i; break;}
    326     }
    327     for (int i = 0; i <= 4; i++) {
    328         if (check(g, i, 0, even, 0)) {res += i; break;}
    329     }
    330     cout << res << '\n';
    331 }
    332 int main() {
    333 	
    334 	for (int i = 0; i < 7; i++) {
    335 		for (int j = 0; j < 7; j++) {
    336 			if ((i + j) % 2) {
    337 				odd.emplace_back(i, j);
    338 			}
    339 			else {
    340 				even.emplace_back(i, j);
    341 			}
    342 		}
    343 	}
    344 	
    345 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    346 }
    347 ```
    348 
    349 [1926G - Vlad and Trouble at MIT](/contest/1926/problem/G "Codeforces Round 928 (Div. 4)")
    350 
    351 Idea: [mesanu](/profile/mesanu "Candidate Master mesanu")
    352 
    353 **Tutorial**
    354 
    355 Tutorial is loading...
    356 
    357 Solution coded by [Dominater069](/profile/Dominater069 "Grandmaster Dominater069"), thanks!
    358 
    359 **Solution**
    360 
    361 ```
    362  #include <bits/stdc++.h>
    363 using namespace std;
    364 #define int long long
    365 #define INF (int)1e18
    366  
    367 int n;
    368 const int N = 1e5 + 69;
    369 int dp[N][3];
    370 string s; 
    371 vector <int> adj[N];
    372  
    373 void dfs(int u){
    374     // dp[u][0] = nothing open 
    375     // dp[u][1] = P open 
    376     // dp[u][2] = S open 
    377     
    378     dp[u][0] = INF;
    379     if (s[u] != 'S') dp[u][1] = 0;
    380     else dp[u][1] = INF;
    381     if (s[u] != 'P') dp[u][2] = 0;
    382     else dp[u][2] = INF;
    383     int tot = 0;
    384     
    385     for (int v : adj[u]){
    386         dfs(v);
    387         dp[u][1] = dp[u][1] + min({dp[v][1], dp[v][2] + 1, dp[v][0]});
    388         dp[u][2] = dp[u][2] + min({dp[v][2], dp[v][1] + 1, dp[v][0]});
    389         tot += dp[v][0];
    390     }
    391     
    392     if (s[u] != 'C') tot = INF;
    393     
    394     dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1});
    395     
    396     //cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << "\n";
    397 }
    398  
    399 void Solve() 
    400 {
    401     cin >> n;
    402     for (int i = 1; i <= n; i++) adj[i].clear();
    403     for (int i = 2; i <= n; i++){
    404         int x; cin >> x;
    405         adj[x].push_back(i);
    406     }
    407     
    408     cin >> s; s = "0" + s;
    409     
    410     dfs(1);
    411     
    412     cout << min({dp[1][0], dp[1][1], dp[1][2]}) << "\n";
    413 }
    414  
    415 int32_t main() 
    416 {
    417     int t = 1;
    418     // freopen("in",  "r", stdin);
    419     // freopen("out", "w", stdout);
    420     
    421     cin >> t;
    422     for(int i = 1; i <= t; i++) 
    423     {
    424         //cout << "Case #" << i << ": ";
    425         Solve();
    426     }
    427     return 0;
    428 }
    429 ```