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