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