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