1036.md (9249B)
1 Source: https://codeforces.com/blog/entry/61727 2 3 [1036A - Function Height](/contest/1036/problem/A "Educational Codeforces Round 50 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 n, k = map(int, input().split()) 13 print((k + n - 1) // n) 14 ``` 15 16 [1036B - Diagonal Walking v.2](/contest/1036/problem/B "Educational Codeforces Round 50 (Rated for Div. 2)") 17 18 **Tutorial** 19 20 Tutorial is loading... 21 22 **Solution (Vovuh)** 23 24 ``` 25 q = int(input()) 26 27 for i in range(q): 28 n, m, k = map(int, input().split()) 29 if (n < m): n, m = m, n 30 if (n % 2 != m % 2): 31 k -= 1 32 n -= 1 33 elif (n % 2 != k % 2): 34 k -= 2 35 n -= 1 36 m -= 1 37 print(-1 if k < n else k) 38 ``` 39 40 [1036C - Classy Numbers](/contest/1036/problem/C "Educational Codeforces Round 50 (Rated for Div. 2)") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution with combinatorics (PikMike)** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 #define forn(i, n) for (int i = 0; i < int(n); i++) 52 53 using namespace std; 54 55 long long C[20][20]; 56 long long pw[4]; 57 58 long long cnk(int n, int k){ 59 if (k < 0 || k > n) return 0; 60 return C[n][k]; 61 } 62 63 long long get(int n, int lft){ 64 long long tot = 0; 65 forn(i, lft + 1) 66 tot += cnk(n, i) * pw[i]; 67 return tot; 68 } 69 70 long long calc(long long x){ 71 string s = to_string(x); 72 73 long long res = 0; 74 int cur = 3; 75 int n = s.size(); 76 77 forn(i, n){ 78 if (s[i] == '0') continue; 79 res += get(n - i - 1, cur); 80 --cur; 81 if (cur == -1) break; 82 res += get(n - i - 1, cur) * (s[i] - '1'); 83 } 84 85 return res; 86 } 87 88 int main() { 89 forn(i, 20){ 90 C[i][0] = C[i][i] = 1; 91 for (int j = 1; j < i; ++j) 92 C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; 93 } 94 pw[0] = 1, pw[1] = 9, pw[2] = 81, pw[3] = 729; 95 int T; 96 scanf("%d", &T); 97 forn(i, T){ 98 long long L, R; 99 scanf("%lld%lld", &L, &R); 100 printf("%lld\n", calc(R + 1) - calc(L)); 101 } 102 return 0; 103 } 104 ``` 105 106 **Solution with precalc (PikMike)** 107 108 ``` 109 #include <bits/stdc++.h> 110 111 #define forn(i, n) for (int i = 0; i < int(n); i++) 112 113 using namespace std; 114 115 vector<long long> res; 116 117 void brute(int pos, int cnt, long long cur){ 118 if (pos == 18){ 119 res.push_back(cur); 120 return; 121 } 122 123 brute(pos + 1, cnt, cur * 10); 124 125 if (cnt < 3) 126 for (int i = 1; i <= 9; ++i) 127 brute(pos + 1, cnt + 1, cur * 10 + i); 128 } 129 130 int main() { 131 brute(0, 0, 0); 132 res.push_back(1000000000000000000); 133 134 int T; 135 scanf("%d", &T); 136 forn(i, T){ 137 long long L, R; 138 scanf("%lld%lld", &L, &R); 139 printf("%d\n", int(upper_bound(res.begin(), res.end(), R) - lower_bound(res.begin(), res.end(), L))); 140 } 141 return 0; 142 } 143 ``` 144 145 [1036D - Vasya and Arrays](/contest/1036/problem/D "Educational Codeforces Round 50 (Rated for Div. 2)") 146 147 **Tutorial** 148 149 Tutorial is loading... 150 151 **Solution (Ajosteen)** 152 153 ``` 154 #include <bits/stdc++.h> 155 156 using namespace std; 157 158 const int N = 300 * 1000 + 9; 159 160 int n, m; 161 int a[N], b[N]; 162 163 int main() { 164 scanf("%d", &n); 165 for(int i = 0; i < n; ++i) scanf("%d", a + i); 166 scanf("%d", &m); 167 for(int i = 0; i < m; ++i) scanf("%d", b + i); 168 169 long long sum = 0; 170 for(int i = 0; i < n; ++i) sum += a[i]; 171 for(int i = 0; i < m; ++i) sum -= b[i]; 172 if(sum != 0){ 173 puts("-1"); 174 return 0; 175 } 176 177 int posa = 0, posb = 0; 178 int res = 0; 179 while(posa < n){ 180 ++res; 181 long long suma = a[posa++], sumb = b[posb++]; 182 183 while(suma != sumb){ 184 if(suma < sumb) suma += a[posa++]; 185 else sumb += b[posb++]; 186 } 187 } 188 189 printf("%d\n", res); 190 return 0; 191 } 192 ``` 193 194 [1036E - Covered Points](/contest/1036/problem/E "Educational Codeforces Round 50 (Rated for Div. 2)") 195 196 **Tutorial** 197 198 Tutorial is loading... 199 200 **Solution (PikMike)** 201 202 ``` 203 #include <bits/stdc++.h> 204 205 #define forn(i, n) for (int i = 0; i < int(n); i++) 206 207 using namespace std; 208 209 const int N = 1000 + 7; 210 211 struct seg{ 212 int x1, y1, x2, y2; 213 seg(){}; 214 }; 215 216 struct line{ 217 long long A, B, C; 218 line(){}; 219 line(seg a){ 220 A = a.y1 - a.y2; 221 B = a.x2 - a.x1; 222 C = -A * a.x1 - B * a.y1; 223 }; 224 }; 225 226 int n; 227 seg a[N]; 228 229 int get(seg a){ 230 int dx = a.x1 - a.x2; 231 int dy = a.y1 - a.y2; 232 return __gcd(abs(dx), abs(dy)) + 1; 233 } 234 235 long long det(long long a, long long b, long long c, long long d){ 236 return a * d - b * c; 237 } 238 239 bool in(int x, int l, int r){ 240 if (l > r) swap(l, r); 241 return (l <= x && x <= r); 242 } 243 244 bool inter(seg a, seg b, int& x, int& y){ 245 line l1(a), l2(b); 246 long long dx = det(l1.C, l1.B, l2.C, l2.B); 247 long long dy = det(l1.A, l1.C, l2.A, l2.C); 248 long long d = det(l1.A, l1.B, l2.A, l2.B); 249 if (d == 0) 250 return false; 251 if (dx % d != 0 || dy % d != 0) 252 return false; 253 x = -dx / d; 254 y = -dy / d; 255 if (!in(x, a.x1, a.x2) || !in(y, a.y1, a.y2)) 256 return false; 257 if (!in(x, b.x1, b.x2) || !in(y, b.y1, b.y2)) 258 return false; 259 return true; 260 } 261 262 int main() { 263 scanf("%d", &n); 264 forn(i, n) 265 scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2); 266 267 int ans = 0; 268 int x, y; 269 forn(i, n){ 270 ans += get(a[i]); 271 set<pair<int, int>> pts; 272 forn(j, i) 273 if (inter(a[i], a[j], x, y)) 274 pts.insert({x, y}); 275 ans -= pts.size(); 276 } 277 278 printf("%d\n", ans); 279 return 0; 280 } 281 ``` 282 283 [1036F - Relatively Prime Powers](/contest/1036/problem/F "Educational Codeforces Round 50 (Rated for Div. 2)") 284 285 **Tutorial** 286 287 Tutorial is loading... 288 289 **Solution (PikMike)** 290 291 ``` 292 #include <bits/stdc++.h> 293 294 #define forn(i, n) for (int i = 0; i < int(n); i++) 295 296 using namespace std; 297 298 const int K = 100; 299 const int N = 100 * 1000 + 13; 300 const long long INF64 = 3e18; 301 302 int mu[K]; 303 304 void precalc(){ 305 static bool prime[K]; 306 static int lst[K]; 307 308 memset(prime, false, sizeof(prime)); 309 forn(i, K) lst[i] = i; 310 311 for (int i = 2; i < K; ++i){ 312 if (lst[i] == i) mu[i] = 1; 313 for (int j = 2 * i; j < K; j += i){ 314 lst[j] = min(lst[j], lst[i]); 315 if (lst[j] == lst[i]) 316 mu[j] = 0; 317 else 318 mu[j] = -mu[i]; 319 } 320 } 321 } 322 323 int mx[K]; 324 325 long long binpow(long long a, int b){ 326 long long res = 1; 327 while (b){ 328 if (b & 1){ 329 if (res < INF64 / a) res *= a; 330 else return INF64; 331 } 332 if (b > 1){ 333 if (a < INF64 / a) a *= a; 334 else return INF64; 335 } 336 b >>= 1; 337 } 338 return res; 339 } 340 341 long long calc(long long n){ 342 int pw = 63 - __builtin_clzll(n); 343 for (int i = 3; i <= pw; ++i){ 344 if (mu[i] == 0) continue; 345 while (binpow(mx[i], i) > n) 346 --mx[i]; 347 } 348 349 long long res = n - 1; 350 for (int i = 2; i <= pw; ++i) 351 res -= mu[i] * (mx[i] - 1); 352 353 return res; 354 } 355 356 int get_sqrt(long long n){ 357 int l = 1, r = 1000000000; 358 while (l < r - 1){ 359 int m = (l + r) / 2; 360 if (m * 1ll * m <= n) 361 l = m; 362 else 363 r = m; 364 } 365 return (r * 1ll * r <= n ? r : l); 366 } 367 368 long long ans[N]; 369 370 int main() { 371 precalc(); 372 int T; 373 scanf("%d", &T); 374 vector<pair<long long, int>> q; 375 376 forn(i, T){ 377 long long n; 378 scanf("%lld", &n); 379 q.push_back({n, i}); 380 } 381 382 sort(q.begin(), q.end(), greater<pair<long long, int>>()); 383 mx[3] = 1000000; 384 mx[4] = 31622; 385 mx[5] = 3981; 386 for (int i = 6; i < K; ++i) 387 mx[i] = 1000; 388 389 forn(z, T){ 390 long long n = q[z].first; 391 mx[2] = get_sqrt(n); 392 ans[q[z].second] = calc(n); 393 } 394 395 forn(i, T) 396 printf("%lld\n", ans[i]); 397 return 0; 398 } 399 ``` 400 401 [1036G - Sources and Sinks](/contest/1036/problem/G "Educational Codeforces Round 50 (Rated for Div. 2)") 402 403 **Tutorial** 404 405 Tutorial is loading... 406 407 **Solution (BledDest)** 408 409 ``` 410 #include <bits/stdc++.h> 411 412 using namespace std; 413 414 const int N = 1000043; 415 416 vector<int> g[N]; 417 vector<int> gt[N]; 418 vector<int> src; 419 vector<int> snk; 420 int reach[20]; 421 int used[N]; 422 423 void dfs(int x) 424 { 425 if(used[x]) return; 426 used[x] = 1; 427 for(auto y : g[x]) dfs(y); 428 } 429 430 int main() 431 { 432 int n, m; 433 scanf("%d %d", &n, &m); 434 for(int i = 0; i < m; i++) 435 { 436 int x, y; 437 scanf("%d %d", &x, &y); 438 --x; 439 --y; 440 g[x].push_back(y); 441 gt[y].push_back(x); 442 } 443 for(int i = 0; i < n; i++) 444 { 445 if(g[i].empty()) 446 snk.push_back(i); 447 if(gt[i].empty()) 448 src.push_back(i); 449 } 450 int cnt = src.size(); 451 for(int i = 0; i < cnt; i++) 452 { 453 memset(used, 0, sizeof used); 454 dfs(src[i]); 455 for(int j = 0; j < cnt; j++) 456 if(used[snk[j]]) 457 reach[i] ^= (1 << j); 458 } 459 bool ok = true; 460 for(int mask = 0; mask < (1 << cnt); mask++) 461 { 462 int res = 0; 463 for(int j = 0; j < cnt; j++) 464 if(mask & (1 << j)) 465 res |= reach[j]; 466 int cnt1 = __builtin_popcount(mask); 467 int cnt2 = __builtin_popcount(res); 468 if(cnt2 < cnt1 || (cnt2 == cnt1 && cnt1 != 0 && cnt1 != cnt)) 469 ok = false; 470 } 471 if(!ok) 472 puts("NO"); 473 else 474 puts("YES"); 475 } 476 ```