2121.md (7354B)
1 Source: https://codeforces.com/blog/entry/143822 2 3 Thank you all for participating! 👊👊👊 4 5 [2121A - Letter Home](/contest/2121/problem/A "Codeforces Round 1032 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 ios_base::sync_with_stdio(0); 20 cin.tie(0); 21 cout.tie(0); 22 int t; 23 cin >> t; 24 while (t--) { 25 int n, s; 26 cin >> n >> s; 27 vector<int> x(n); 28 for (int i = 0; i < n; i++) cin >> x[i]; 29 int ans = min(abs(s - x[0]), abs(s - x.back())) + x.back() - x[0]; 30 cout << ans << '\n'; 31 } 32 return 0; 33 } 34 ``` 35 36 [2121B - Above the Clouds](/contest/2121/problem/B "Codeforces Round 1032 (Div. 3)") 37 38 **Tutorial** 39 40 Tutorial is loading... 41 42 **Code** 43 44 ``` 45 #include<bits/stdc++.h> 46 47 using namespace std; 48 49 int main() { 50 ios_base::sync_with_stdio(0); 51 cin.tie(0); 52 cout.tie(0); 53 int t; 54 cin >> t; 55 while (t--) { 56 int n; 57 cin >> n; 58 string s; 59 cin >> s; 60 vector<int> cnt(26, 0); 61 for (auto c : s) cnt[c - 'a']++; 62 int flag = 0; 63 for (int i = 0; i < 26; i++) { 64 if (cnt[i] >= 3) flag = 1; 65 else if (cnt[i] == 2 && (s[0] - 'a' != i || s.back() - 'a' != i)) flag = 1; 66 } 67 if (flag) cout << "Yes" << '\n'; 68 else cout << "No" << '\n'; 69 } 70 return 0; 71 } 72 ``` 73 74 [2121C - Those Who Are With Us](/contest/2121/problem/C "Codeforces Round 1032 (Div. 3)") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Code** 81 82 ``` 83 #include<bits/stdc++.h> 84 85 using namespace std; 86 87 main() { 88 ios_base::sync_with_stdio(0); 89 cin.tie(0); 90 cout.tie(0); 91 int t; 92 cin >> t; 93 while (t--) { 94 int n, m; 95 cin >> n >> m; 96 vector<vector<int>> a(n, vector<int> (m)); 97 int mx = 0, cnt_mx = 0; 98 for (int i = 0; i < n; i++) { 99 for (int j = 0; j < m; j++) { 100 cin >> a[i][j]; 101 if (a[i][j] > mx) { 102 mx = a[i][j], cnt_mx = 1; 103 } else if (a[i][j] == mx) { 104 cnt_mx++; 105 } 106 } 107 } 108 vector<int> r(n), c(m); 109 for (int i = 0; i < n; i++) { 110 for (int j = 0; j < m; j++) { 111 if (a[i][j] == mx) { 112 r[i]++; 113 c[j]++; 114 } 115 } 116 } 117 int flag = 0; 118 for (int i = 0; i < n; i++) { 119 for (int j = 0; j < m; j++) { 120 if (r[i] + c[j] - (a[i][j] == mx) == cnt_mx) { 121 flag = 1; 122 } 123 } 124 } 125 cout << mx - flag << '\n'; 126 } 127 return 0; 128 } 129 ``` 130 131 [2121D - 1709](/contest/2121/problem/D "Codeforces Round 1032 (Div. 3)") 132 133 **Tutorial** 134 135 Tutorial is loading... 136 137 **Code** 138 139 ``` 140 #include<bits/stdc++.h> 141 142 using namespace std; 143 144 main() { 145 ios_base::sync_with_stdio(0); 146 cin.tie(0); 147 cout.tie(0); 148 int t; 149 cin >> t; 150 while (t--) { 151 int n; 152 cin >> n; 153 vector<int> a(n), b(n); 154 for (int i = 0; i < n; i++) cin >> a[i]; 155 for (int i = 0; i < n; i++) cin >> b[i]; 156 vector<pair<int, int>> ans; 157 for (int i = 0; i < n; i++) { 158 for (int j = 1; j < n; j++) { 159 if (a[j - 1] > a[j]) { 160 swap(a[j - 1], a[j]); 161 ans.push_back({1, j}); 162 } 163 } 164 } 165 for (int i = 0; i < n; i++) { 166 for (int j = 1; j < n; j++) { 167 if (b[j - 1] > b[j]) { 168 swap(b[j - 1], b[j]); 169 ans.push_back({2, j}); 170 } 171 } 172 } 173 for (int i = 0; i < n; i++) { 174 if (a[i] > b[i]) { 175 ans.push_back({3, i + 1}); 176 } 177 } 178 cout << ans.size() << '\n'; 179 for (auto [x, y] : ans) cout << x << " " << y << '\n'; 180 } 181 return 0; 182 } 183 ``` 184 185 [2121E - Sponsor of Your Problems](/contest/2121/problem/E "Codeforces Round 1032 (Div. 3)") 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Code** 192 193 ``` 194 #include<bits/stdc++.h> 195 196 using namespace std; 197 198 int main() { 199 ios_base::sync_with_stdio(0); 200 cin.tie(0); 201 cout.tie(0); 202 int t; 203 cin >> t; 204 while (t--) { 205 string l, r; 206 cin >> l >> r; 207 if (l == r) { 208 cout << 2 * l.size() << '\n'; 209 continue; 210 } 211 int ptr = 0; 212 while (ptr < l.size() && l[ptr] == r[ptr]) ptr++; 213 if (l[ptr] + 1 < r[ptr]) { 214 cout << 2 * ptr << '\n'; 215 } else { 216 int res = 2 * ptr + 1; 217 for (int i = ptr + 1; i < l.size(); i++) { 218 if (l[i] == '9' && r[i] == '0') res++; 219 else break; 220 } 221 cout << res << '\n'; 222 } 223 } 224 return 0; 225 } 226 ``` 227 228 [2121F - Yamakasi](/contest/2121/problem/F "Codeforces Round 1032 (Div. 3)") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Code** 235 236 ``` 237 #include<bits/stdc++.h> 238 239 using namespace std; 240 241 typedef long long ll; 242 int const maxn = 2e5 + 5; 243 int a[maxn]; 244 ll pref[maxn], s; 245 246 main() { 247 ios_base::sync_with_stdio(0); 248 cin.tie(0); 249 cout.tie(0); 250 int t; 251 cin >> t; 252 while (t--) { 253 int n, x; 254 cin >> n >> s >> x; 255 for (int i = 1; i <= n; i++) { 256 cin >> a[i]; 257 pref[i] = pref[i - 1] + a[i]; 258 } 259 ll ans = 0; 260 map<ll, int> cnt; 261 int lef = 1; 262 for (int r = 1; r <= n; r++) { 263 if (a[r] > x) cnt.clear(), lef = r + 1; 264 else if (a[r] == x) { 265 while (lef <= r) { 266 cnt[pref[lef - 1]]++; 267 lef++; 268 } 269 } 270 ans += cnt[pref[r] - s]; 271 } 272 cout << ans << '\n'; 273 } 274 return 0; 275 } 276 ``` 277 278 [2121G - Gangsta](/contest/2121/problem/G "Codeforces Round 1032 (Div. 3)") 279 280 **Tutorial** 281 282 Tutorial is loading... 283 284 **Code** 285 286 ``` 287 #include<bits/stdc++.h> 288 289 using namespace std; 290 291 typedef long long ll; 292 int const maxn = 2e5 + 5; 293 int pref[maxn]; 294 295 main() { 296 ios_base::sync_with_stdio(0); 297 cin.tie(0); 298 cout.tie(0); 299 int t; 300 cin >> t; 301 while (t--) { 302 int n; 303 cin >> n; 304 string s; 305 cin >> s; 306 ll ans = 0; 307 for (int i = 0; i < n; i++) { 308 pref[i + 1] = pref[i]; 309 if (s[i] == '0') pref[i + 1]--; 310 else pref[i + 1]++; 311 } 312 for (int i = 1; i <= n; i++) { 313 ans += (ll)i * (n - i + 1); 314 } 315 sort(pref, pref + n + 1); 316 for (int i = 0; i <= n; i++) { 317 ans += (ll)pref[i] * (i - (n - i)); 318 } 319 cout << ans / 2 << '\n'; 320 } 321 return 0; 322 } 323 ``` 324 325 [2121H - Ice Baby](/contest/2121/problem/H "Codeforces Round 1032 (Div. 3)") 326 327 **Tutorial** 328 329 Tutorial is loading... 330 331 **Code** 332 333 ``` 334 #include<bits/stdc++.h> 335 336 using namespace std; 337 338 main() { 339 ios_base::sync_with_stdio(0); 340 cin.tie(0); 341 cout.tie(0); 342 int t; 343 cin >> t; 344 while (t--) { 345 int n; 346 cin >> n; 347 multiset<int> dp; 348 for (int i = 1; i <= n; i++) { 349 int l, r; 350 cin >> l >> r; 351 auto it = dp.upper_bound(r); 352 if (it != dp.end()) { 353 dp.erase(it); 354 } 355 dp.insert(l); 356 cout << dp.size() << " "; 357 } 358 cout << '\n'; 359 } 360 return 0; 361 } 362 ```