codeforces-scrape

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

1716.md (5817B)


      1 Source: https://codeforces.com/blog/entry/105653
      2 
      3 [1716A - 2-3 Moves](/contest/1716/problem/A "Educational Codeforces Round 133 (Rated for Div. 2)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     n = int(input())
     16     print(1 + (n == 1) if n <= 3 else (n + 2) // 3)
     17 ```
     18 
     19 [1716B - Permutation Chain](/contest/1716/problem/B "Educational Codeforces Round 133 (Rated for Div. 2)")
     20 
     21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (awoo)**
     28 
     29 ```
     30 for _ in range(int(input())):
     31 	n = int(input())
     32 	p = [i + 1 for i in range(n)]
     33 	print(n)
     34 	for i in range(n):
     35 		print(*p)
     36 		if i < n - 1:
     37 			p[i], p[i + 1] = p[i + 1], p[i]
     38 ```
     39 
     40 [1716C - Robot in a Hallway](/contest/1716/problem/C "Educational Codeforces Round 133 (Rated for Div. 2)")
     41 
     42 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution (awoo)**
     49 
     50 ```
     51 INF = 2 * 10**9
     52 
     53 for _ in range(int(input())):
     54 	m = int(input())
     55 	a = [[int(x) for x in input().split()] for i in range(2)]
     56 	su = [[-INF for j in range(m + 1)] for i in range(2)]
     57 	for i in range(2):
     58 		for j in range(m - 1, -1, -1):
     59 			su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
     60 	pr = a[0][0] - 1
     61 	ans = INF
     62 	for j in range(m):
     63 		jj = j & 1
     64 		ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
     65 		pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
     66 		ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
     67 		if j < m - 1:
     68 			pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
     69 	print(ans + 2 * m)
     70 ```
     71 
     72 [1716D - Chip Move](/contest/1716/problem/D "Educational Codeforces Round 133 (Rated for Div. 2)")
     73 
     74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution (Neon)**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 
     85 using namespace std;
     86 
     87 const int MOD = 998244353;
     88 
     89 int main() {
     90   int n, k;
     91   cin >> n >> k;
     92   vector<int> dp(n + 1), ans(n + 1);
     93   dp[0] = 1;
     94   for (int mn = 0; mn + k <= n; mn += k++) {
     95     vector<int> sum(k);
     96     for (int i = mn; i <= n; ++i) {
     97       int cur = dp[i];
     98       dp[i] = sum[i % k];
     99       (sum[i % k] += cur) %= MOD;
    100       (ans[i] += dp[i]) %= MOD;
    101     }
    102   }
    103   for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    104 }
    105 ```
    106 
    107 [1716E - Swap and Maximum Block](/contest/1716/problem/E "Educational Codeforces Round 133 (Rated for Div. 2)")
    108 
    109 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution (BledDest)**
    116 
    117 ```
    118 #include<bits/stdc++.h>
    119 
    120 using namespace std;     
    121 const int K = 18;
    122 
    123 struct node
    124 {
    125     long long sum, pref, suff, ans;
    126     
    127     node(const node& l, const node& r)
    128     {                                                                                          
    129         sum = l.sum + r.sum;
    130         pref = max(l.pref, l.sum + r.pref);
    131         suff = max(r.suff, r.sum + l.suff);
    132         ans = max(max(l.ans, r.ans), l.suff + r.pref);
    133     }
    134 
    135     node(int x)
    136     {
    137         sum = x;
    138         pref = suff = ans = max(x, 0);
    139     }
    140 
    141     node() {};
    142 };
    143 
    144 int a[1 << K];
    145 vector<node> tree[2 << K];  
    146 
    147 void build(int v, int l, int r)
    148 {
    149     tree[v].resize(r - l);
    150     if(l == r - 1)
    151     {
    152         tree[v][0] = node(a[l]);  
    153     }
    154     else
    155     {
    156         int m = (l + r) / 2;
    157         build(v * 2 + 1, l, m);
    158         build(v * 2 + 2, m, r);
    159         for(int i = 0; i < m - l; i++)
    160         {
    161             tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
    162             tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);    
    163         }
    164     }
    165 }
    166 
    167 int main()
    168 {            
    169     int n;
    170     scanf("%d", &n);
    171     int m = (1 << n);
    172     for(int i = 0; i < m; i++)
    173     {
    174         scanf("%d", &a[i]);
    175     }
    176     build(0, 0, m);
    177     int q;
    178     scanf("%d", &q);
    179     int cur = 0;
    180     for(int i = 0; i < q; i++)
    181     {
    182         int x;
    183         scanf("%d", &x);
    184         cur ^= (1 << x);
    185         printf("%lld\n", tree[0][cur].ans);
    186     }
    187 }
    188 ```
    189 
    190 [1716F - Bags with Balls](/contest/1716/problem/F "Educational Codeforces Round 133 (Rated for Div. 2)")
    191 
    192 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution (BledDest)**
    199 
    200 ```
    201 #include<bits/stdc++.h>
    202 
    203 using namespace std;
    204 
    205 const int MOD = 998244353;   
    206 const int N = 2043;
    207 
    208 int dp[N][N];
    209 
    210 int add(int x, int y)
    211 {
    212     x += y;
    213     while(x >= MOD) x -= MOD;
    214     while(x < 0) x += MOD;
    215     return x;
    216 }   
    217 
    218 int sub(int x, int y)
    219 {
    220     return add(x, -y);
    221 }
    222 
    223 int mul(int x, int y)
    224 {
    225     return (x * 1ll * y) % MOD;
    226 }
    227 
    228 int binpow(int x, int y)
    229 {
    230     int z = 1;
    231     while(y > 0)
    232     {
    233         if(y % 2 == 1) z = mul(z, x);
    234         x = mul(x, x);
    235         y /= 2;
    236     }
    237     return z;
    238 }
    239 
    240 int inv(int x)
    241 {
    242     return binpow(x, MOD - 2);
    243 }
    244 
    245 int divide(int x, int y)
    246 {
    247     return mul(x, inv(y));
    248 }
    249 
    250 void precalc()
    251 {
    252     dp[1][1] = 1;
    253     for(int i = 1; i < N - 1; i++)
    254         for(int j = 1; j <= i; j++)
    255         {
    256             dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
    257             dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
    258         }
    259 }
    260 
    261 int solve(int n, int m, int k)
    262 {
    263     int way1 = (m / 2) + (m % 2);
    264     int curA = n;
    265     int ans = 0;
    266     int ways_chosen = way1;
    267     int ways_other = binpow(m, n - 1);
    268     int invm = inv(m);
    269     for(int i = 1; i <= k; i++)
    270     {
    271         ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other)));
    272         curA = mul(curA, sub(n, i));
    273         ways_chosen = mul(way1, ways_chosen);
    274         ways_other = mul(ways_other, invm);
    275     }  
    276     return ans;
    277 }   
    278 
    279 int main()
    280 {
    281     int t;
    282     cin >> t;
    283     precalc();
    284     for(int i = 0; i < t; i++)
    285     {
    286         int n, m, k;
    287         cin >> n >> m >> k;
    288         cout << solve(n, m, k) << endl;
    289     }
    290 }
    291 ```