codeforces-scrape

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

1065.md (9805B)


      1 Source: https://codeforces.com/blog/entry/62411
      2 
      3 [1065A - Vasya and Chocolate](/contest/1065/problem/A "Educational Codeforces Round 52 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Ajosteen)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17     int s, a, b, c;
     18     int t;
     19     cin >> t;
     20     for(int i = 0; i < t; ++i){
     21         cin >> s >> a >> b >> c;
     22         
     23         s /= c;
     24         int x = s / a;
     25         s %= a;
     26         long long res = x * 1LL * (a + b);
     27         res += s;
     28         
     29         cout << res << endl;
     30     }
     31     return 0;
     32 }
     33 ```
     34 
     35 [1065B - Vasya and Isolated Vertices](/contest/1065/problem/B "Educational Codeforces Round 52 (Rated for Div. 2)")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution (Ajosteen)**
     42 
     43 ```
     44 #include <bits/stdc++.h>
     45 
     46 using namespace std;
     47 
     48 int main() {
     49     int n;
     50     long long m;
     51     cin >> n >> m;
     52     long long cur = 1;
     53     long long rem = m;
     54     while(rem > 0){
     55         long long d = min(cur, rem);
     56         rem -= d;
     57         ++cur;
     58     }
     59     assert(rem == 0);
     60     
     61     long long res = n;
     62     if(cur > 1) res = n - cur;
     63     
     64     cout << max(0ll, n - m * 2) << ' ' << res << endl;
     65     return 0;
     66 }
     67 ```
     68 
     69 [1065C - Make It Equal](/contest/1065/problem/C "Educational Codeforces Round 52 (Rated for Div. 2)")
     70 
     71 **Tutorial**
     72 
     73 Tutorial is loading...
     74 
     75 **Solution (Ajosteen)**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 using namespace std;
     81 
     82 const int N = int(2e5) + 9;
     83 
     84 int n, k, h;
     85 int need = int(1e9);
     86 int cnt[N];
     87 
     88 int main() {
     89     scanf("%d %d", &n, &k);
     90     for(int i = 0; i < n; ++i){
     91         int x;
     92         scanf("%d", &x);
     93         h = max(h, x);
     94         need = min(need, x);
     95         ++cnt[x];
     96     }
     97     
     98     int pos = N - 1;
     99     int res = 0;
    100     long long sum = 0;
    101     int c = 0;
    102     while(true){
    103         long long x = sum - c * 1LL * (pos - 1);
    104         if(x > k){
    105             ++res;
    106             h = pos;
    107             sum = pos * 1LL * c;
    108         }   
    109     
    110         --pos;
    111         if(pos == need) break;
    112         c += cnt[pos];
    113         sum += cnt[pos] * 1LL * pos;
    114     }
    115     
    116     if(h != need) ++res;
    117     
    118     cout << res << endl;
    119 }
    120 ```
    121 
    122 [1065D - Three Pieces](/contest/1065/problem/D "Educational Codeforces Round 52 (Rated for Div. 2)")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Solution (PikMike)**
    129 
    130 ```
    131 #include <bits/stdc++.h>
    132 
    133 #define forn(i, n) for (int i = 0; i < int(n); i++)
    134 #define mp make_pair
    135 #define x first
    136 #define y second
    137 
    138 using namespace std;
    139 
    140 typedef pair<int, int> pt;
    141 
    142 const int N = 12;
    143 const int M = 305;
    144 const int INF = 1e9;
    145 
    146 int n;
    147 int a[N][N];
    148 pt pos[N * N];
    149 pt dist[M][M];
    150 
    151 pt operator +(const pt &a, const pt &b){
    152     return mp(a.x + b.x, a.y + b.y);
    153 }
    154 
    155 int dx[] = {-2, -1, 1, 2,  2,  1, -1, -2};
    156 int dy[] = { 1,  2, 2, 1, -1, -2, -2, -1};
    157 
    158 bool in(int x, int y){
    159     return (0 <= x && x < n && 0 <= y && y < n);
    160 }
    161 
    162 int get(int x, int y, int p){
    163     return x * n * 3 + y * 3 + p;
    164 }
    165 
    166 pt dp[N * N][3];
    167 
    168 int main() {
    169     scanf("%d", &n);
    170     forn(i, n) forn(j, n){
    171         scanf("%d", &a[i][j]);
    172         --a[i][j];
    173         pos[a[i][j]] = mp(i, j);
    174     }
    175     
    176     forn(i, M) forn(j, M) dist[i][j] = mp(INF, INF);
    177     forn(i, M) dist[i][i] = mp(0, 0);
    178     
    179     forn(x, n) forn(y, n){
    180         forn(i, 8){
    181             int nx = x + dx[i];
    182             int ny = y + dy[i];
    183             if (in(nx, ny))
    184                 dist[get(x, y, 0)][get(nx, ny, 0)] = mp(1, 0);
    185         }
    186         
    187         for (int i = -n + 1; i <= n - 1; ++i){
    188             int nx = x + i;
    189             int ny = y + i;
    190             if (in(nx, ny))
    191                 dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
    192             ny = y - i;
    193             if (in(nx, ny))
    194                 dist[get(x, y, 1)][get(nx, ny, 1)] = mp(1, 0);
    195         }
    196         
    197         forn(i, n){
    198             int nx = x;
    199             int ny = i;
    200             dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
    201             nx = i;
    202             ny = y;
    203             dist[get(x, y, 2)][get(nx, ny, 2)] = mp(1, 0);
    204         }
    205         
    206         forn(i, 3) forn(j, 3){
    207             if (i != j){
    208                 dist[get(x, y, i)][get(x, y, j)] = mp(1, 1);
    209             }
    210         }
    211     }
    212     
    213     forn(k, M) forn(i, M) forn(j, M)
    214         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    215     
    216     forn(i, N * N) forn(j, 3) dp[i][j] = mp(INF, INF);
    217     dp[0][0] = dp[0][1] = dp[0][2] = mp(0, 0);
    218     forn(i, n * n - 1) forn(j, 3) forn(k, 3)
    219         dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + dist[get(pos[i].x, pos[i].y, j)][get(pos[i + 1].x, pos[i + 1].y, k)]);
    220     
    221     pt ans = mp(INF, INF);
    222     ans = min(ans, dp[n * n - 1][0]);
    223     ans = min(ans, dp[n * n - 1][1]);
    224     ans = min(ans, dp[n * n - 1][2]);
    225     
    226     printf("%d %d\n", ans.x, ans.y);
    227     return 0;
    228 }
    229 ```
    230 
    231 [1065E - Side Transmutations](/contest/1065/problem/E "Educational Codeforces Round 52 (Rated for Div. 2)")
    232 
    233 **Tutorial**
    234 
    235 Tutorial is loading...
    236 
    237 **Solution (PikMike)**
    238 
    239 ```
    240 #include <bits/stdc++.h>
    241 
    242 #define forn(i, n) for (int i = 0; i < int(n); i++)
    243 
    244 using namespace std;
    245 
    246 const int N = 200 * 1000 + 13;
    247 const int MOD = 998244353;
    248 
    249 int n, m, A;
    250 int b[N];
    251 
    252 int add(int a, int b){
    253     a += b;
    254     if (a >= MOD)
    255         a -= MOD;
    256     return a;
    257 }
    258 
    259 int mul(int a, int b){
    260     return (a * 1ll * b) % MOD;
    261 }
    262 
    263 int binpow(int a, int b){
    264     int res = 1;
    265     while (b){
    266         if (b & 1)
    267             res = mul(res, a);
    268         a = mul(a, a);
    269         b >>= 1;
    270     }
    271     return res;
    272 }
    273 
    274 int cnt(int x){
    275     int base = binpow(A, x);
    276     return mul(add(mul(base, base), base), (MOD + 1) / 2);
    277 }
    278 
    279 int main() {
    280     scanf("%d%d%d", &n, &m, &A);
    281     forn(i, m)
    282         scanf("%d", &b[i]);
    283     
    284     int ans = binpow(A, n - b[m - 1] * 2);
    285     ans = mul(ans, cnt(b[0]));
    286     forn(i, m - 1)
    287         ans = mul(ans, cnt(b[i + 1] - b[i]));
    288     
    289     printf("%d\n", ans);
    290     return 0;
    291 }
    292 ```
    293 
    294 [1065F - Up and Down the Tree](/contest/1065/problem/F "Educational Codeforces Round 52 (Rated for Div. 2)")
    295 
    296 **Tutorial**
    297 
    298 Tutorial is loading...
    299 
    300 **Solution (adedalic)**
    301 
    302 ```
    303 #include<bits/stdc++.h>
    304 
    305 using namespace std;
    306 
    307 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    308 #define sz(a) int((a).size())
    309 
    310 #define x first
    311 #define y second
    312 
    313 typedef long long li;
    314 typedef pair<int, int> pt;
    315 
    316 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    317     return out << "(" << p.x << ", " << p.y << ")";
    318 }
    319 
    320 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    321     out << "[";
    322     fore(i, 0, v.size()) {
    323         if(i) out << ", ";
    324         out << v[i];
    325     }
    326     return out << "]";
    327 }
    328 
    329 const int INF = int(1e9);
    330 const li INF64 = li(1e18);
    331 
    332 const int N = 1000 * 1000 + 555;
    333 
    334 int n, k;
    335 vector<int> g[N];
    336 
    337 inline bool read() {
    338     if(!(cin >> n >> k))
    339         return false;
    340     fore(i, 1, n) {
    341         int p; assert(scanf("%d", &p) == 1);
    342         p--;
    343         
    344         g[p].push_back(i);
    345         g[i].push_back(p);
    346     }
    347     return true;
    348 }
    349 
    350 int h[N];
    351 pt drev[N];
    352 
    353 void calcRev(int v, int p) {
    354     drev[v] = pt(INF, 0);
    355     for(int to : g[v]) {
    356         if(to == p) continue;
    357         
    358         h[to] = h[v] + 1;
    359         calcRev(to, v);
    360         
    361         if(drev[to].x <= h[v]) {
    362             drev[v].x = min(drev[v].x, drev[to].x);
    363             drev[v].y += drev[to].y;
    364         }
    365     }
    366     
    367     if(p >= 0 && g[v].size() == 1)
    368         drev[v] = pt(h[v] - k, 1);
    369 }
    370 
    371 int d[N];
    372 
    373 void calcAns(int v, int p) {
    374     d[v] = (p >= 0 && g[v].size() == 1);
    375     for(int to : g[v]) {
    376         if(to == p) continue;
    377         calcAns(to, v);
    378         
    379         int tmp = drev[v].y;
    380         if(drev[to].x <= h[v])
    381             tmp -= drev[to].y;
    382         
    383         d[v] = max(d[v], tmp + d[to]);
    384     }
    385 }
    386 
    387 inline void solve() {
    388     h[0] = 0;
    389     calcRev(0, -1);
    390     calcAns(0, -1);
    391     cout << d[0] << endl;
    392 }
    393 
    394 int main() {
    395 #ifdef _DEBUG
    396     freopen("input.txt", "r", stdin);
    397     int tt = clock();
    398 #endif
    399     cout << fixed << setprecision(15);
    400     
    401     if(read()) {
    402         solve();
    403         
    404 #ifdef _DEBUG
    405         cerr << "TIME = " << clock() - tt << endl;
    406         tt = clock();
    407 #endif
    408     }
    409     return 0;
    410 }
    411 ```
    412 
    413 [1065G - Fibonacci Suffix](/contest/1065/problem/G "Educational Codeforces Round 52 (Rated for Div. 2)")
    414 
    415 **Tutorial**
    416 
    417 Tutorial is loading...
    418 
    419 **Solution (BledDest)**
    420 
    421 ```
    422 #include <bits/stdc++.h>
    423 
    424 using namespace std;
    425 
    426 typedef long long li;
    427 
    428 const li INF64 = li(1e18);
    429 
    430 li add(li x, li y)
    431 {
    432     return min(x + y, INF64);
    433 }
    434 
    435 const int N = 243;
    436 
    437 int A1[N][2];
    438 li A2[N][N];
    439 int A3[N][N];
    440 int n, m;
    441 li k;
    442 int z;
    443 int p[N];
    444 
    445 void build(const string& s)
    446 {
    447     z = (int)(s.size());
    448     p[0] = 0;
    449     for(int i = 1; i < z; i++)
    450     {
    451         int j = p[i - 1];
    452         while(j > 0 && s[j] != s[i])
    453             j = p[j - 1];
    454         if(s[j] == s[i])
    455             j++;
    456         p[i] = j;
    457     }
    458     for(int i = 0; i <= z; i++)
    459         for(int j = 0; j < 2; j++)
    460         {
    461             if(i < z && s[i] == char('0' + j))
    462                 A1[i][j] = i + 1;
    463             else if(i == 0)
    464                 A1[i][j] = 0;
    465             else
    466                 A1[i][j] = A1[p[i - 1]][j];
    467         }
    468     for(int i = 0; i <= z; i++)
    469         for(int j = 0; j < 2; j++)
    470         {
    471             A3[i][j] = A1[i][j];
    472             A2[i][j] = (A3[i][j] == z ? 1 : 0);
    473         }
    474     for(int i = 2; i <= n; i++)
    475         for(int j = 0; j <= z; j++)
    476         {
    477             A3[j][i] = A3[A3[j][i - 2]][i - 1];
    478             A2[j][i] = add(A2[j][i - 2], A2[A3[j][i - 2]][i - 1]);
    479         }
    480 }
    481 
    482 int main()
    483 {
    484     cin >> n >> k >> m;
    485     string cur = "";
    486     for(int i = 0; i < m; i++)
    487     {
    488         if(cur != "") build(cur);
    489         li x = 0;
    490         if(cur != "" && A3[0][n] == i)
    491             x = 1;
    492         if(k == 1 && x == 1)
    493             break;
    494         k -= x;
    495         build(cur + '0');
    496         li x1 = A2[0][n];
    497         if(k > x1)
    498         {
    499             cur += '1';
    500             k -= x1;
    501         }
    502         else
    503             cur += '0';
    504     }
    505     cout << cur << endl;
    506     return 0;
    507 }
    508 ```