1809.md (8223B)
1 Source: https://codeforces.com/blog/entry/114300 2 3 [1809A - Garland](/contest/1809/problem/A "Educational Codeforces Round 145 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 ios::sync_with_stdio(false); cin.tie(0); 20 int tc; 21 cin >> tc; 22 while (tc--) { 23 string s; 24 cin >> s; 25 vector<int> cnt(10); 26 for (auto c : s) ++cnt[c - '0']; 27 int mx = *max_element(cnt.begin(), cnt.end()); 28 if (mx == 4) cout << -1; 29 else if (mx == 3) cout << 6; 30 else cout << 4; 31 cout << '\n'; 32 } 33 } 34 ``` 35 36 [1809B - Points on Plane](/contest/1809/problem/B "Educational Codeforces Round 145 (Rated for Div. 2)") 37 38 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution 1 (adedalic)** 45 46 ``` 47 fun main() { 48 repeat(readln().toInt()) { 49 val n = readln().toLong() 50 var l = (-1).toLong() 51 var r = 1e9.toLong() 52 while (r - l > 1) { 53 val mid = (l + r) / 2 54 if (mid * mid >= n) 55 r = mid 56 else 57 l = mid 58 } 59 println(r - 1) 60 } 61 } 62 ``` 63 64 **Solution 2 (adedalic)** 65 66 ``` 67 import kotlin.math.sqrt 68 69 fun main() { 70 repeat(readln().toInt()) { 71 val n = readln().toLong() 72 var ans = sqrt(n.toDouble()).toLong() 73 while (ans * ans > n) 74 ans-- 75 while (ans * ans < n) 76 ans++ 77 println(ans - 1) 78 } 79 } 80 ``` 81 82 [1809C - Sum on Subarrays](/contest/1809/problem/C "Educational Codeforces Round 145 (Rated for Div. 2)") 83 84 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 85 86 **Tutorial** 87 88 Tutorial is loading... 89 90 **Solution (BledDest)** 91 92 ``` 93 def solve(n, k): 94 if n == 0: 95 return [] 96 if k < n: 97 a = [-1 for i in range(n)] 98 if k > 0: 99 a[k - 1] = 200 100 a[k] = -400 101 else: 102 a = solve(n - 1, k - n) 103 a.append(1000) 104 return a 105 106 t = int(input()) 107 for i in range(t): 108 n, k = map(int, input().split()) 109 b = solve(n, k) 110 print(*b) 111 ``` 112 113 [1809D - Binary String Sorting](/contest/1809/problem/D "Educational Codeforces Round 145 (Rated for Div. 2)") 114 115 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 116 117 **Tutorial** 118 119 Tutorial is loading... 120 121 **Solution (Neon)** 122 123 ``` 124 #include <bits/stdc++.h> 125 126 using namespace std; 127 128 const long long pw10 = 1e12; 129 130 int main() { 131 ios::sync_with_stdio(false); cin.tie(0); 132 int tc; 133 cin >> tc; 134 while (tc--) { 135 string s; 136 cin >> s; 137 int n = s.size(); 138 int cnt0 = 0, cnt1 = count(s.begin(), s.end(), '1'); 139 long long ans = 1e18; 140 if (n == 1) ans = 0; 141 for (int i = 0; i < n - 1; ++i) { 142 cnt0 += s[i] == '0'; 143 cnt1 -= s[i] == '1'; 144 int k = cnt0 + cnt1 + (s[i] == '1') + (s[i + 1] == '0'); 145 long long cur = (n - k) * (pw10 + 1); 146 if (s[i] > s[i + 1]) cur += pw10; 147 ans = min(ans, cur); 148 } 149 cout << ans << '\n'; 150 } 151 } 152 ``` 153 154 [1809E - Two Tanks](/contest/1809/problem/E "Educational Codeforces Round 145 (Rated for Div. 2)") 155 156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 157 158 **Tutorial** 159 160 Tutorial is loading... 161 162 **Solution (awoo)** 163 164 ``` 165 #include <bits/stdc++.h> 166 167 #define forn(i, n) for (int i = 0; i < int(n); i++) 168 169 using namespace std; 170 171 int main() { 172 int n, a, b; 173 scanf("%d%d%d", &n, &a, &b); 174 vector<int> v(n); 175 forn(i, n) scanf("%d", &v[i]); 176 vector<vector<int>> ans(a + 1, vector<int>(b + 1)); 177 forn(cd, a + b + 1){ 178 int l = max(0, cd - b), r = min(a, cd); 179 int sum = 0; 180 for (int x : v){ 181 sum += x; 182 l = max({l, sum, cd + sum - b}); 183 r = min({r, a + sum, sum + cd}); 184 } 185 if (l > r) l = r = max(0, cd - b); 186 int res = l; 187 for (int x : v){ 188 if (x > 0) 189 res -= min({res, x, b - (cd - res)}); 190 else 191 res += min({cd - res, -x, a - res}); 192 } 193 forn(c, cd + 1) if (c <= a && cd - c <= b){ 194 ans[c][cd - c] = (c < l ? res : (c > r ? res + r - l : res + c - l)); 195 } 196 } 197 forn(i, a + 1){ 198 forn(j, b + 1) 199 printf("%d ", ans[i][j]); 200 puts(""); 201 } 202 return 0; 203 } 204 ``` 205 206 [1809F - Traveling in Berland](/contest/1809/problem/F "Educational Codeforces Round 145 (Rated for Div. 2)") 207 208 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 209 210 **Tutorial (Neon)** 211 212 Tutorial is loading... 213 214 **Solution (awoo)** 215 216 ``` 217 #include<bits/stdc++.h> 218 219 using namespace std; 220 221 #define forn(i, n) for (int i = 0; i < int(n); ++i) 222 223 void solve(){ 224 int n, k; 225 scanf("%d%d", &n, &k); 226 vector<int> a(n); 227 forn(i, n) scanf("%d", &a[i]); 228 vector<int> b(n); 229 forn(i, n) scanf("%d", &b[i]); 230 231 vector<long long> pr(2 * n + 1); 232 forn(i, 2 * n) pr[i + 1] = pr[i] + a[i % n]; 233 234 vector<long long> dist(n); 235 vector<long long> cost(n); 236 int cnt = 0; 237 for (int i = 2 * n - 1; i >= 0; --i){ 238 if (i < n){ 239 if (b[i] == 2){ 240 dist[i] = 1; 241 cost[i] = a[i] * 2; 242 } 243 else if (cnt == 0){ 244 dist[i] = 1; 245 cost[i] = a[i]; 246 } 247 else{ 248 int j = lower_bound(pr.begin() + i, pr.begin() + i + cnt + 1, pr[i] + k) - pr.begin(); 249 assert(j > i); 250 dist[i] = j - i; 251 if (pr[j] - pr[i] <= k) 252 cost[i] = pr[j] - pr[i]; 253 else 254 cost[i] = 2 * (pr[j] - pr[i]) - k; 255 } 256 } 257 if (b[i % n] == 2) ++cnt; 258 else cnt = 0; 259 } 260 261 int pw = 0; 262 while ((1 << pw) <= n) ++pw; 263 264 vector<vector<long long>> distk(pw, dist); 265 vector<vector<long long>> costk(pw, cost); 266 for (int j = 1; j < pw; ++j) forn(i, n){ 267 distk[j][i] = distk[j - 1][i] + distk[j - 1][(i + distk[j - 1][i]) % n]; 268 costk[j][i] = costk[j - 1][i] + costk[j - 1][(i + distk[j - 1][i]) % n]; 269 } 270 271 forn(i, n){ 272 int pos = i; 273 long long tot = 0; 274 long long ans = 0; 275 for (int j = pw - 1; j >= 0; --j) if (tot + distk[j][pos] <= n){ 276 tot += distk[j][pos]; 277 ans += costk[j][pos]; 278 pos = (pos + distk[j][pos]) % n; 279 } 280 if (tot < n) ans += pr[i + n] - pr[i + tot]; 281 printf("%lld ", ans); 282 } 283 puts(""); 284 } 285 286 int main(){ 287 int tc; 288 scanf("%d", &tc); 289 while (tc--) solve(); 290 } 291 ``` 292 293 [1809G - Prediction](/contest/1809/problem/G "Educational Codeforces Round 145 (Rated for Div. 2)") 294 295 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 296 297 **Tutorial** 298 299 Tutorial is loading... 300 301 **Solution (BledDest)** 302 303 ``` 304 #include <bits/stdc++.h> 305 306 using namespace std; 307 308 const int MOD = 998244353; 309 310 int add(int x, int y) 311 { 312 return ((x + y) % MOD + MOD) % MOD; 313 } 314 315 int mul(int x, int y) 316 { 317 return x * 1ll * y % MOD; 318 } 319 320 int binpow(int x, int y) 321 { 322 int z = 1; 323 while(y) 324 { 325 if(y % 2 == 1) z = mul(z, x); 326 x = mul(x, x); 327 y /= 2; 328 } 329 return z; 330 } 331 332 int inv(int x) 333 { 334 return binpow(x, MOD - 2); 335 } 336 337 int divide(int x, int y) 338 { 339 return mul(x, inv(y)); 340 } 341 342 int main() 343 { 344 int n, k; 345 scanf("%d %d", &n, &k); 346 vector<int> a(n); 347 for(int i = 0; i < n; i++) 348 scanf("%d", &a[i]); 349 350 reverse(a.begin(), a.end()); 351 352 vector<int> fact(n + 1); 353 fact[0] = 1; 354 for(int i = 1; i <= n; i++) 355 fact[i] = mul(fact[i - 1], i); 356 357 // for each player, we find the first player which doesn't conflict with them 358 vector<int> first_no_conflict(n); 359 for(int i = 0; i < n; i++) 360 { 361 if(i) first_no_conflict[i] = first_no_conflict[i - 1]; 362 while(first_no_conflict[i] < n && a[first_no_conflict[i]] >= a[i] - k) 363 first_no_conflict[i]++; 364 } 365 366 vector<int> dp(n + 1); 367 if(a[0] - a[1] > k) dp[1] = 1; 368 for(int i = 1; i < n; i++) 369 { 370 // first choice: put a[i] on the first position 371 // then we put all which conflict with a[i] on any position other than 1 372 int no_of_conflicting = first_no_conflict[i] - i - 1; 373 // put all conflicting with a[i] on any position other than 1 374 // the first one chooses from i positions, the second - from i+1 positions, and so on 375 // so the number of ways is fact[i + no_of_conflicting - 1] / fact[i - 1] 376 dp[i + no_of_conflicting + 1] = add(dp[i + no_of_conflicting + 1], mul(dp[i], divide(fact[i + no_of_conflicting - 1], fact[i - 1]))); 377 378 // second choice: put a[i] on any other position 379 dp[i + 1] = add(dp[i + 1], mul(dp[i], i)); 380 } 381 382 printf("%d\n", dp[n]); 383 } 384 ```