codeforces-scrape

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

2231.md (8492B)


      1 Source: https://codeforces.com/blog/entry/153910
      2 
      3 **Problem A**:
      4 
      5 **Editorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 t = int(input())
     13 for tt in range(t):
     14     n = int(input())
     15     ans = [2 * i + 1 for i in range(n)]
     16     print(*ans)
     17 ```
     18 
     19 **Problem B** (Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")):
     20 
     21 **Editorial**
     22 
     23 Tutorial is loading...
     24 
     25 **Code**
     26 
     27 ```
     28 #include <bits/stdc++.h>
     29 
     30 #define all(a) a.begin(), a.end()
     31 #define rall(a) a.rbegin(), a.rend()
     32 #define len(a) (int)(a.size())
     33 
     34 #ifdef LOCAL
     35 #define __lg(n) log2(n)
     36 #endif
     37 
     38 using namespace std;
     39 
     40 using ll = long long;
     41 using ull = unsigned long long;
     42 using ld = long double;
     43 
     44 template<typename T>
     45 using PQ = priority_queue<T, vector<T>, greater<>>;
     46 
     47 void solve() {
     48     int n;
     49     cin >> n;
     50     vector<int> a(n);
     51     for (int i = 0; i < n; ++i) {
     52         cin >> a[i];
     53     }
     54     int mx = 0;
     55     for (int i = 0; i < n &mdash; 1; ++i) {
     56         mx = max(mx, a[i] &mdash; a[i + 1]);
     57     }
     58     for (int i = 1; i < n; ++i) {
     59         if (a[i] < a[i &mdash; 1]) {
     60             a[i] += mx;
     61         }
     62     }
     63     if (is_sorted(all(a))) {
     64         cout << "YES\n";
     65     } else {
     66         cout << "NO\n";
     67     }
     68 }
     69 
     70 signed main() {
     71     ios_base::sync_with_stdio(0);
     72     cin.tie(0);
     73 
     74     int t = 1;
     75     cin >> t;
     76     while (t--) solve();
     77 }
     78 ```
     79 
     80 **Задача C**:
     81 
     82 **Editorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Code**
     87 
     88 ```
     89 for _ in range(int(input())):
     90     n = int(input())
     91     a = list(map(int, input().split()))
     92     cnt1 = dict()
     93     cnt2 = dict()
     94     x = a[0]
     95     a = a[1:]
     96     s = set()
     97     c = 0
     98     while x not in s:
     99         if x not in cnt1:
    100             cnt1[x] = 0
    101             cnt2[x] = 0
    102         cnt1[x] += 1
    103         cnt2[x] += c
    104         s.add(x)
    105         if x & 1:
    106             x += 1
    107         else:
    108             x >>= 1
    109         c += 1
    110     for x in a:
    111         s = set()
    112         c = 0
    113         while x not in s:
    114             if x in cnt1:
    115                 cnt1[x] += 1
    116                 cnt2[x] += c
    117             s.add(x)
    118             if x & 1:
    119                 x += 1
    120             else:
    121                 x >>= 1
    122             c += 1
    123     ans = 10 ** 18
    124     for k, v in cnt1.items():
    125         if v == n:
    126             ans = min(ans, cnt2[k])
    127     print(ans)
    128 ```
    129 
    130 **Problem D** (Author: [sunkuangzheng](/profile/sunkuangzheng "Grandmaster sunkuangzheng")):
    131 
    132 **Editorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Code**
    137 
    138 ```
    139 #include<bits/stdc++.h>
    140 #ifdef DEBUG_LOCAL
    141 #include <mydebug/debug.h>
    142 #endif
    143 using ll = long long;
    144 const int N = 5e5+5;
    145 using namespace std;
    146 int T,n; string s; ll a[N],c[N],b[N],d[N];
    147 void los(){
    148     cin >> n >> s,s = " " + s; d[0] = 1;
    149     for(int i = 1;i <= n;i ++) cin >> a[i],d[i] = 0;
    150     for(int i = 1;i <= n;i ++) cin >> c[i];
    151     c[0] = -1e18,b[0] = 0;
    152     for(int i = 1;i <= n;i ++){
    153         if(c[i] != c[i &mdash; 1]){
    154             if(c[i] < c[i-1]) return cout << "No\n",void();
    155             b[i] = c[i],d[i] = 1;
    156             for(int j = i;j >= 0;j --){
    157                 if(s[j] == '1'){
    158                     if(d[j &mdash; 1] && b[j &mdash; 1] + a[j] != b[j]) return cout << "No\n",void();
    159                     d[j &mdash; 1] = 1,b[j &mdash; 1] = b[j] &mdash; a[j];
    160                 }else break;
    161             }
    162         }
    163     }for(int i = 1;i <= n;i ++){
    164         if(s[i] == '1') b[i] = b[i-1] + a[i],d[i] = 1;
    165         if(!d[i]) b[i] = -1e16;
    166         a[i] = b[i] &mdash; b[i-1];
    167         if(max(c[i-1],b[i]) != c[i]) return cout << "No\n",void();
    168     }
    169     cout << "Yes\n";
    170     for(int i = 1;i <= n;i ++){
    171         cout << a[i] << " \n"[i == n];
    172     }
    173 }int main(){
    174     ios::sync_with_stdio(0),cin.tie(0);
    175     for(cin >> T;T --;) los();
    176 }
    177 ```
    178 
    179 **Problem E**:
    180 
    181 **Editorial**
    182 
    183 Tutorial is loading...
    184 
    185 **Code**
    186 
    187 ```
    188 #include <bits/stdc++.h>
    189  
    190 #define all(a) a.begin(), a.end()
    191 #define rall(a) a.rbegin(), a.rend()
    192 #define len(a) (int)(a.size())
    193  
    194 using namespace std;
    195  
    196 using ll = long long;
    197 using ld = long double;
    198  
    199 const int N = 2228;
    200  
    201 vector<int> G[N];
    202 int tin[N], tout[N];
    203 int timer = 0;
    204 int cntup[N][N];
    205 int cntdown[N][N];
    206 ll ans1 = 0, ans2 = 0, ans3 = 0;
    207  
    208 void solve_path(int n, int v, int d) {
    209     vector<int> dist(n);
    210     auto dfs = [&](auto &self, int v, int p, int h = 0) -> void {
    211         dist[v] = h;
    212         for (int i : G[v]) {
    213             if (i != p) self(self, i, v, h + 1);
    214         }
    215     };
    216  
    217     dfs(dfs, v, -1, 0);
    218  
    219     for (int i = v + 1; i < n; ++i) {
    220         if (dist[i] == d) {
    221             ans1 += d - 1;
    222         }
    223     }
    224 }
    225  
    226 void dfs_tin(int v, int p) {
    227     tin[v] = timer++;
    228  
    229     for (int i : G[v]) {
    230         if (i != p) dfs_tin(i, v);
    231     }
    232     tout[v] = timer;
    233 }
    234  
    235 void solve() {
    236     int n, d;
    237     cin >> n >> d;
    238     --d;
    239     for (int i = 0; i < n; ++i) G[i].clear();
    240     ans1 = 0, ans2 = 0, ans3 = 0, timer = 0;
    241  
    242     for (int i = 0; i < n - 1; ++i) {
    243         int a, b;
    244         cin >> a >> b;
    245         G[a - 1].push_back(b - 1);
    246         G[b - 1].push_back(a - 1);
    247     }
    248  
    249     for (int i = 0; i < n; ++i) solve_path(n, i, d);
    250     for (int i = 0; i < n; ++i) {
    251         fill(cntup[i], cntup[i] + N, 0);
    252         fill(cntdown[i], cntdown[i] + N, 0);
    253     }
    254     dfs_tin(0, -1);
    255  
    256     for (int i = 0; i < n; ++i) {
    257         auto dfs = [&](auto &self, int v, int p, int h) -> void {
    258             if (tin[i] <= tin[v] && tin[v] < tout[i]) ++cntdown[i][h];
    259             else ++cntup[i][h];
    260  
    261             for (int j : G[v]) {
    262                 if (j != p) self(self, j, v, h + 1);
    263             }
    264         };
    265  
    266         dfs(dfs, i, -1, 0);
    267     }
    268  
    269     vector<int> h(n);
    270     auto dfs = [&](auto &self, int v, int p, int hh = 0) -> vector<int> {
    271         int m = len(G[v]);
    272         vector<vector<int>> who(m);
    273         vector<int> all;
    274         all.push_back(v);
    275         h[v] = hh;
    276  
    277         for (int i = 0; i < len(G[v]); ++i) {
    278             if (G[v][i] == p) continue;
    279  
    280             who[i] = self(self, G[v][i], v, hh + 1);
    281             for (int j : who[i]) all.push_back(j);
    282  
    283             for (int j = 0; j < i; ++j) {
    284                 for (int v1 : who[i]) {
    285                     for (int v2 : who[j]) {
    286  
    287                         int D = h[v1] + h[v2] - 2 * hh;
    288                         if (D >= d) continue;
    289                         int need = d - D;
    290                         ans2 += cntup[v][need];
    291                         int cnt3 = cntdown[v][need];
    292                         cnt3 -= cntdown[G[v][i]][need - 1];
    293                         cnt3 -= cntdown[G[v][j]][need - 1];
    294                         ans3 += cnt3;
    295  
    296                     }
    297                 }
    298             }
    299         }
    300  
    301         return all;
    302     };
    303  
    304     dfs(dfs, 0, -1, 0);
    305     cout << ans1 + ans2 + ans3 / 3 << '\n';
    306 }
    307  
    308 int main() {
    309     ios_base::sync_with_stdio(0);
    310     cin.tie(0);
    311  
    312     int t = 1;
    313     cin >> t;
    314     while (t--) solve();
    315 }
    316 ```
    317 
    318 **Problem F** (Author: [Vladithur](/profile/Vladithur "Master Vladithur")):
    319 
    320 **Editorial**
    321 
    322 Tutorial is loading...
    323 
    324 **Code**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328  
    329 #define all(x) (x).begin(), (x).end()
    330 #define allr(x) (x).rbegin(), (x).rend()
    331 #define gsize(x) (int)((x).size())
    332  
    333 const char nl = '\n';
    334 typedef long long ll;
    335 typedef long double ld;
    336  
    337 using namespace std;
    338  
    339 const int K = 450;
    340  
    341 void solve() {
    342     int n, q;
    343     cin >> n >> q;
    344  
    345     vector<int> f(n, -1); // f[i] = -1 if impossible, 1 if i = a^2, 2 if i = a^2 + b^2
    346     for (int a = 1; a * a < n; a++) {
    347         for (int b = a; a * a + b * b < n; b++) {
    348             f[a * a + b * b] = 2;
    349         }
    350         
    351         f[a * a] = 1;
    352     }
    353     
    354     vector<int> g(n, -1); // g[i] = -1 if impossible, else min `b` over i = a^2 - b^2
    355     for (int b = 1; b * b < n; b++) {
    356         for (int a = b; a * a - b * b < n; a++) {
    357             int v = a * a - b * b;
    358             if (g[v] < 0) g[v] = b * b;
    359         }
    360     }
    361     
    362     while (q--) {
    363         int a, b;
    364         cin >> a >> b;
    365         
    366         int ans = 4;
    367         for (int d = -K; d <= K; d++) {
    368             int x = a + abs(d) * d;
    369             if (x <= 0 || x > n) continue;
    370             
    371             int ta = x, tb = b;
    372             if (ta > tb) swap(ta, tb);
    373             
    374             int tans = 4;
    375             {
    376                 int v = tb - ta;
    377                 if (g[v] > 0 && g[v] <= max(n - tb, ta - 1)) {
    378                     tans = 2;
    379                 }
    380                 
    381                 if (f[v] > 0) {
    382                     tans = f[v];
    383                 }
    384                 
    385                 if (d != 0) tans++;
    386             }
    387             
    388             ans = min(ans, tans);
    389         }
    390         
    391         cout << ans << nl;
    392     }
    393 }
    394  
    395 int main() {
    396 	ios::sync_with_stdio(0); cin.tie(0);
    397     
    398     int t;
    399     cin >> t;
    400     while (t--) solve();
    401 }
    402 ```