codeforces-scrape

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

2008.md (12534B)


      1 Source: https://codeforces.com/blog/entry/133509
      2 
      3 [2008A - Экзамен Сакурако](/contest/2008/problem/A "Codeforces Round 970 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution in C++**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main(){
     17     int t;
     18     cin>>t;
     19     while(t--)
     20     {
     21         int cnt1,cnt2;
     22         cin>>cnt1>>cnt2;
     23         if(cnt1%2)
     24         {
     25             cout<<"NO"<<endl;
     26         }
     27         else
     28         {
     29             if(cnt2%2==0)
     30             {
     31                 cout<<"YES"<<endl;
     32             }
     33             else
     34             {
     35                 if(cnt1==0)
     36                 {
     37                     cout<<"NO"<<endl;
     38                 }
     39                 else
     40                 {
     41                     cout<<"YES"<<endl;
     42                 }
     43             }
     44         }
     45     }
     46 }
     47 ```
     48 
     49 **Solution in Python**
     50 
     51 ```
     52 t=int(input())
     53 for _ in range(t):
     54     a,b=map(int,input().split())
     55     if a%2==1:
     56         print("NO")
     57         continue
     58     if a==0 and b%2==1:
     59         print("NO")
     60         continue
     61     print("YES")
     62 ```
     63 
     64 **Rate the problem**
     65 
     66 * Didn't solve
     67 * Good task
     68 * Average task
     69 * Bad task
     70 
     71 [2008B - Квадрат или нет](/contest/2008/problem/B "Codeforces Round 970 (Div. 3)")
     72 
     73 **Tutorial**
     74 
     75 Tutorial is loading...
     76 
     77 **Solution in C++**
     78 
     79 ```
     80 #include <bits/stdc++.h>
     81 using namespace std;
     82 
     83 int main() {
     84     int t;
     85     cin>>t;
     86     while(t--)
     87     {
     88         int n;
     89         cin>>n;
     90         string s;
     91         cin>>s;
     92         int id=0;
     93         while(id<n&&s[id]=='1')
     94         {
     95             id++;
     96         }
     97         if(id==n)
     98         {
     99             if(n==4)
    100             {
    101                 cout<<"Yes"<<endl;
    102             }
    103             else
    104             {
    105                 cout<<"No"<<endl;
    106             }
    107         }
    108         else
    109         {
    110             if((id-1)*(id-1)==n)
    111             {
    112                 cout<<"Yes"<<endl;
    113             }
    114             else
    115             {
    116                 cout<<"No"<<endl;
    117             }
    118         }
    119     }
    120     return 0;
    121 }
    122 ```
    123 
    124 **Solution in Python**
    125 
    126 ```
    127 for _ in range(int(input())):
    128     n=int(input())
    129     s=input()
    130     i=0
    131     while i<n and s[i]=='1':
    132         i+=1
    133     if i==n:
    134         if n==4:
    135             print("Yes")
    136         else:
    137             print("No")
    138         continue
    139     i-=1
    140     if i*i==n:
    141         print("Yes")
    142     else:
    143         print("No")
    144 ```
    145 
    146 **Rate the problem**
    147 
    148 * Didn't solve
    149 * Good task
    150 * Average task
    151 * Bad task
    152 
    153 [2008C - Самый длинный хороший массив](/contest/2008/problem/C "Codeforces Round 970 (Div. 3)")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution in C++**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 int main(){
    167     int t;
    168     cin>>t;
    169     while(t--)
    170     {
    171         long long a,b;
    172         cin>>a>>b;
    173         b-=a;
    174         long long l=2,r=1000000000;
    175         while(l<r)
    176         {
    177             long long m=(l+r)/2;
    178             if(m*(m-1)/2<=b)
    179             {
    180                 l=m+1;
    181             }
    182             else
    183             {
    184                 r=m;
    185             }
    186         }
    187         cout<<l-1<<endl;
    188     }
    189 }
    190 ```
    191 
    192 **Solution in Python**
    193 
    194 ```
    195 for _ in range(int(input())): 
    196     a, b = map(int, input().split())
    197     i = 0
    198     while a + i <= b:
    199         a += i
    200         i += 1
    201     print(i)
    202 ```
    203 
    204 **Rate the problem**
    205 
    206 * Didn't solve
    207 * Good task
    208 * Average task
    209 * Bad task
    210 
    211 [2008D - Хобби Сакурако](/contest/2008/problem/D "Codeforces Round 970 (Div. 3)")
    212 
    213 **Tutorial**
    214 
    215 Tutorial is loading...
    216 
    217 **Solution in C++**
    218 
    219 ```
    220 #include <bits/stdc++.h>
    221 
    222 using namespace std;
    223 
    224 int main(){
    225     int t;
    226     cin>>t;
    227     while(t--)
    228     {
    229         long long n;
    230         cin>>n;
    231         long long p[n+1]={0},b[n+1]={0};
    232         int us[n+1]={0};
    233         for(int i=1;i<=n;i++)
    234         {
    235             cin>>p[i];
    236         }
    237         string s;
    238         cin >> s;
    239         for(int i=1;i<=n;i++)
    240         {
    241             if(us[i])continue;
    242             int sz=0;
    243             while(!us[i])
    244             {
    245                 us[i]=1;
    246                 sz += s[i - 1] == '0';
    247                 i=p[i];
    248             }
    249             while(us[i]!=2)
    250             {
    251                 b[i]=sz;
    252                 us[i]=2;
    253                 i=p[i];
    254             }
    255         }
    256         for(int i=1;i<=n;i++)
    257         {
    258             cout<<b[i]<<" ";
    259         }
    260         cout<<endl;
    261     }
    262 }
    263 ```
    264 
    265 **Solution in Python**
    266 
    267 ```
    268 t = int(input())
    269 for _ in range(t):
    270     n = int(input())
    271     b = [0] * (n + 1)
    272     us = [0] * (n + 1)
    273     p = [k-1 for k in map(int, input().split())]
    274     s = input()
    275     for i in range(0, n):
    276         if us[i]:
    277             continue
    278         sz = 0
    279         while not us[i]:
    280             us[i] = 1
    281             sz += s[i] == '0'
    282             i = p[i]
    283         while us[i] != 2:
    284             b[i] = sz
    285             us[i] = 2
    286             i = p[i]
    287     print(" ".join(map(str, b[:-1])))
    288 ```
    289 
    290 **Rate the problem**
    291 
    292 * Didn't solve
    293 * Good task
    294 * Average task
    295 * Bad task
    296 
    297 [2008E - Чередующаяся строка](/contest/2008/problem/E "Codeforces Round 970 (Div. 3)")
    298 
    299 **Tutorial**
    300 
    301 Tutorial is loading...
    302 
    303 **Solution in C++**
    304 
    305 ```
    306 #include <bits/stdc++.h>
    307 
    308 using namespace std;
    309 
    310 int main()
    311 {
    312     int t;
    313     cin>>t;
    314     while(t--)
    315     {
    316         int n;
    317         cin>>n;
    318         string s;
    319         cin>>s;
    320         int res=s.size();
    321         if(n%2==0)
    322         {
    323             vector<int>v[2]={vector<int>(26),vector<int>(26)};
    324             for(int i=0;i<n;i++)
    325             {
    326                 v[i%2][s[i]-'a']++;
    327             }
    328             for(int i=0;i<2;i++)
    329             {
    330                 int mx=0;
    331                 for(int j=0;j<26;j++)
    332                 {
    333                     mx=max(mx,v[i][j]);
    334                 }
    335                 res-=mx;
    336             }
    337             cout<<res<<endl;
    338         }
    339         else
    340         {
    341             vector<int>pref[2]={vector<int>(26),vector<int>(26)};
    342             vector<int>suf[2]={vector<int>(26),vector<int>(26)};
    343             for(int i=n-1;i>=0;i--)
    344             {
    345                 suf[i%2][s[i]-'a']++;
    346             }
    347             for(int i=0;i<n;i++)
    348             {
    349                 suf[i%2][s[i]-'a']--;
    350                 int ans=n;
    351                 for(int k=0;k<2;k++)
    352                 {
    353                     int mx=0;
    354                     for(int j=0;j<26;j++)
    355                     {
    356                         mx=max(mx,suf[1-k][j]+pref[k][j]);
    357                     }
    358                     ans-=mx;
    359                 }
    360                 res=min(res,ans);
    361                 pref[i%2][s[i]-'a']++;
    362             }
    363             cout<<res<<endl;
    364         }
    365     }
    366 }
    367 ```
    368 
    369 **Solution in Python**
    370 
    371 ```
    372 t = int(input())
    373 for _ in range(t):
    374     n = int(input())
    375     s = input()
    376     res = len(s)
    377     if n % 2 == 0:
    378         v = [[0] * 26 for _ in range(2)]
    379         for i in range(n):
    380             v[i % 2][ord(s[i]) - ord('a')] += 1
    381         for i in range(2):
    382             mx = max(v[i])
    383             res -= mx
    384         print(res)
    385     else:
    386         pref = [[0] * 26 for _ in range(2)]
    387         suf = [[0] * 26 for _ in range(2)]
    388         for i in range(n - 1, -1, -1):
    389             suf[i % 2][ord(s[i]) - ord('a')] += 1
    390         for i in range(n):
    391             suf[i % 2][ord(s[i]) - ord('a')] -= 1
    392             ans = n
    393             for k in range(2):
    394                 mx = 0
    395                 for j in range(26):
    396                     mx = max(mx, suf[1 - k][j] + pref[k][j])
    397                 ans -= mx
    398             res = min(res, ans)
    399             pref[i % 2][ord(s[i]) - ord('a')] += 1
    400         print(res)
    401 ```
    402 
    403 **Rate the problem**
    404 
    405 * Didn't solve
    406 * Good task
    407 * Average task
    408 * Bad task
    409 
    410 [2008F - Коробка Сакурако](/contest/2008/problem/F "Codeforces Round 970 (Div. 3)")
    411 
    412 **Tutorial**
    413 
    414 Tutorial is loading...
    415 
    416 **Solution in C++**
    417 
    418 ```
    419 #include <bits/stdc++.h>
    420 
    421 using namespace std;
    422 constexpr int mod=1e9+7;
    423 
    424 long long binpow(long long a,long long b)
    425 {
    426     if(b==0)
    427     {
    428         return 1;
    429     }
    430     if(b%2)
    431     {
    432         return (a*binpow(a,b-1))%mod;
    433     }
    434     return binpow((a*a)%mod,b/2);
    435 }
    436 
    437 int main(){
    438     int t;
    439     cin>>t;
    440     while(t--)
    441     {
    442         long long n;
    443         cin>>n;
    444         long long a[n],sum=0,sumsq=0;
    445         for(int i=0;i<n;i++)
    446         {
    447             cin>>a[i];
    448             sum+=a[i];sum%=mod;
    449             sumsq+=a[i]*a[i];
    450             sumsq%=mod;
    451         }
    452         sum*=sum;sum%=mod;
    453         sum=(sum-sumsq+mod)%mod;
    454         sum=(sum*binpow(2,mod-2))%mod;
    455         long long cnt=n*(n-1)/2;cnt%=mod;
    456         cout<<(sum%mod)*binpow(cnt,mod-2)%mod<<endl;
    457     }
    458 }
    459 ```
    460 
    461 **Solution in Python**
    462 
    463 ```
    464 import sys; input = sys.stdin.readline
    465 for i in range(int(input())):
    466     n = int(input())
    467     a = list(map(int, input().split()))
    468     ans = 0
    469     s = 0
    470     mod = int(1e9 + 7)
    471     for i in range(n): s += a[i]
    472     s %= mod
    473     for i in range(n):
    474         s -= a[i]
    475         ans = (ans + a[i] * s) % mod
    476     ans = (ans * pow(n * (n - 1) // 2, mod - 2, mod)) % mod
    477     print(ans)
    478  
    479 ```
    480 
    481 **Rate the problem**
    482 
    483 * Didn't solve
    484 * Good task
    485 * Average task
    486 * Bad task
    487 
    488 [2008G - Задание Сакурако](/contest/2008/problem/G "Codeforces Round 970 (Div. 3)")
    489 
    490 **Tutorial**
    491 
    492 Tutorial is loading...
    493 
    494 **Solution in C++**
    495 
    496 ```
    497 #include <bits/stdc++.h>
    498 
    499 using namespace std;
    500 
    501 int main(){
    502     int t;
    503     cin>>t;
    504     while(t--)
    505     {
    506         int n,k;
    507         cin>>n>>k;
    508         long long a[n+1],g=0,mx=0;
    509         for(int i=0;i<n;i++)
    510         {
    511             cin>>a[i];
    512             g=__gcd(g,a[i]);
    513             mx=max(mx,a[i]);
    514         }
    515         if(g==0)
    516         {
    517             cout<<k<<endl;
    518             continue;
    519         }
    520         sort(a,a+n);
    521         int q=-g;
    522         if(n!=1)
    523         {
    524             for(int i=0;i<n;i++)
    525             {
    526                 q+=g;
    527                 a[i]=q;
    528             }
    529         }
    530         a[n]=1e16;
    531         long long lst=-1;
    532         for(int i=0;i<=n;i++)
    533         {
    534             if(k<=a[i]-lst-1)
    535             {
    536                 break;
    537             }
    538             k-=max(a[i]-lst-1,0ll);
    539             lst=a[i];
    540         }
    541         cout<<lst+k<<endl;
    542     }
    543 }
    544 ```
    545 
    546 **Solution in Python**
    547 
    548 ```
    549 import math
    550 
    551 t = int(input())
    552 for _ in range(t):
    553     n, k = map(int, input().split())
    554     a = list(map(int, input().split()))
    555     g = 0
    556     mx = 0
    557     for i in range(n):
    558         g = math.gcd(g, a[i])
    559         mx = max(mx, a[i])
    560     if g == 0:
    561         print(k)
    562         continue
    563     a.sort()
    564     q = -g
    565     if n != 1:
    566         for i in range(n):
    567             q += g
    568             a[i] = q
    569     a.append(10**16)
    570     lst = -1
    571     for i in range(n + 1):
    572         if k <= a[i] - lst - 1:
    573             break
    574         k -= max(a[i] - lst - 1, 0)
    575         lst = a[i]
    576     print(lst + k)
    577 ```
    578 
    579 **Rate the problem**
    580 
    581 * Didn't solve
    582 * Good task
    583 * Average task
    584 * Bad task
    585 
    586 [2008H - Тест Сакурако](/contest/2008/problem/H "Codeforces Round 970 (Div. 3)")
    587 
    588 **Tutorial**
    589 
    590 Tutorial is loading...
    591 
    592 **Solution in C++**
    593 
    594 ```
    595 #include <bits/stdc++.h>
    596 
    597 using namespace std;
    598 
    599 int main()
    600 {
    601     int t=1;
    602     cin>>t;
    603     for(int i=1;i<=t;i++)
    604     {
    605         int n,m;
    606         cin>>n>>m;
    607         vector<int>a(n);
    608         vector<int>c(n+1,0ll);
    609         for(int i=0;i<n;i++)
    610         {
    611             cin>>a[i];
    612             c[a[i]]++;
    613         }
    614         for(int i=1;i<=n;i++)
    615         {
    616             c[i]+=c[i-1];
    617         }
    618         int res[n+1]={0};
    619         for(int x=1;x<=n;x++)
    620         {
    621             int l=0,r=x;
    622             while(l<r)
    623             {
    624                 int mid=(l+r)/2;
    625                 int cnt=c[mid];
    626                 for(int k=1;k*x<=n;k++)
    627                 {
    628                     cnt+=c[min(k*x+mid,n)]-c[k*x-1];
    629                 }
    630                 if(cnt-1>=n/2)
    631                 {
    632                     r=mid;
    633                 }
    634                 else
    635                 {
    636                     l=mid+1;
    637                 }
    638             }
    639             res[x]=l;
    640         }
    641         while(m--)
    642         {
    643             int x;
    644             cin>>x;
    645             cout<<res[x]<<" ";
    646         }
    647         cout<<endl;
    648     }
    649 }
    650 ```
    651 
    652 **Solution in Python**
    653 
    654 ```
    655 for _ in range(int(input())):
    656     n, m = map(int, input().split())
    657     a = list(map(int, input().split()))
    658     c = [0] * (n + 1)
    659     
    660     for i in range(n):
    661         c[a[i]] += 1
    662     
    663     for i in range(1, n + 1):
    664         c[i] += c[i - 1]
    665     
    666     res = [0] * (n + 1)
    667     
    668     for x in range(1, n + 1):
    669         l, r = 0, x
    670         while l < r:
    671             mid = (l + r) // 2
    672             cnt = c[mid]
    673             for k in range(1, n // x + 1):
    674                 cnt += c[min(k * x + mid, n)] - c[k * x - 1]
    675             if cnt - 1 >= n // 2:
    676                 r = mid
    677             else:
    678                 l = mid + 1
    679         res[x] = l
    680     
    681     for _ in range(m):
    682         x = int(input())
    683         print(res[x])
    684 ```
    685 
    686 **Rate the problem**
    687 
    688 * Didn't solve
    689 * Good task
    690 * Average task
    691 * Bad task