codeforces-scrape

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

2033.md (7849B)


      1 Source: https://codeforces.com/blog/entry/135520
      2 
      3 [2033A - Sakurako and Kosuke](/contest/2033/problem/A "Codeforces Round 981 (Div. 3)")
      4 
      5 Idea: [FBI](/profile/FBI "Master FBI")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n = int(input())
     16     x = 0
     17     c = 1
     18     while -n <= x <= n:
     19         if c % 2 == 1:
     20             x -= 2 * c - 1
     21         else:
     22             x += 2 * c - 1
     23         c += 1
     24     if c % 2 == 0:
     25         print("Sakurako")
     26     else:
     27         print("Kosuke")
     28 
     29 for tc in range(int(input())):
     30     solve()
     31 ```
     32 
     33 [2033B - Sakurako and Water](/contest/2033/problem/B "Codeforces Round 981 (Div. 3)")
     34 
     35 Idea: [FBI](/profile/FBI "Master FBI")
     36 
     37 **Tutorial**
     38 
     39 Tutorial is loading...
     40 
     41 **Solution**
     42 
     43 ```
     44 def solve():
     45     n = int(input())
     46     mn = dict()
     47     for i in range(n):
     48         a = [int(x) for x in input().split()]
     49         for j in range(n):
     50             mn[i - j] = min(a[j], mn.get(i - j, 0))
     51     ans = 0
     52     for value in mn.values():
     53         ans -= value
     54     print(ans)
     55  
     56 t = int(input())
     57 for _ in range(t):
     58     solve()
     59 ```
     60 
     61 [2033C - Sakurako's Field Trip](/contest/2033/problem/C "Codeforces Round 981 (Div. 3)")
     62 
     63 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
     64 
     65 **Tutorial**
     66 
     67 Tutorial is loading...
     68 
     69 **Solution**
     70 
     71 ```
     72 #include <bits/stdc++.h>
     73 using namespace std;
     74 int main(){
     75     int t;
     76     cin>>t;
     77     while(t--){
     78         int n;
     79         cin>>n;
     80         int a[n+1];
     81         for(int i=1;i<=n;i++){
     82             cin>>a[i];
     83         }
     84         for(int i=n/2-1;i>=1;i--){
     85             if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){
     86                 swap(a[i],a[n-i+1]);
     87             }
     88         }
     89         int re=0;
     90         for(int i=1;i<n;i++){
     91             re+=(a[i]==a[i+1]);
     92         }
     93         cout<<re<<endl;
     94     }
     95 }
     96 ```
     97 
     98 [2033D - Kousuke's Assignment](/contest/2033/problem/D "Codeforces Round 981 (Div. 3)")
     99 
    100 Idea: [FBI](/profile/FBI "Master FBI")
    101 
    102 **Tutorial**
    103 
    104 Tutorial is loading...
    105 
    106 **Solution**
    107 
    108 ```
    109 #include <bits/stdc++.h>
    110 using namespace std;
    111 int main(){
    112     int t;
    113     cin>>t;
    114     while(t--){
    115         int n;
    116         cin>>n;
    117         int a[n+1];
    118         map<int,int>mp;
    119         for(int i=1;i<=n;i++){
    120             cin>>a[i];
    121         }
    122         int p_su[n+1];
    123         p_su[0]=0;
    124         int lst[n+1];
    125         mp[0]=0;
    126         for(int i=1;i<=n;i++){
    127             p_su[i]=p_su[i-1]+a[i];
    128             if(mp.find(p_su[i])==mp.end()){
    129                 lst[i]=-1;
    130             }
    131             else{
    132                 lst[i]=mp[p_su[i]];
    133             }
    134             mp[p_su[i]]=i;
    135         }
    136         int dp[n+1];
    137         memset(dp,0,sizeof dp);
    138         for(int i=1;i<=n;i++){
    139             dp[i]=max(dp[i],dp[i-1]);
    140             if(lst[i]!=-1){
    141                 dp[i]=max(dp[i],dp[lst[i]]+1);
    142             }
    143         }
    144         cout<<*max_element(dp,dp+n+1)<<endl;
    145     }
    146 }
    147 ```
    148 
    149 [2033E - Sakurako, Kosuke, and the Permutation](/contest/2033/problem/E "Codeforces Round 981 (Div. 3)")
    150 
    151 Idea: [FBI](/profile/FBI "Master FBI")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution**
    158 
    159 ```
    160 #include<bits/stdc++.h>
    161 using namespace std;
    162 int main(){
    163     int t;
    164     ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
    165     cin>>t;
    166     while(t--){
    167         int n;
    168         cin>>n;
    169         int p[n+1];
    170         for(int i=1;i<=n;i++){
    171             cin>>p[i];
    172         }
    173         bool us[n+1];
    174         memset(us,0,sizeof us);
    175         int re=0;
    176         for(int i=1;i<=n;i++){
    177             if(!us[i]){
    178                 int cu=i;
    179                 int le=0;
    180                 while(us[cu]==0){
    181                     le++;
    182                     us[cu]=1;
    183                     cu=p[cu];
    184                 }
    185                 re+=(le-1)/2;
    186             }
    187         }
    188         cout<<re<<'\n';
    189     }
    190 }
    191 ```
    192 
    193 [2033F - Kosuke's Sloth](/contest/2033/problem/F "Codeforces Round 981 (Div. 3)")
    194 
    195 Idea: [FBI](/profile/FBI "Master FBI")
    196 
    197 **Tutorial**
    198 
    199 Tutorial is loading...
    200 
    201 **Solution**
    202 
    203 ```
    204 #include <bits/stdc++.h>
    205  
    206 using namespace std;
    207 using LL = long long;
    208 #define ssize(x) (int)(x.size())
    209 #define ALL(x) (x).begin(), (x).end()
    210  
    211 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    212  
    213 int rd(int l, int r) {
    214     return uniform_int_distribution<int>(l, r)(rng);
    215 }
    216 const LL MOD = 1e9 + 7;
    217 int bp(int a, int n) {
    218     if (n == 0)
    219         return 1;
    220     if (n % 2 == 0)
    221         return bp(1LL * a * a % MOD, n / 2);
    222     else
    223         return 1LL * bp(a, n - 1) * a % MOD;
    224 }
    225 int inv(int a) {
    226     return bp(a, MOD - 2);
    227 }
    228 void solve() {
    229     LL n, k;
    230     cin >> n >> k;
    231     n %= MOD;
    232     if (k == 1) {
    233         cout << n << "\n";
    234         return;
    235     }
    236     vector<int> fib(3);
    237     fib[0] = fib[1] = 1;
    238     int cnt = 0;
    239     for (int i = 2; i <= 10 * k; i++) {
    240         fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k;
    241         if (fib[i % 3] == 0)
    242             cnt++;
    243         if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) {
    244             cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n";
    245             return;
    246         }
    247     }
    248 }
    249 int main() {
    250     ios_base::sync_with_stdio(0);
    251     cin.tie(0);
    252     cout.tie(0);
    253     int t = 1;
    254      cin >> t;
    255     while (t--) {
    256         solve();
    257     }
    258 }
    259 ```
    260 
    261 [2033G - Sakurako and Chefir](/contest/2033/problem/G "Codeforces Round 981 (Div. 3)")
    262 
    263 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    264 
    265 **Tutorial**
    266 
    267 Tutorial is loading...
    268 
    269 **Solution**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273  
    274 //#define int long long
    275 #define pb emplace_back
    276 #define mp make_pair
    277 #define x first
    278 #define y second
    279 #define all(a) a.begin(), a.end()
    280 #define rall(a) a.rbegin(), a.rend()
    281  
    282 typedef long double ld;
    283 typedef long long ll;
    284  
    285 using namespace std;
    286  
    287 mt19937 rnd(time(nullptr));
    288  
    289 const int inf = 1e9;
    290 const int M = 1e9 + 7;
    291 const ld pi = atan2(0, -1);
    292 const ld eps = 1e-6;
    293  
    294 void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){
    295     maxd[v] = {0, 0};
    296     if (v != p) h[v] = h[p] + 1;
    297     for(int u: sl[v]){
    298         if (u == p) continue;
    299         precalc(u, v, sl, maxd, h);
    300         if (maxd[v].y < maxd[u].x + 1) {
    301             maxd[v].y = maxd[u].x + 1;
    302         }
    303         if (maxd[v].y > maxd[v].x) {
    304             swap(maxd[v].x, maxd[v].y);
    305         }
    306     }
    307 }
    308  
    309 void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
    310     binup[v][0] = {maxd[p].x, p};
    311     if (maxd[p].x == maxd[v].x + 1) {
    312         binup[v][0].x = maxd[p].y;
    313     }
    314     binup[v][0].x -= h[p];
    315     for(int i = 1; i < 20; ++i){
    316         binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y;
    317         binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x);
    318     }
    319  
    320     for(int u: sl[v]){
    321         if (u == p) continue;
    322         calc_binups(u, v, sl, binup, maxd, h);
    323     }
    324 }
    325  
    326 int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
    327     k = min(k, h[v]);
    328     int res = maxd[v].x - h[v];
    329     int ini = h[v];
    330     for(int i = 19; i >= 0; --i){
    331         if ((1 << i) <= k) {
    332             res = max(res, binup[v][i].x);
    333             v = binup[v][i].y;
    334             k -= (1 << i);
    335         }
    336     }
    337     return res + ini;
    338 }
    339  
    340 void solve(int tc){
    341     int n;
    342     cin >> n;
    343     vector<vector<int>> sl(n);
    344     for(int i = 1; i < n; ++i){
    345         int u, v;
    346         cin >> u >> v;
    347         sl[--u].emplace_back(--v);
    348         sl[v].emplace_back(u);
    349     }
    350     vector<pair<int, int>> maxd(n);
    351     vector<int> h(n);
    352     precalc(0, 0, sl, maxd, h);
    353     vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20));
    354     calc_binups(0, 0, sl, binup, maxd, h);
    355     int q;
    356     cin >> q;
    357     for(int _ = 0; _ < q; ++_){
    358         int v, k;
    359         cin >> v >> k;
    360         cout << get_ans(v - 1, k, binup, maxd, h) << " ";
    361     }
    362 }
    363  
    364 bool multi = true;
    365  
    366 signed main() {
    367     int t = 1;
    368     if (multi)cin >> t;
    369     for (int i = 1; i <= t; ++i) {
    370         solve(i);
    371         cout << "\n";
    372     }
    373     return 0;
    374 }
    375 ```