codeforces-scrape

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

2230.md (7898B)


      1 Source: https://codeforces.com/blog/entry/153834
      2 
      3 [2230A - Optimal Purchase](/contest/2230/problem/A "Educational Codeforces Round 190 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm"), preparation: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n, a, b = map(int, input().split())
     17     c = n // 3
     18     d = n % 3
     19     print(min((c + 1) * b, c * b + d * a, n * a))
     20 ```
     21 
     22 [2230B - Digit String](/contest/2230/problem/B "Educational Codeforces Round 190 (Rated for Div. 2)")
     23 
     24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (BledDest)**
     31 
     32 ```
     33 t = int(input())
     34 for i in range(t):
     35     s = input()
     36     pref2 = 0
     37     suf = 0
     38     for x in s:
     39         if x == '1' or x == '3':
     40             suf += 1
     41     ans = pref2 + suf
     42     for x in s:
     43         if x == '2':
     44             pref2 += 1
     45         if x == '1' or x == '3':
     46             suf -= 1
     47         ans = max(ans, pref2 + suf)
     48     print(len(s) - ans)
     49 ```
     50 
     51 [2230C - Arrange the Numbers in a Circle](/contest/2230/problem/C "Educational Codeforces Round 190 (Rated for Div. 2)")
     52 
     53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (BledDest)**
     60 
     61 ```
     62 t = int(input())
     63 for i in range(t):
     64     n = int(input())
     65     c = list(map(int, input().split()))
     66 
     67     s = sum(c)
     68     ones = 0
     69     slots = 0
     70     for x in c:
     71         if x == 1:
     72             ones += 1
     73         else:
     74             slots += x // 2 - 1
     75     if ones == n - 1:
     76         slots += 1
     77     wasted = max(0, ones - slots)
     78     if s - wasted < 3:
     79         print(0)
     80     else:
     81         print(s - wasted)
     82 ```
     83 
     84 [2230D - Good Schedule](/contest/2230/problem/D "Educational Codeforces Round 190 (Rated for Div. 2)")
     85 
     86 Idea: [Neon](/profile/Neon "Candidate Master Neon"), preparation: [Neon](/profile/Neon "Candidate Master Neon")
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution (Neon)**
     93 
     94 ```
     95 #include <bits/stdc++.h>
     96  
     97 using namespace std;
     98 
     99 int main() {
    100     ios::sync_with_stdio(false); cin.tie(0);
    101     int t;
    102     cin >> t;
    103     while (t--) {
    104         int n;
    105         cin >> n;
    106         vector<int> a(n), b(n);
    107         for (auto &x : a) cin >> x, --x;
    108         for (auto &x : b) cin >> x, --x;
    109         vector<int> pa(n + 1, n), pb(n + 1, n), dp(n + 1, n);
    110         long long ans = 0;
    111         for (int i = n - 1; i >= 0; --i) {
    112             pa[a[i]] = i;
    113             pb[b[i]] = i;
    114             if (a[i] == b[i]) {
    115                 int x = a[i] + 1;
    116                 if (pa[x] == pb[x]) {
    117                     dp[i] = dp[pa[x]];
    118                 } else {
    119                     dp[i] = min(pa[x], pb[x]);
    120                 }
    121             }
    122             if (pa[0] != pb[0]) {
    123                 ans += min(pa[0], pb[0]) - i;
    124             } else {
    125                 ans += dp[pa[0]] - i;
    126             }
    127         }
    128         cout << ans << '\n';
    129     }
    130 }
    131 ```
    132 
    133 [2230E - Minimum Influence](/contest/2230/problem/E "Educational Codeforces Round 190 (Rated for Div. 2)")
    134 
    135 Idea: [adedalic](/profile/adedalic "International Master adedalic"), preparation: [adedalic](/profile/adedalic "International Master adedalic")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution (adedalic)**
    142 
    143 ```
    144 import bisect
    145 import sys
    146 input = sys.stdin.readline
    147 
    148 INF = int(1e9) + 7
    149 A = int(1e6) + 3
    150 
    151 n = int(input())
    152 a = [list(map(int, input().split())) for i in range(2)]
    153 
    154 minVal = [[INF] * A for i in range(2)]
    155 pMin = [[INF] * A for i in range(2)]
    156 sMin = [[INF] * A for i in range(2)]
    157 for k in range(2):
    158     for i in range(n):
    159         minVal[k][a[k][i]] = min(minVal[k][a[k][i]], a[k ^ 1][i])
    160 
    161     for v in range(A - 1):
    162         pMin[k][v + 1] = min(pMin[k][v], minVal[k][v])
    163     
    164     for v in range(A - 2, -1, -1):
    165         sMin[k][v] = min(sMin[k][v + 1], minVal[k][v])
    166 
    167 mid = 0
    168 for i in range(n):
    169     if a[0][mid] + a[1][mid] > a[0][i] + a[1][i]:
    170         mid = i
    171 
    172 m = int(input())
    173 t = [list(map(int, input().split())) for i in range(3)]
    174 
    175 def I(val, l, r):
    176     if val < l:
    177         return 0
    178     return min(val, r)
    179 
    180 ans = []
    181 for id in range(m):
    182     cur = I(a[0][mid], t[0][id], t[0][id] + t[2][id]) + I(a[1][mid], t[1][id], t[1][id] + t[2][id])
    183     for k in range(2):
    184         pos_l = t[k][id]
    185         pos_r = min(A - 1, t[k][id] + t[2][id])
    186         
    187         if pMin[k][pos_l] < INF:
    188             cur = min(cur, I(pMin[k][pos_l], t[k ^ 1][id], t[k ^ 1][id] + t[2][id]))
    189         if sMin[k][pos_r] < INF:
    190             cur = min(cur, pos_r + I(sMin[k][pos_r], t[k ^ 1][id], t[k ^ 1][id] + t[2][id]))
    191     ans.append(cur)
    192 
    193 print("\n".join(map(str, ans)))
    194 ```
    195 
    196 [2230F - Game on Growing Tree](/contest/2230/problem/F "Educational Codeforces Round 190 (Rated for Div. 2)")
    197 
    198 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    199 
    200 **Tutorial**
    201 
    202 Tutorial is loading...
    203 
    204 **Solution (BledDest)**
    205 
    206 ```
    207 #include<bits/stdc++.h>
    208 
    209 using namespace std;
    210 
    211 const int N = 200043;
    212 const int K = 3;
    213 const int LN = 20;
    214 
    215 vector<int> g[N];
    216 int p[N];
    217 pair<int, int> dp_down[N][K];
    218 int dp_up[N];
    219 int q_index;
    220 int ans[N];
    221 int f[N];
    222 
    223 void upd_down(int idx, pair<int, int> p)
    224 {
    225     if(dp_down[idx][K - 1] < p)
    226     {
    227         dp_down[idx][K - 1] = p;
    228         int j = K - 1;
    229         while(j != 0)
    230         {
    231             if(dp_down[idx][j - 1] < dp_down[idx][j])
    232             {
    233                 swap(dp_down[idx][j - 1], dp_down[idx][j]);
    234                 j--;
    235             }
    236             else break;
    237         }
    238     }
    239 }
    240 
    241 void upd(pair<int, int>& p, int x)
    242 {
    243     if(p.second < x) p.second = x;
    244     if(p.first < p.second) swap(p.first, p.second);
    245 }
    246 
    247 int get_cur(int x)
    248 {
    249     pair<int, int> cur_ans = {0, 0};
    250     for(int i = 0; i < K; i++)
    251         if(dp_down[x][i].second != f[x])
    252             upd(cur_ans, dp_down[x][i].first);
    253     if(f[x] != -1)
    254         upd(cur_ans, dp_up[x]);
    255     return cur_ans.second + 1;        
    256 }
    257 
    258 int get_full(int x)
    259 {
    260     pair<int, int> cur_ans = {0, 0};
    261     for(int i = 0; i < K; i++)
    262         upd(cur_ans, dp_down[x][i].first);
    263     upd(cur_ans, dp_up[x]);
    264     return cur_ans.second + 1;    
    265 }
    266 
    267 void dfs1(int x, int parent = -1)
    268 {
    269     p[x] = parent;
    270     for(auto y : g[x])
    271     {
    272         if(y > q_index) continue;
    273         if(y != parent)
    274         {
    275             dfs1(y, x);
    276             upd_down(x, make_pair(get_cur(y), y));
    277         }
    278     }
    279 }
    280 
    281 void dfs2(int x)
    282 {
    283     if(p[x] != -1)
    284         dp_up[x] = get_cur(p[x]);
    285     for(auto y : g[x])
    286     {
    287         if(y > q_index) continue;
    288         if(y != p[x])
    289         {
    290             f[x] = y;
    291             dfs2(y);
    292             f[x] = -1;
    293         }
    294     }
    295 }
    296 
    297 int get_ans(int x)
    298 {
    299     q_index = x + 2;
    300     for(int i = 1; i <= q_index; i++)
    301     {
    302         dp_up[i] = 0;
    303         for(int j = 0; j < K; j++)
    304             dp_down[i][j] = {0, -1};
    305         p[i] = -1;
    306         f[i] = -1;
    307     }
    308     dfs1(1);
    309     dfs2(1);
    310     int ans = 1;
    311     for(int i = 1; i <= q_index; i++)
    312         ans = max(ans, get_full(i));
    313     return ans;
    314 }
    315 
    316 void rec(int l, int r, int L, int R)
    317 {
    318     if(l >= r) return;
    319     if(L == R)
    320     {
    321         for(int i = l; i < r; i++)
    322             ans[i] = L;
    323         return;
    324     }
    325     int mid = (l + r) / 2;
    326     ans[mid] = get_ans(mid);
    327     rec(l, mid, L, ans[mid]);
    328     rec(mid + 1, r, ans[mid], R);
    329 }
    330 
    331 void solve()
    332 {
    333     int q;
    334     cin >> q;
    335     for(int i = 0; i < q; i++)
    336     {
    337         int x;
    338         cin >> x;
    339         g[x].push_back(i + 2);
    340         g[i + 2].push_back(x);
    341     }
    342     rec(0, q, 1, LN);
    343     for(int i = 0; i < q; i++)
    344         cout << ans[i] << " ";
    345     cout << "\n";
    346 }
    347 
    348 int main()
    349 {
    350     ios_base::sync_with_stdio(0);
    351     cin.tie(0);
    352     int t = 1;
    353     for(int i = 0; i < t; i++)
    354         solve();
    355     return 0;
    356 }
    357 ```