codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```