codeforces-scrape

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

1857.md (9338B)


      1 Source: https://codeforces.com/blog/entry/119134
      2 
      3 [1857A - Array Coloring](/contest/1857/problem/A "Codeforces Round 891 (Div. 3)")
      4 
      5 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), prepared: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), [Esestree](/profile/Esestree "Expert Esestree")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code C++**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16 int main()
     17 {
     18     int t;cin>>t;
     19     while(t--)
     20     {
     21         int n;cin>>n;
     22         int cnt=0;
     23         for(int i=0;i<n;i++)
     24         {
     25             int x;cin>>x;
     26             if(x%2!=0)cnt++;
     27         }
     28         if(cnt%2==0)cout<<"YES\n";
     29         else cout<<"NO\n";
     30     }
     31 }
     32 ```
     33 
     34 **Code Python**
     35 
     36 ```
     37 for i in range(int(input())):
     38     n=int(input())
     39     a=[*map(int,input().split())]
     40     cnt=0
     41     for i in range(n):
     42         if a[i]%2!=0:cnt+=1
     43     if cnt%2==0:print('YES')
     44     else:print('NO')
     45 ```
     46 
     47 **Rate the problem**
     48 
     49 * Good task
     50 * Average task
     51 * Bad task
     52 * Didn't solve
     53 
     54 [1857B - Maximum Rounding](/contest/1857/problem/B "Codeforces Round 891 (Div. 3)")
     55 
     56 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), prepared: [FBI](/profile/FBI "Candidate Master FBI"), [Esestree](/profile/Esestree "Expert Esestree")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Code C++**
     63 
     64 ```
     65 #include<bits/stdc++.h>
     66 using namespace std;
     67 int main()
     68 {
     69     int t;cin>>t;
     70     while(t--)
     71     {
     72         string s;cin>>s;
     73         s='0'+s;
     74         int p=s.size();
     75         for(int i=s.size()-1;i>=0;i--)
     76         {
     77             if(s[i]>='5')s[i-1]++,p=i;
     78         }
     79         for(int i=(s[0]=='0');i<s.size();i++)
     80         {
     81             cout<<(i>=p?'0':s[i]);
     82         }
     83         cout<<"\n";
     84     }
     85 }
     86 ```
     87 
     88 **Code Python**
     89 
     90 ```
     91 for i in range(int(input())):
     92     s=[0]+[*map(int,list(input()))]
     93     k=len(s)
     94     for i in range(len(s)-1,0,-1):
     95         if s[i]>4:s[i-1]+=1;k=i
     96     if s[0]!=0:print(s[0],end='')
     97     s=[*map(str,s)]
     98     print(''.join(s[1:k]+['0']*(len(s)-k)))
     99 ```
    100 
    101 **Rate the problem**
    102 
    103 * Good task
    104 * Average task
    105 * Bad task
    106 * Didn't solve
    107 
    108 [1857C - Assembly via Minimums](/contest/1857/problem/C "Codeforces Round 891 (Div. 3)")
    109 
    110 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), prepared: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), [Esestree](/profile/Esestree "Expert Esestree")
    111 
    112 **Tutorial**
    113 
    114 Tutorial is loading...
    115 
    116 **Code C++**
    117 
    118 ```
    119 #include<bits/stdc++.h>
    120 using namespace std;
    121 int main()
    122 {
    123     int t;cin>>t;
    124     while(t--)
    125     {
    126         int n;cin>>n;
    127         int m=n*(n-1)/2,b[m];
    128         for(int i=0;i<m;i++)cin>>b[i];
    129         sort(b,b+m);
    130         for(int i=0;i<m;i+=--n)cout<<b[i]<<' ';
    131         cout<<"1000000000\n";
    132     }
    133 }
    134 ```
    135 
    136 **Code Python**
    137 
    138 ```
    139 for _ in range(int(input())):
    140     n=int(input())
    141     l=sorted(map(int,input().split()))
    142     j=0
    143     for i in range(n-1,0,-1):
    144         print(l[j],end=' ')
    145         j+=i
    146     print(l[-1])
    147 ```
    148 
    149 **Rate the problem**
    150 
    151 * Good task
    152 * Average task
    153 * Bad task
    154 * Didn't solve
    155 
    156 [1857D - Strong Vertices](/contest/1857/problem/D "Codeforces Round 891 (Div. 3)")
    157 
    158 Author: [Pa_sha](/profile/Pa_sha "Expert Pa_sha"), prepared: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), [Esestree](/profile/Esestree "Expert Esestree")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Code C++**
    165 
    166 ```
    167 #include<bits/stdc++.h>
    168 using namespace std;
    169 const int N=200005;
    170 int a[N],b[N];
    171 int main()
    172 {
    173     int t;cin>>t;
    174     while(t--)
    175     {
    176         int n;cin>>n;
    177         for(int i=1;i<=n;i++)cin>>a[i];
    178         for(int i=1;i<=n;i++)cin>>b[i];
    179         int mx=INT_MIN;
    180         for(int i=1;i<=n;i++)mx=max(mx,a[i]-b[i]);
    181         int c=0;
    182         for(int i=1;i<=n;i++)c+=(a[i]-b[i]==mx);
    183         cout<<c<<"\n";
    184         for(int i=1;i<=n;i++)if(a[i]-b[i]==mx)cout<<i<<' ';
    185         cout<<"\n";
    186     }
    187 }
    188 ```
    189 
    190 **Code Python**
    191 
    192 ```
    193 for _ in range(int(input())):
    194     n=int(input())
    195     a=[*map(int,input().split())]
    196     b=[*map(int,input().split())]
    197     c=[a[i]-b[i] for i in range(n)]
    198     mx=max(c)
    199     ans=[]
    200     for i in range(n):
    201         if c[i]==mx:ans.append(i+1)
    202     print(len(ans))
    203     print(*ans)
    204 ```
    205 
    206 **Rate the problem**
    207 
    208 * Good task
    209 * Average task
    210 * Bad task
    211 * Didn't solve
    212 
    213 [1857E - Power of Points](/contest/1857/problem/E "Codeforces Round 891 (Div. 3)")
    214 
    215 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), prepared: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), [Esestree](/profile/Esestree "Expert Esestree")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Code C++**
    222 
    223 ```
    224 #include<bits/stdc++.h>
    225 using namespace std;
    226 const int N=200005;
    227 pair<int,int>x[N];
    228 long long a[N];
    229 int main()
    230 {
    231     int t;cin>>t;
    232     while(t--)
    233     {
    234         int n;cin>>n;
    235         long long s1=0,s2=0;
    236         for(int i=1;i<=n;i++)
    237         {
    238             cin>>x[i].first;
    239             x[i].second=i;
    240             s2+=x[i].first;
    241         }
    242         sort(x+1,x+n+1);
    243         for(int i=1;i<=n;i++)
    244         {
    245             s2-=x[i].first;
    246             s1+=x[i].first;
    247             a[x[i].second]=n+1ll*x[i].first*(2*i-n)-s1+s2;
    248         }
    249         for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
    250     }
    251 }
    252 ```
    253 
    254 **Code Python**
    255 
    256 ```
    257 for i in range(int(input())):
    258     n=int(input())
    259     a=sorted([(b,i)for i,b in enumerate(map(int,input().split()))])
    260     ans=[0]*n
    261     s1=0
    262     s2=sum(a[i][0] for i in range(n))
    263     for i in range(n):
    264         ans[a[i][1]]=s2-a[i][0]*(n-i)+n-i+a[i][0]*i-s1+i
    265         s1+=a[i][0]
    266         s2-=a[i][0]
    267     print(*ans)
    268 ```
    269 
    270 **Rate the problem**
    271 
    272 * Good task
    273 * Average task
    274 * Bad task
    275 * Didn't solve
    276 
    277 [1857F - Sum and Product](/contest/1857/problem/F "Codeforces Round 891 (Div. 3)")
    278 
    279 Author: [Pa_sha](/profile/Pa_sha "Expert Pa_sha"), prepared: [Pa_sha](/profile/Pa_sha "Expert Pa_sha"), [Esestree](/profile/Esestree "Expert Esestree")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Code C++**
    286 
    287 ```
    288 #include<bits/stdc++.h>
    289 using namespace std;
    290 map<long long,int>cnt;
    291 long long my_sqrt(long long a)
    292 {
    293     long long l=0,r=5000000001;
    294     while(r-l>1)
    295     {
    296         long long mid=(l+r)/2;
    297         if(1ll*mid*mid<=a)l=mid;
    298         else r=mid;
    299     }
    300     return l;
    301 }
    302 long long get(int b,long long c)
    303 {
    304     long long D=1ll*b*b-4ll*c;
    305     if(D<0)return 0;
    306     long long x1=(b-my_sqrt(D))/2;
    307     long long x2=(b+my_sqrt(D))/2;
    308     if(x1+x2!=b||x1*x2!=c)return 0;
    309     if(x1==x2)return 1ll*cnt[x1]*(cnt[x1]-1)/2ll;
    310     else return 1ll*cnt[x1]*cnt[x2];
    311 }
    312 int main()
    313 {
    314     int t;cin>>t;
    315     while(t--)
    316     {
    317         int n;cin>>n;
    318         cnt.clear();
    319         for(int i=1;i<=n;i++)
    320         {
    321             int x;cin>>x;
    322             cnt[x]++;
    323         }
    324         int q;cin>>q;
    325         for(int i=0;i<q;i++)
    326         {
    327             int b;long long c;
    328             cin>>b>>c;
    329             cout<<get(b,c)<<" \n"[i==q-1];
    330         }
    331     }
    332 }
    333 ```
    334 
    335 **Code Python**
    336 
    337 ```
    338 from collections import Counter
    339 from math import sqrt
    340  
    341 for _ in range(int(input())):
    342     n=int(input())
    343     a=[*map(int,input().split())]
    344     d=Counter(map(str,a))
    345     for i in range(int(input())):
    346         x,y=map(int,input().split())
    347         if x*x-4*y<0:print(0);continue
    348         D=int(sqrt(x*x-4*y))
    349         x1=(x+D)//2
    350         x2=(x-D)//2
    351         if x1+x2!=x or x1*x2!=y:print(0);continue
    352         if x1!=x2:print(d[str(x1)]*d[str(x2)])
    353         else:print(d[str(x1)]*(d[str(x1)]-1)//2)
    354 ```
    355 
    356 **Rate the problem**
    357 
    358 * Good task
    359 * Average task
    360 * Bad task
    361 * Didn't solve
    362 
    363 [1857G - Counting Graphs](/contest/1857/problem/G "Codeforces Round 891 (Div. 3)")
    364 
    365 Author: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), prepared: [JuicyGrape](/profile/JuicyGrape "Expert JuicyGrape"), [Esestree](/profile/Esestree "Expert Esestree")
    366 
    367 **Tutorial**
    368 
    369 Tutorial is loading...
    370 
    371 **Code C++**
    372 
    373 ```
    374 #include<bits/stdc++.h>
    375 using namespace std;
    376 const int N=200000,mod=998244353;
    377 int p[N+1],sz[N+1];
    378 struct edge
    379 {
    380     int u,v,w;
    381     void read(){cin>>u>>v>>w;}
    382     bool operator<(edge x){return w<x.w;}
    383 }a[N+1];
    384 int leader(int v)
    385 {
    386     if(p[v]==v)return v;
    387     else return p[v]=leader(p[v]);
    388 }
    389 void unite(int u,int v)
    390 {
    391     u=leader(u);
    392     v=leader(v);
    393     p[u]=v;
    394     sz[v]+=sz[u];
    395 }
    396 long long binpow(long long a,long long n)
    397 {
    398     if(n==0)return 1;
    399     if(n%2==0)return binpow(a*a%mod,n/2);
    400     else return a*binpow(a,n-1)%mod;
    401 }
    402 int main()
    403 {
    404     int t;cin>>t;
    405     while(t--)
    406     {
    407         int n,S;cin>>n>>S;
    408         for(int i=1;i<=n;i++)p[i]=i,sz[i]=1;
    409         for(int i=0;i<n-1;i++)a[i].read();
    410         sort(a,a+n-1);
    411         long long ans=1;
    412         for(int i=0;i<n-1;i++)
    413         {
    414             int sub_u=sz[leader(a[i].u)];
    415             int sub_v=sz[leader(a[i].v)];
    416             ans=ans*binpow(S-a[i].w+1,1ll*sub_u*sub_v-1)%mod;
    417             unite(a[i].u,a[i].v);
    418         }
    419         cout<<ans<<"\n";
    420     }
    421 }
    422 ```
    423 
    424 **Code Python**
    425 
    426 ```
    427 mod=998244353
    428 def find_(v):
    429     stack=[v]
    430     while dsu[v]!=v:
    431         stack.append(dsu[v])
    432         v=stack[-1]
    433     while stack:
    434         dsu[stack[-1]]=dsu[v]
    435         v=stack.pop()
    436     return dsu[v]
    437  
    438 for i in range(int(input())):
    439     n,S=map(int,input().split())
    440     l=[tuple(map(int,input().split()))for i in range(n-1)]
    441     l.sort(key=lambda x:x[2])
    442     ans=1
    443     dsu=[i for i in range(n)]
    444     coun=[1]*n
    445     for a,b,c in l:
    446         a-=1;b-=1
    447         if find_(a)!=find_(b):
    448             ans=ans*pow(S-c+1,coun[dsu[a]]*coun[dsu[b]]-1,mod)
    449             ans%=mod
    450             coun[dsu[a]]+=coun[dsu[b]]
    451             coun[dsu[b]]=0
    452             dsu[b]=dsu[a]
    453     print(ans)
    454 ```
    455 
    456 **Rate the problem**
    457 
    458 * Good task
    459 * Average task
    460 * Bad task
    461 * Didn't solve