1921.md (8465B)
1 Source: https://codeforces.com/blog/entry/124757 2 3 [1921A - Square](/contest/1921/problem/A "Codeforces Round 920 (Div. 3)") 4 5 Idea: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike"), prepared: [pashka](/profile/pashka "International Grandmaster pashka") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 t = int(input()) 15 for _ in range(t): 16 a = [[int(x) for x in input().split()] for i in range(4)] 17 x = [p[0] for p in a] 18 dx = max(x) - min(x) 19 print(dx * dx) 20 ``` 21 22 [1921B - Arranging Cats](/contest/1921/problem/B "Codeforces Round 920 (Div. 3)") 23 24 Idea: [pashka](/profile/pashka "International Grandmaster pashka"), prepared: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution** 31 32 ``` 33 t = int(input()) 34 35 for _ in range(t): 36 n = int(input()) 37 start = [int(x) for x in input()] 38 finish = [int(x) for x in input()] 39 pairs = list(zip(start, finish)) 40 add_amnt = sum(int(a < b) for a, b in pairs) 41 rmv_amnt = sum(int(a > b) for a, b in pairs) 42 print(max(add_amnt, rmv_amnt)) 43 ``` 44 45 [1921C - Sending Messages](/contest/1921/problem/C "Codeforces Round 920 (Div. 3)") 46 47 Idea: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step"), prepared: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution** 54 55 ``` 56 t = int(input()) 57 for _ in range(t): 58 n, f, a, b = map(int, input().split()) 59 m = [0] + [int(x) for x in input().split()] 60 for i in range(1, n + 1): 61 f -= min(a * (m[i] - m[i - 1]), b) 62 print('YES' if f > 0 else 'NO') 63 ``` 64 65 [1921D - Very Different Array](/contest/1921/problem/D "Codeforces Round 920 (Div. 3)") 66 67 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [pashka](/profile/pashka "International Grandmaster pashka") 68 69 **Tutorial** 70 71 Tutorial is loading... 72 73 **Solution** 74 75 ``` 76 #include <bits/stdc++.h> 77 using namespace std; 78 79 struct test { 80 void solve() { 81 int n, m; 82 cin >> n >> m; 83 vector<int> a(n); 84 for (int i = 0; i < n; i++) cin >> a[i]; 85 vector<int> b(m); 86 for (int i = 0; i < m; i++) cin >> b[i]; 87 sort(a.begin(), a.end()); 88 sort(b.rbegin(), b.rend()); 89 vector<int> c(n); 90 long long s = 0; 91 for (int i = 0; i < n; i++) { 92 c[i] = b[m — n + i]; 93 s += abs(c[i] — a[i]); 94 } 95 long long res = 0; 96 for (int k = 0; k <= n; k++) { 97 res = max(res, s); 98 if (k < n) { 99 s -= abs(c[k] — a[k]); 100 c[k] = b[k]; 101 s += abs(c[k] — a[k]); 102 } 103 } 104 cout << res << "\n"; 105 } 106 }; 107 108 int main() { 109 ios::sync_with_stdio(false); 110 int n; 111 cin >> n; 112 for (int i = 0; i < n; i++) { 113 test().solve(); 114 } 115 return 0; 116 } 117 ``` 118 119 [1921E - Eat the Chip](/contest/1921/problem/E "Codeforces Round 920 (Div. 3)") 120 121 Idea: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp"), prepared: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp") 122 123 **Tutorial** 124 125 Tutorial is loading... 126 127 **Solution** 128 129 ``` 130 def solve(): 131 h, w, xA, yA, xB, yB = map(int, input().split()) 132 133 if (xA - xB) % 2 == 0: 134 winner = "Bob" 135 if xA >= xB: 136 win = False 137 elif yA == yB: 138 win = True 139 else: 140 if yA < yB: 141 n_turns = yB - 1 142 else: 143 n_turns = w - yB 144 win = xB - 2 * n_turns >= xA 145 146 else: 147 winner = "Alice" 148 149 xA += 1 150 yA += 0 if yB - yA == 0 else 1 if yB - yA > 0 else -1 151 152 if xA > xB: 153 win = False 154 elif yA == yB: 155 win = True 156 else: 157 if yA < yB: 158 n_turns = w - yA 159 else: 160 n_turns = yA - 1 161 win = xB - 2 * n_turns >= xA 162 163 print(winner if win else "Draw") 164 165 t = int(input()) 166 167 for _ in range(t): 168 solve() 169 ``` 170 171 [1921F - Sum of Progression](/contest/1921/problem/F "Codeforces Round 920 (Div. 3)") 172 173 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239") 174 175 **Tutorial** 176 177 Tutorial is loading... 178 179 **Solution** 180 181 ``` 182 #include <bits/stdc++.h> 183 184 using namespace std; 185 186 long long precalc[322][200322]; 187 long long precalci[322][200322]; 188 189 void solve() { 190 int n, q; 191 cin >> n >> q; 192 vector<long long> a(n); 193 int pivot = 1; 194 while (pivot * pivot < n) { 195 pivot++; 196 } 197 for (int i = 0; i < n; i++) { 198 cin >> a[i]; 199 } 200 for (int i = 0; i < pivot; i++) { 201 for (int j = 0; j <= i; j++) { 202 precalc[i][j] = 0LL; 203 precalci[i][j] = 0LL; 204 } 205 for (int j = 0; j < n; j++) { 206 precalci[i][j + i + 1] = precalci[i][j] + a[j] * (j / (i + 1) + 1); 207 precalc[i][j + i + 1] = precalc[i][j] + a[j]; 208 } 209 } 210 while (q--) { 211 int s, d; 212 long long k; 213 long long ans = 0; 214 cin >> s >> d >> k; 215 s--; 216 if (d > pivot) { 217 for (int i = s; i <= s + (k - 1) * d; i += d) { 218 ans += a[i] * ((i - s) / d + 1); 219 } 220 cout << ans << " "; 221 continue; 222 } 223 long long last = s + d * k - d; 224 int first = s; 225 cout << precalci[d - 1][last + d] - precalci[d - 1][first] - 226 (precalc[d - 1][last + d] - precalc[d - 1][first]) * (first / d) << ' '; 227 } 228 } 229 230 int main() { 231 ios_base::sync_with_stdio(false); 232 cin.tie(nullptr); 233 cout.tie(nullptr); 234 int tests; 235 cin >> tests; 236 while (tests--) { 237 solve(); 238 if (tests) cout << "\n"; 239 } 240 return 0; 241 } 242 ``` 243 244 [1921G - Mischievous Shooter](/contest/1921/problem/G "Codeforces Round 920 (Div. 3)") 245 246 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike") 247 248 **Tutorial** 249 250 Tutorial is loading... 251 252 **Solution** 253 254 ``` 255 //ciao_chill 256 #include<bits/stdc++.h> 257 using namespace std; 258 #define int long long 259 260 int n, m, k; 261 vector<vector<int>> a; 262 263 bool prov(int i, int j) { 264 return 0 <= i && i < n && 0 <= j && j < m; 265 } 266 267 int ans() { 268 int cnt = 0; 269 int dp[n][m]; 270 int pref[n][m]; 271 int pref_up[n][m]; 272 for (int i = 0; i < n; i++) { 273 for (int j = 0; j < m; j++) { 274 pref_up[i][j] = a[i][j]; 275 if (prov(i - 1, j)) 276 pref_up[i][j] += pref_up[i - 1][j]; 277 } 278 } 279 280 for (int i = 0; i < n; i++) { 281 for (int j = m - 1; j >= 0; j--) { 282 pref[i][j] = a[i][j]; 283 if (prov(i - 1, j + 1)) 284 pref[i][j] += pref[i - 1][j + 1]; 285 } 286 } 287 288 for (int i = 0; i < n; i++) { 289 for (int j = 0; j < m; j++) { 290 dp[i][j] = pref_up[i][j]; 291 if (prov(i - k, j)) 292 dp[i][j] -= pref_up[i - k][j]; 293 if (prov(i, j - 1)) 294 dp[i][j] += dp[i][j - 1]; 295 if (j < k) { 296 int i1 = j - k + i; 297 if (i1 >= 0) 298 dp[i][j] -= pref[i1][0]; 299 } 300 else 301 dp[i][j] -= pref[i][j - k]; 302 if (prov(i - k, j)) 303 dp[i][j] += pref[i - k][j]; 304 cnt = max(cnt, dp[i][j]); 305 } 306 } 307 308 return cnt; 309 } 310 311 void solve() { 312 cin >> n >> m >> k; 313 k++; 314 char c; 315 bool st[n][m]; 316 a.resize(n); 317 for (int i = 0; i < n; i++) { 318 a[i].resize(m); 319 } 320 for (int i = 0; i < n; i++) { 321 for (int j = 0; j < m; j++) 322 { 323 cin >> c; 324 st[i][j] = (c == '#'); 325 a[i][j] = st[i][j]; 326 } 327 } 328 329 int mx = ans(); 330 for (int i = 0; i < n; i++) { 331 for (int j = 0; j < m; j++) { 332 a[i][j] = st[n - i - 1][j]; 333 } 334 } 335 mx = max(mx, ans()); 336 for (int i = 0; i < n; i++) { 337 for (int j = 0; j < m; j++) { 338 a[i][j] = st[i][m - j - 1]; 339 } 340 } 341 mx = max(mx, ans()); 342 for (int i = 0; i < n; i++) { 343 for (int j = 0; j < m; j++) { 344 a[i][j] = st[n - i - 1][m - j - 1]; 345 } 346 } 347 mx = max(mx, ans()); 348 349 cout << mx << '\n'; 350 351 } 352 353 signed main() { 354 cin.tie(nullptr); 355 cout.tie(nullptr); 356 ios_base::sync_with_stdio(false); 357 358 int tt; 359 cin >> tt; 360 while (tt--) 361 solve(); 362 363 return 0; 364 } 365 ```