2050.md (6629B)
1 Source: https://codeforces.com/blog/entry/137018 2 3 [2050A - Line Breaks](/contest/2050/problem/A "Codeforces Round 991 (Div. 3)") 4 5 Идея: [kbats183](/profile/kbats183 "Specialist kbats183") 6 7 **Решение** 8 9 Tutorial is loading... 10 11 **Код** 12 13 ``` 14 def solve(): 15 n, m = [int(i) for i in input().split()] 16 17 ans = 0 18 for i in range(n): 19 l = input() 20 if len(l) <= m: 21 m -= len(l) 22 ans += 1 23 else: 24 for i in range(i + 1, n): 25 input() 26 break 27 28 print(ans) 29 30 t = int(input()) 31 for i in range(t): 32 solve() 33 ``` 34 35 [2050B - Transfusion](/contest/2050/problem/B "Codeforces Round 991 (Div. 3)") 36 37 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin") 38 39 **Решение** 40 41 Tutorial is loading... 42 43 **Код** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 void solve() { 51 int n; cin >> n; 52 vector<int> a(n); 53 for (int &x : a) cin >> x; 54 55 long long ods = 0, evs = 0; 56 for (int i = 0; i < n; i++) { 57 if (i & 1) ods += a[i]; 58 else evs += a[i]; 59 } 60 int odc = n / 2, evc = n / 2; 61 if (n & 1) evc++; 62 63 if (ods % odc != 0 || evs % evc != 0 || ods / odc != evs / evc) { 64 cout << "NO"; 65 return; 66 } 67 cout << "YES"; 68 } 69 70 int main() { 71 int TESTS; cin >> TESTS; 72 while (TESTS --> 0) { 73 solve(); 74 cout << '\n'; 75 } 76 return 0; 77 } 78 ``` 79 80 [2050C - Uninteresting Number](/contest/2050/problem/C "Codeforces Round 991 (Div. 3)") 81 82 Идея: [DanGolov](/profile/DanGolov "Expert DanGolov") 83 84 **Решение** 85 86 Tutorial is loading... 87 88 **Код** 89 90 ``` 91 def solve(): 92 s = [int(x) for x in list(input())] 93 94 sm = sum(s) 95 twos = s.count(2) 96 threes = s.count(3) 97 98 for i in range(min(10, twos + 1)): 99 for j in range(min(10, threes + 1)): 100 if (sm + i * 2 + j * 6) % 9 == 0: 101 print('YES') 102 return 103 print('NO') 104 105 t = int(input()) 106 for _ in range(t): 107 solve() 108 ``` 109 110 [2050D - Digital string maximization](/contest/2050/problem/D "Codeforces Round 991 (Div. 3)") 111 112 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin") 113 114 **Решение** 115 116 Tutorial is loading... 117 118 **Код** 119 120 ``` 121 #include <bits/stdc++.h> 122 123 using namespace std; 124 125 void solve() { 126 string s; cin >> s; 127 for (int i = 0; i < s.size(); i++) { 128 int best = s[i] - '0', pos = i; 129 for (int j = i; j < min(i + 10, (int) s.size()); j++) { 130 if (s[j] - '0' - (j - i) > best) { 131 best = s[j] - '0' - (j - i); 132 pos = j; 133 } 134 } 135 while (pos > i) { 136 swap(s[pos], s[pos - 1]); 137 pos--; 138 } 139 s[i] = char(best + '0'); 140 } 141 cout << s; 142 } 143 144 int main() { 145 int TESTS = 1; cin >> TESTS; 146 while (TESTS --> 0) { 147 solve(); 148 cout << '\n'; 149 } 150 return 0; 151 } 152 ``` 153 154 [2050E - Three Strings](/contest/2050/problem/E "Codeforces Round 991 (Div. 3)") 155 156 Идея: [pskobx](/profile/pskobx "Candidate Master pskobx"), [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 157 158 **Решение** 159 160 Tutorial is loading... 161 162 **Код** 163 164 ``` 165 #include <iostream> 166 #include <algorithm> 167 168 static const int inf = 1e9; 169 170 void solve() { 171 std::string a, b, res; 172 std::cin >> a >> b >> res; 173 int n = (int) a.size(), m = (int) b.size(); 174 int dp[n + 1][m + 1]; 175 std::fill(&dp[0][0], &dp[0][0] + (n + 1) * (m + 1), inf); 176 dp[0][0] = 0; 177 for (int i = 0; i < n; i++) { 178 dp[i + 1][0] = dp[i][0] + (a[i] != res[i]); 179 } 180 for (int j = 0; j < m; j++) { 181 dp[0][j + 1] = dp[0][j] + (b[j] != res[j]); 182 } 183 for (int i = 1; i <= n; i++) { 184 for (int j = 1; j <= m; j++) { 185 dp[i][j] = std::min(dp[i - 1][j] + (a[i - 1] != res[i + j - 1]), 186 dp[i][j - 1] + (b[j - 1] != res[i + j - 1])); 187 } 188 } 189 std::cout << dp[n][m] << std::endl; 190 } 191 192 int main() { 193 int tests; 194 std::cin >> tests; 195 while (tests--) { 196 solve(); 197 } 198 } 199 ``` 200 201 [2050F - Maximum modulo equality](/contest/2050/problem/F "Codeforces Round 991 (Div. 3)") 202 203 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin") 204 205 **Решение** 206 207 Tutorial is loading... 208 209 **Код** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 using namespace std; 215 216 const int LOGN = 20; 217 218 vector<vector<int>> stGCD; 219 220 int get_gcd(int l, int r) { 221 int k = __lg(r - l + 1); 222 return __gcd(stGCD[k][l], stGCD[k][r - (1 << k) + 1]); 223 } 224 225 void solve() { 226 stGCD.clear(); 227 int n, q; cin >> n >> q; 228 vector<int> a(n); 229 for (int &x : a) cin >> x; 230 231 vector<int> b; 232 for (int i = 1; i < n; i++) 233 b.push_back(abs(a[i - 1] - a[i])); 234 235 stGCD.resize(LOGN, vector<int>(b.size(), 1)); 236 for (int i = 0; i < b.size(); i++) 237 stGCD[0][i] = b[i]; 238 for (int i = 1; i < LOGN; i++) 239 for (int j = 0; j + (1 << (i - 1)) < b.size(); j++) 240 stGCD[i][j] = __gcd(stGCD[i - 1][j], stGCD[i - 1][j + (1 << (i - 1))]); 241 242 while (q--) { 243 int l, r; cin >> l >> r; 244 if (l == r) { 245 cout << 0 << " "; 246 continue; 247 } 248 l--; r -= 2; 249 int gcd = get_gcd(l, r); 250 cout << gcd << " "; 251 } 252 } 253 254 int main() { 255 int TESTS = 1; cin >> TESTS; 256 while (TESTS --> 0) { 257 solve(); 258 cout << "\n"; 259 } 260 return 0; 261 } 262 ``` 263 264 [2050G - Tree Destruction](/contest/2050/problem/G "Codeforces Round 991 (Div. 3)") 265 266 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin") 267 268 **Решение** 269 270 Tutorial is loading... 271 272 **Код** 273 274 ``` 275 #include <bits/stdc++.h> 276 277 #define int long long 278 #define x first 279 #define y second 280 281 using namespace std; 282 283 void dfs(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &dp){ 284 dp[v].x = sl[v].size(); 285 int m1 = -1, m2 = -1; 286 for(int u: sl[v]){ 287 if(u == p){ 288 continue; 289 } 290 dfs(u, v, sl, dp); 291 dp[v].x = max(dp[v].x, dp[u].x + (int)sl[v].size() - 2); 292 m2 = max(m2, dp[u].x); 293 if(m1 < m2) swap(m1, m2); 294 } 295 dp[v].y = dp[v].x; 296 if(m2 != -1){ 297 dp[v].y = m1 + m2 + sl[v].size() - 4; 298 } 299 } 300 301 void solve(int tc){ 302 int n; 303 cin >> n; 304 vector<vector<int>> sl(n); 305 for(int i = 1; i < n; ++i){ 306 int u, v; 307 cin >> u >> v; 308 sl[--u].emplace_back(--v); 309 sl[v].emplace_back(u); 310 } 311 vector<pair<int, int>> dp(n); 312 dfs(0, 0, sl, dp); 313 int ans = 0; 314 for(int i = 0; i < n; ++i){ 315 ans = max(ans, max(dp[i].x, dp[i].y)); 316 } 317 cout << ans; 318 } 319 320 bool multi = true; 321 322 signed main() { 323 int t = 1; 324 if (multi)cin >> t; 325 for (int i = 1; i <= t; ++i) { 326 solve(i); 327 cout << "\n"; 328 } 329 return 0; 330 } 331 ```