codeforces-scrape

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

1207.md (9591B)


      1 Source: https://codeforces.com/blog/entry/69314
      2 
      3 [1207A - There Are Two Types Of Burgers](/contest/1207/problem/A "Educational Codeforces Round 71 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int t;
     19 int b, p, f;
     20 int h, c;
     21 
     22 int main() {
     23     cin >> t;
     24     for(int tc = 0; tc < t; ++tc){
     25         cin >> b >> p >> f;
     26         cin >> h >> c;
     27 
     28         b /= 2;
     29         if(h < c){
     30             swap(h, c);
     31             swap(p, f);
     32         }
     33 
     34         int res = 0;
     35 
     36         int cnt = min(b, p);
     37         b -= cnt, p -= cnt;
     38         res += h * cnt; 
     39         
     40         cnt = min(b, f);
     41         b -= cnt, f -= cnt;
     42         res += c * cnt; 
     43             
     44         cout << res << endl;
     45     }
     46     return 0;
     47 }
     48 ```
     49 
     50 [1207B - Square Filling](/contest/1207/problem/B "Educational Codeforces Round 71 (Rated for Div. 2)")
     51 
     52 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution (BledDest)**
     59 
     60 ```
     61 n, m = map(int, input().split())
     62 a = [[] for i in range(n)]
     63 for i in range(n):
     64     a[i] = list(map(int, input().split()))
     65 
     66 ans = []
     67 for i in range(n - 1):
     68     for j in range(m - 1):
     69         if(a[i][j] * a[i][j + 1] * a[i + 1][j] * a[i + 1][j + 1] > 0):
     70             a[i][j] = 2
     71             a[i + 1][j] = 2
     72             a[i][j + 1] = 2
     73             a[i + 1][j + 1] = 2
     74             ans.append([i, j])
     75 
     76 cnt1 = 0
     77 for i in range(n):
     78     for j in range(m):
     79         if(a[i][j] == 1):
     80             cnt1 += 1
     81 
     82 if(cnt1 != 0):
     83     print(-1)
     84 else:
     85     print(len(ans))
     86     for x in ans:
     87         print(x[0] + 1, x[1] + 1)
     88 ```
     89 
     90 [1207C - Gas Pipeline](/contest/1207/problem/C "Educational Codeforces Round 71 (Rated for Div. 2)")
     91 
     92 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution (adedalic)**
     99 
    100 ```
    101 const val INF64 = 1e18.toLong()
    102 
    103 fun main(args: Array<String>) {
    104     val tc = readLine()!!.toInt()
    105     for (t in 1..tc) {
    106         val (n, a, b) = readLine()!!.split(' ').map { it.toInt() }
    107         val s = readLine()!!
    108 
    109         val d = Array(n + 1) { arrayOf(INF64, INF64) }
    110         d[0][0] = b.toLong()
    111 
    112         for (pos in 0 until n) {
    113             if (s[pos] == '0') {
    114                 d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][0] + a + b)
    115                 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][0] + 2 * (a + b))
    116 
    117                 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
    118                 d[pos + 1][0] = minOf(d[pos + 1][0], d[pos][1] + 2 * a + b)
    119             } else {
    120                 d[pos + 1][1] = minOf(d[pos + 1][1], d[pos][1] + a + 2 * b)
    121             }
    122         }
    123         println(d[n][0])
    124     }
    125 }
    126 ```
    127 
    128 [1207D - Number Of Permutations](/contest/1207/problem/D "Educational Codeforces Round 71 (Rated for Div. 2)")
    129 
    130 Idea: [Roms](/profile/Roms "Master Roms")
    131 
    132 **Tutorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Solution (Roms)**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 
    141 using namespace std;
    142 
    143 const int N = int(3e5) + 99;
    144 const int MOD = 998244353;
    145 
    146 int mul(int a, int b){
    147     return (a * 1LL * b) % MOD;
    148 }
    149 
    150 int sum(int a, int b){
    151     return (a + b) % MOD;
    152 }
    153 
    154 int n;
    155 pair<int, int> a[N];
    156 int f[N];
    157 
    158 int main() {
    159     scanf("%d", &n);
    160     for(int i = 0; i < n; ++i)
    161         scanf("%d%d", &a[i].first, &a[i].second);
    162 
    163     f[0] = 1;
    164     for(int i = 1; i < N; ++i)
    165         f[i] = mul(i, f[i - 1]);
    166 
    167     int res = f[n];
    168     for(int c = 0; c < 2; ++c){
    169         int d = 1;
    170         sort(a, a + n);
    171         int l = 0;
    172         while(l < n){
    173             int r = l + 1;
    174             while(r < n && a[l].first == a[r].first) ++r;
    175             d = mul(d, f[r - l]);
    176             l = r;
    177         }
    178         res = sum(res, MOD - d);
    179         for(int i = 0; i < n; ++i) 
    180             swap(a[i].first, a[i].second);
    181     }       
    182 
    183     sort(a, a + n);
    184     int l = 0;
    185     int d = 1;
    186     while(l < n){
    187         int r = l + 1;
    188         while(r < n && a[l].first == a[r].first) ++r;
    189         map<int, int> m;
    190         for(int i = l; i < r; ++i) ++m[a[i].second];
    191         for(auto p : m) d = mul(d, f[p.second]);
    192         l = r;
    193     }
    194     for(int i = 1; i < n; ++i) 
    195         if(a[i - 1].second > a[i].second) d = 0;
    196 
    197     res = sum(res, d);
    198     printf("%d\n", res);
    199     return 0;
    200 }
    201 ```
    202 
    203 [1207E - XOR Guessing](/contest/1207/problem/E "Educational Codeforces Round 71 (Rated for Div. 2)")
    204 
    205 Idea: [adedalic](/profile/adedalic "International Master adedalic"), [Neon](/profile/Neon "Candidate Master Neon"), [BledDest](/profile/BledDest "Grandmaster BledDest")
    206 
    207 **Tutorial**
    208 
    209 Tutorial is loading...
    210 
    211 **Solution (BledDest)**
    212 
    213 ```
    214 #include<bits/stdc++.h>
    215 
    216 using namespace std;
    217 
    218 int main()
    219 {
    220     cout << "?";
    221     for(int i = 1; i <= 100; i++)
    222         cout << " " << i;
    223     cout << endl;
    224     cout.flush();
    225     int res1;
    226     cin >> res1;
    227     cout << "?";
    228     for(int i = 1; i <= 100; i++)
    229         cout << " " << (i << 7);
    230     cout << endl;
    231     cout.flush();
    232     int res2;
    233     cin >> res2;
    234     int x = 0;
    235     x |= (res1 & (((1 << 7) - 1) << 7));
    236     x |= (res2 & ((1 << 7) - 1));
    237     cout << "! " << x << endl;
    238     cout.flush();
    239     return 0;
    240 }
    241 ```
    242 
    243 [1207F - Remainder Problem](/contest/1207/problem/F "Educational Codeforces Round 71 (Rated for Div. 2)")
    244 
    245 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest")
    246 
    247 **Tutorial**
    248 
    249 Tutorial is loading...
    250 
    251 **Solution (BledDest)**
    252 
    253 ```
    254 #include <bits/stdc++.h>
    255 
    256 using namespace std;
    257 
    258 const int N = 500043;
    259 const int K = 750;
    260 
    261 int a[N];
    262 int sum[K][K];
    263 
    264 int main()
    265 {
    266     int q;
    267     scanf("%d", &q);
    268     for(int i = 0; i < q; i++)
    269     {
    270         int t, x, y;
    271         scanf("%d %d %d", &t, &x, &y);
    272         if(t == 1)
    273         {
    274             a[x] += y;
    275             for(int i = 1; i < K; i++)
    276                 sum[i][x % i] += y;
    277         }
    278         else
    279         {
    280             if(x >= K)
    281             {
    282                 int ans = 0;
    283                 for(int i = y; i <= 500000; i += x)
    284                     ans += a[i];
    285                 printf("%d\n", ans);
    286             }
    287             else
    288                 printf("%d\n", sum[x][y]);
    289         }
    290     }
    291     return 0;
    292 }
    293 ```
    294 
    295 [1207G - Indie Album](/contest/1207/problem/G "Educational Codeforces Round 71 (Rated for Div. 2)")
    296 
    297 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    298 
    299 **Tutorial**
    300 
    301 Tutorial is loading...
    302 
    303 **Solution (PikMike)**
    304 
    305 ```
    306 #include <bits/stdc++.h>
    307 
    308 #define forn(i, n) for (int i = 0; i < int(n); i++)
    309 
    310 using namespace std;
    311 
    312 const int AL = 26;
    313 const int N = 400 * 1000 + 13;
    314 
    315 struct node{
    316     int nxt[AL];
    317     node(){
    318         memset(nxt, -1, sizeof(nxt));
    319     }
    320     int& operator [](int x){
    321         return nxt[x];
    322     }
    323 };
    324 
    325 struct node_at{
    326     int nxt[AL];
    327     int p;
    328     char pch;
    329     int link;
    330     int go[AL];
    331     node_at(){
    332         memset(nxt, -1, sizeof(nxt));
    333         memset(go, -1, sizeof(go));
    334         link = p = -1;
    335     }
    336     int& operator [](int x){
    337         return nxt[x];
    338     }
    339 };
    340 
    341 int cntnm;
    342 node trienm[N];
    343 
    344 int cntqr;
    345 node_at trieqr[N];
    346 
    347 int add_string(string s){
    348     int v = 0;
    349     for (auto it : s){
    350         int c = it - 'a';
    351         if (trieqr[v][c] == -1){
    352             trieqr[cntqr] = node_at();
    353             trieqr[cntqr].p = v;
    354             trieqr[cntqr].pch = c;
    355             trieqr[v][c] = cntqr;
    356             ++cntqr;
    357         }
    358         v = trieqr[v][c];
    359     }
    360     return v;
    361 }
    362 
    363 int go(int v, int c);
    364  
    365 int get_link(int v){
    366     if (trieqr[v].link == -1){
    367         if (v == 0 || trieqr[v].p == 0)
    368             trieqr[v].link = 0;
    369         else
    370             trieqr[v].link = go(get_link(trieqr[v].p), trieqr[v].pch);
    371     }
    372     return trieqr[v].link;
    373 }
    374  
    375 int go(int v, int c) {
    376     if (trieqr[v].go[c] == -1){
    377         if (trieqr[v][c] != -1)
    378             trieqr[v].go[c] = trieqr[v][c];
    379         else
    380             trieqr[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
    381     }
    382     return trieqr[v].go[c];
    383 }
    384 
    385 int add_letter(int v, int c){
    386     if (trienm[v][c] == -1){
    387         trienm[cntnm] = node();
    388         trienm[v][c] = cntnm;
    389         ++cntnm;
    390     }
    391     return trienm[v][c];
    392 }
    393 
    394 vector<int> g[N];
    395 int tin[N], tout[N], T;
    396 
    397 void dfs_init(int v){
    398     tin[v] = T++;
    399     for (auto u : g[v])
    400         dfs_init(u);
    401     tout[v] = T;
    402 }
    403 
    404 int f[N];
    405 
    406 void upd(int v, int val){
    407     for (int i = tin[v]; i < N; i |= i + 1)
    408         f[i] += val;
    409 }
    410 
    411 int get(int x){
    412     int sum = 0;
    413     for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    414         sum += f[i];
    415     return sum;
    416 }
    417 
    418 int sum(int v){
    419     return get(tout[v] - 1) - get(tin[v] - 1);
    420 }
    421 
    422 int n, m;
    423 int nm[N], qr[N];
    424 vector<int> nms[N];
    425 vector<int> reqs[N];
    426 int ans[N];
    427 
    428 void dfs(int v, int cur){
    429     upd(cur, 1);
    430     for (auto it : nms[v])
    431         for (auto q : reqs[it])
    432             ans[q] = sum(qr[q]);
    433     forn(i, AL) if (trienm[v][i] != -1)
    434         dfs(trienm[v][i], go(cur, i));
    435     upd(cur, -1);
    436 }
    437 
    438 int main(){
    439     cntqr = 0;
    440     trieqr[cntqr++] = node_at();
    441     
    442     cntnm = 0;
    443     trienm[cntnm++] = node();
    444     
    445     char buf[N];
    446     scanf("%d", &n);
    447     forn(i, n){
    448         int t;
    449         scanf("%d", &t);
    450         if (t == 1){
    451             scanf("%s", buf);
    452             nm[i] = add_letter(0, buf[0] - 'a');
    453         }
    454         else{
    455             int j;
    456             scanf("%d%s", &j, buf);
    457             --j;
    458             nm[i] = add_letter(nm[j], buf[0] - 'a');
    459         }
    460         nms[nm[i]].push_back(i);
    461     }
    462     
    463     scanf("%d", &m);
    464     forn(i, m){
    465         int j;
    466         scanf("%d%s", &j, buf);
    467         --j;
    468         reqs[j].push_back(i);
    469         qr[i] = add_string(buf);
    470     }
    471     
    472     for (int v = 1; v < cntqr; ++v)
    473         g[get_link(v)].push_back(v);
    474     
    475     T = 0;
    476     dfs_init(0);
    477     dfs(0, 0);
    478     
    479     forn(i, m)
    480         printf("%d\n", ans[i]);
    481 }
    482 ```