1466.md (16617B)
1 Source: https://codeforces.com/blog/entry/86126 2 3 [1466A - Bovine Dilemma](/contest/1466/problem/A "Good Bye 2020") 4 5 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 6 * Developer: [Anadi](/profile/Anadi "International Grandmaster Anadi") 7 * First solve: [mip182](/profile/mip182 "International Master mip182") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution 1** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 void solve() { 21 int n; 22 scanf("%d", &n); 23 24 vector <int> in(n); 25 vector <int> is(N); 26 27 for(auto &p: in) 28 scanf("%d", &p); 29 30 for(int i = 0; i < n; ++i) 31 for(int j = i + 1; j < n; ++j) 32 is[in[j] - in[i]] = true; 33 34 int ans = 0; 35 for(auto &v: is) 36 ans += v; 37 printf("%d\n", ans); 38 } 39 40 int main() { 41 int cases; 42 scanf("%d", &cases); 43 44 while(cases--) 45 solve(); 46 return 0; 47 } 48 ``` 49 50 **Solution 2** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 using namespace std; 56 57 void solve() { 58 int n; 59 scanf("%d", &n); 60 61 vector <int> in(n); 62 for(auto &p: in) 63 scanf("%d", &p); 64 65 set <int> S; 66 for(int i = 0; i < n; ++i) 67 for(int j = i + 1; j < n; ++j) 68 S.insert(in[j] - in[i]); 69 70 printf("%d\n", (int)S.size()); 71 } 72 73 int main() { 74 int cases; 75 scanf("%d", &cases); 76 77 while(cases--) 78 solve(); 79 return 0; 80 } 81 ``` 82 83 **Challenge** 84 85 Try to solve it for $n, x_i \leq 10^5$. 86 87 [1466B - Last minute enhancements](/contest/1466/problem/B "Good Bye 2020") 88 89 * Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 90 * Developer: [Anadi](/profile/Anadi "International Grandmaster Anadi") 91 * First solve: [zscoder](/profile/zscoder "International Grandmaster zscoder") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution 1** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 void solve() { 105 int n; 106 scanf("%d", &n); 107 108 int ans = 0; 109 int prv = 0, ok = 0; 110 111 for(int i = 1; i <= n; ++i) { 112 int a; 113 scanf("%d", &a); 114 115 ans += (a != prv); 116 ok |= (a == prv); 117 118 if(prv + 1 < a) 119 ans += ok, ok = 0; 120 prv = a; 121 } 122 123 ans += ok; 124 printf("%d\n", ans); 125 } 126 127 int main() { 128 int cases; 129 scanf("%d", &cases); 130 131 while(cases--) 132 solve(); 133 return 0; 134 } 135 ``` 136 137 **Solution 2** 138 139 ``` 140 #include <bits/stdc++.h> 141 142 using namespace std; 143 144 void solve() { 145 int n; 146 scanf("%d", &n); 147 148 set <int> S; 149 for(int i = 1; i <= n; ++i) { 150 int v; 151 scanf("%d", &v); 152 153 if(S.count(v)) 154 v++; 155 S.insert(v); 156 } 157 158 printf("%d\n", (int)S.size()); 159 } 160 161 int main() { 162 int cases; 163 scanf("%d", &cases); 164 165 while(cases--) 166 solve(); 167 return 0; 168 } 169 ``` 170 171 **Challenge** 172 173 Can you solve it if we can increase note $x_i$ by any integer in $[0, k_i]$, for given $k_i$? 174 175 [1466C - Canine poetry](/contest/1466/problem/C "Good Bye 2020") 176 177 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 178 * Developer: [Anadi](/profile/Anadi "International Grandmaster Anadi") 179 * First solve: [thenymphsofdelphi](/profile/thenymphsofdelphi "Grandmaster thenymphsofdelphi") 180 181 **Tutorial** 182 183 Tutorial is loading... 184 185 **Solution 1** 186 187 ``` 188 #include <bits/stdc++.h> 189 190 using namespace std; 191 192 const int N = 100 * 1000 + 7; 193 194 int n; 195 char in[N]; 196 bool used[N]; 197 198 void solve(){ 199 scanf("%s", in + 1); 200 n = strlen(in + 1); 201 202 for(int i = 1; i <= n; ++i) 203 used[i] = false; 204 205 int ans = 0; 206 for(int i = 2; i <= n; ++i){ 207 bool use_need = false; 208 if(in[i] == in[i - 1] && !used[i - 1]) 209 use_need = true; 210 211 if(i > 2 && in[i] == in[i - 2] && !used[i - 2]) 212 use_need = true; 213 214 used[i] = use_need; 215 ans += used[i]; 216 } 217 218 printf("%d\n", ans); 219 } 220 221 int main(){ 222 int cases; 223 scanf("%d", &cases); 224 225 while(cases--) 226 solve(); 227 return 0; 228 } 229 ``` 230 231 **Solution 2** 232 233 ``` 234 #include <bits/stdc++.h> 235 236 using namespace std; 237 238 const int N = 1e5 + 7; 239 240 int n; 241 char in[N]; 242 int dp[N][2][2]; 243 244 void solve(){ 245 scanf("%s", in + 1); 246 n = strlen(in + 1); 247 248 for(int ta = 0; ta < 2; ++ta) 249 for(int tb = 0; tb < 2; ++tb) 250 dp[0][ta][tb] = 0; 251 252 for(int i = 1; i <= n; ++i) 253 for(int ta = 0; ta < 2; ++ta) 254 for(int tb = 0; tb < 2; ++tb) 255 dp[i][ta][tb] = N; 256 257 for(int i = 1; i <= n; ++i){ 258 if(in[i] != in[i - 1]){ 259 if(in[i] != in[i - 2]) 260 dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][0]); 261 dp[i][0][0] = min(dp[i][0][0], dp[i - 1][0][1]); 262 } 263 264 if(in[i] != in[i - 2]) 265 dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][0]); 266 dp[i][0][1] = min(dp[i][0][1], dp[i - 1][1][1]); 267 268 dp[i][1][0] = min(dp[i][1][0], min(dp[i - 1][0][0], dp[i - 1][0][1]) + 1); 269 dp[i][1][1] = min(dp[i][1][1], min(dp[i - 1][1][0], dp[i - 1][1][1]) + 1); 270 } 271 272 int ans = N; 273 for(int ta = 0; ta < 2; ++ta) 274 for(int tb = 0; tb < 2; ++tb) 275 ans = min(ans, dp[n][ta][tb]); 276 printf("%d\n", ans); 277 } 278 279 int main(){ 280 int cases; 281 scanf("%d", &cases); 282 283 while(cases--) 284 solve(); 285 return 0; 286 } 287 ``` 288 289 **Challenge** 290 291 What if letters can change, and you need the calculate the result after each change? 292 293 [1466D - 13th Labour of Heracles](/contest/1466/problem/D "Good Bye 2020") 294 295 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 296 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 297 * First solve: [w4p3r](/profile/w4p3r "Master w4p3r") 298 299 **Tutorial** 300 301 Tutorial is loading... 302 303 **Solution** 304 305 ``` 306 #include <bits/stdc++.h> 307 308 using namespace std; 309 310 typedef long long int LL; 311 312 const int N = 100 * 1000 + 7; 313 314 int n; 315 int w[N]; 316 int deg[N]; 317 318 void solve() { 319 scanf("%d", &n); 320 for(int i = 1; i <= n; ++i) { 321 scanf("%d", &w[i]); 322 deg[i] = 0; 323 } 324 325 for(int i = 1; i < n; ++i) { 326 int u, v; 327 scanf("%d %d", &u, &v); 328 deg[u]++; deg[v]++; 329 } 330 331 LL ans = 0; 332 vector <int> to_sort; 333 334 for(int i = 1; i <= n; ++i) { 335 for(int j = 1; j < deg[i]; ++j) 336 to_sort.push_back(w[i]); 337 ans += w[i]; 338 } 339 340 sort(to_sort.begin(), to_sort.end()); 341 reverse(to_sort.begin(), to_sort.end()); 342 343 for(auto &v: to_sort) { 344 printf("%lld ", ans); 345 ans += v; 346 } 347 348 printf("%lld\n", ans); 349 } 350 351 int main() { 352 int cases; 353 scanf("%d", &cases); 354 355 while(cases--) 356 solve(); 357 return 0; 358 } 359 ``` 360 361 [1466E - Apollo versus Pan](/contest/1466/problem/E "Good Bye 2020") 362 363 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 364 * Developer: [Anadi](/profile/Anadi "International Grandmaster Anadi") 365 * First solve: [dengyipeng](/profile/dengyipeng "International Master dengyipeng") 366 367 **Tutorial** 368 369 Tutorial is loading... 370 371 **Solution** 372 373 ``` 374 #include <bits/stdc++.h> 375 376 using namespace std; 377 378 typedef long long int LL; 379 380 const int N = 500 * 1000 + 7; 381 const int P = 60; 382 const int MX = 1e9 + 7; 383 384 int n; 385 LL in[N]; 386 int cnt[P]; 387 388 void solve(){ 389 scanf("%d", &n); 390 for(int i = 0; i < P; ++i) 391 cnt[i] = 0; 392 393 for(int i = 1; i <= n; ++i){ 394 scanf("%lld", &in[i]); 395 for(int j = 0; j < P; ++j) 396 cnt[j] += in[i] >> j & 1; 397 } 398 399 int ans = 0; 400 for(int i = 1; i <= n; ++i){ 401 LL exp_or = 0, exp_and = 0; 402 for(int j = 0; j < P; ++j){ 403 if(in[i] >> j & 1){ 404 exp_or += (1LL << j) % MX * n; 405 exp_and += (1LL << j) % MX * cnt[j]; 406 } 407 else 408 exp_or += (1LL << j) % MX * cnt[j]; 409 } 410 411 exp_and %= MX, exp_or %= MX; 412 ans = (ans + 1LL * exp_or * exp_and) % MX; 413 } 414 415 printf("%d\n", ans); 416 } 417 418 int main(){ 419 int cases; 420 scanf("%d", &cases); 421 422 while(cases--) 423 solve(); 424 return 0; 425 } 426 ``` 427 428 [1466F - Euclid's nightmare](/contest/1466/problem/F "Good Bye 2020") 429 430 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 431 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 432 * First solve: [tourist](/profile/tourist "Legendary Grandmaster tourist") 433 434 **Tutorial** 435 436 Tutorial is loading... 437 438 **Solution** 439 440 ``` 441 #include <bits/stdc++.h> 442 443 using namespace std; 444 445 typedef long long int LL; 446 447 const int N = 5e5 + 7; 448 const int MX = 1e9 + 7; 449 450 int n, m; 451 int rep[N]; 452 453 int Find(int a) { 454 if(rep[a] == a) 455 return a; 456 return rep[a] = Find(rep[a]); 457 } 458 459 bool Union(int a, int b) { 460 a = Find(a); 461 b = Find(b); 462 463 rep[a] = b; 464 return a != b; 465 } 466 467 int main() { 468 scanf("%d %d", &n, &m); 469 for(int i = 1; i <= m + 1; ++i) 470 rep[i] = i; 471 472 vector <int> ans; 473 for(int i = 1; i <= n; ++i) { 474 int k; 475 scanf("%d", &k); 476 477 int fa, fb = m + 1; 478 scanf("%d", &fa); 479 480 if(k > 1) 481 scanf("%d", &fb); 482 483 if(Union(fa, fb)) 484 ans.push_back(i); 485 } 486 487 int res = 1; 488 for(int i = 0; i < (int)ans.size(); ++i) 489 res = (res + res) % MX; 490 491 printf("%d %d\n", res, (int)ans.size()); 492 for(auto v: ans) 493 printf("%d ", v); 494 puts(""); 495 return 0; 496 } 497 ``` 498 499 [1466G - Song of the Sirens](/contest/1466/problem/G "Good Bye 2020") 500 501 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 502 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 503 * First solve: [tourist](/profile/tourist "Legendary Grandmaster tourist") 504 505 **Tutorial** 506 507 Tutorial is loading... 508 509 **Solution** 510 511 ``` 512 #include <bits/stdc++.h> 513 514 using namespace std; 515 516 const int MAXLEN = 1e6 + 7; 517 const int MOD = 1e9 + 7; 518 519 int n, q; 520 string s, t; 521 vector <string> songs; 522 523 vector <int> pw; 524 vector <int> sum[26]; 525 526 void read(string &p) { 527 static char input[MAXLEN]; 528 scanf("%s", input); 529 p = input; 530 } 531 532 void prepare_songs() { 533 songs = {s}; 534 for(auto c: t) { 535 if(songs.back().size() >= MAXLEN) 536 break; 537 538 auto p = songs.back(); 539 auto nxt = p + string(1, c) + p; 540 songs.push_back(nxt); 541 } 542 } 543 544 void prepare_sum() { 545 for(int i = 0; i < 26; ++i) { 546 char c = 'a' + i; 547 sum[i].resize(n + 1, 0); 548 549 for(int j = 0; j < n; ++j) 550 sum[i][j + 1] = (sum[i][j] * 2 + (t[j] == c)) % MOD; 551 } 552 553 pw.resize(n + 1, 0); 554 pw[0] = 1; 555 556 for(int i = 1; i <= n; ++i) 557 pw[i] = 2LL * pw[i - 1] % MOD; 558 } 559 560 void init() { 561 scanf("%d %d", &n, &q); 562 read(s), read(t); 563 564 prepare_songs(); 565 prepare_sum(); 566 } 567 568 vector <int> kmp(string &in) { 569 int m = in.size(), cpref = 0; 570 vector <int> dp(m, 0); 571 572 for(int i = 1; i < (int)in.size(); ++i) { 573 while(cpref > 0 && in[cpref] != in[i]) 574 cpref = dp[cpref - 1]; 575 576 if(in[cpref] == in[i]) 577 ++cpref; 578 dp[i] = cpref; 579 } 580 581 return dp; 582 } 583 584 /* Get all borders based on dp from kmp */ 585 vector <bool> get(vector <int> &dp, int m) { 586 vector <bool> ret(m + 1, false); 587 int cur = dp.back(); 588 589 while(cur) { 590 ret[cur] = true; 591 cur = dp[cur - 1]; 592 } 593 594 ret[cur] = true; 595 return ret; 596 } 597 598 int answer(int k, string &w) { 599 int id = 0; 600 while(songs[id].size() < w.size()) 601 ++id; 602 603 if(id > k) 604 return 0; 605 606 int m = w.size(); 607 string s_pref = w + '#' + songs[id]; 608 string s_suf = songs[id] + '#' + w; 609 610 auto dp_pref = kmp(s_pref); 611 auto dp_suf = kmp(s_suf); 612 613 auto pref = get(dp_pref, m); 614 auto suf = get(dp_suf, m); 615 616 /* Compute all internal occurences */ 617 int ret = 0; 618 for(auto &v: dp_pref) 619 ret += (v == m); 620 ret = 1LL * ret * pw[k - id] % MOD; 621 622 /* Compute the remaining occurences */ 623 for(int i = 0; i < m; ++i) { 624 if(!pref[i] || !suf[m - i - 1]) 625 continue; 626 627 int c = w[i] - 'a'; 628 ret = (ret + sum[c][k] - 1LL * sum[c][id] * pw[k - id]) % MOD; 629 } 630 631 ret = (ret + MOD) % MOD; 632 return ret; 633 } 634 635 void solve() { 636 while(q--) { 637 int k; 638 string w; 639 640 scanf("%d", &k); 641 read(w); 642 printf("%d\n", answer(k, w)); 643 } 644 } 645 646 int main() { 647 init(); 648 solve(); 649 return 0; 650 } 651 ``` 652 653 [1466H - Finding satisfactory solutions](/contest/1466/problem/H "Good Bye 2020") 654 655 * Authors: [Okrut](/profile/Okrut "Grandmaster Okrut"), [Anadi](/profile/Anadi "International Grandmaster Anadi") 656 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 657 * First solve: [maroonrk](/profile/maroonrk "Legendary Grandmaster maroonrk") 658 659 **Tutorial** 660 661 Tutorial is loading... 662 663 **Solution** 664 665 ``` 666 #include <bits/stdc++.h> 667 668 using namespace std; 669 670 typedef long long int LL; 671 672 #define st first 673 #define nd second 674 #define PII pair <int, int> 675 676 const int N = 60; 677 const int MX = 1e9 + 7; 678 679 struct state { 680 int sum_picked = 0; 681 int last_picked = 0, cur_picked = 0; 682 int iterator = 0; 683 vector <PII> lengths; 684 685 state(vector <PII> _lengths) { 686 lengths = _lengths; 687 } 688 689 /* operators for map comparisons */ 690 bool operator<(const state &s) const { 691 if(lengths != s.lengths) return lengths < s.lengths; 692 if(last_picked != s.last_picked) return last_picked < s.last_picked; 693 if(cur_picked != s.cur_picked) return cur_picked < s.cur_picked; 694 return iterator < s.iterator; 695 } 696 697 bool operator==(const state &s) const { 698 if(last_picked != s.last_picked) return false; 699 if(cur_picked != s.cur_picked) return false; 700 if(iterator != s.iterator) return false; 701 if(lengths != s.lengths) return false; 702 return true; 703 } 704 }; 705 706 int n; 707 vector <PII> cycles; 708 map <state, int> dp; 709 710 int sil[N], rv[N]; 711 int pre[N][N][N]; 712 713 int fast(int a, int b) { 714 int ret = 1; 715 while(b) { 716 if(b & 1) 717 ret = 1LL * ret * a % MX; 718 719 b >>= 1; 720 a = 1LL * a * a % MX; 721 } 722 723 return ret; 724 } 725 726 int newt(int a, int b) { 727 if(b < 0 || a < b) 728 return 0; 729 return 1LL * sil[a] * rv[b] % MX * rv[a - b] % MX; 730 } 731 732 PII get_ways(int a, int b) { 733 if(a == 0 && b == 0) 734 return {sil[n - 1], 0}; 735 736 int ret = 0, ret2 = 0; 737 int c = n - a - 1; 738 739 for(int t = 1; t + c <= n; ++t) { 740 ret = (ret + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - c - 1, b) % MX * sil[b] % MX * sil[a - b]) % MX; 741 ret2 = (ret2 + 1LL * newt(n - t, c) * sil[c] % MX * newt(n - t - c, b) % MX * sil[b] % MX * sil[a - b]) % MX; 742 } 743 744 return {ret, ret2}; 745 } 746 747 void precalc() { 748 sil[0] = 1; 749 for(int i = 1; i <= n; ++i) 750 sil[i] = 1LL * sil[i - 1] * i % MX; 751 752 rv[n] = fast(sil[n], MX - 2); 753 for(int i = n; i >= 1; --i) 754 rv[i - 1] = 1LL * rv[i] * i % MX; 755 756 for(int i = 0; i < n; ++i) 757 for(int j = 0; j <= i; ++j) { 758 if(i && j == 0) 759 continue; 760 761 auto [val, val2] = get_ways(i, j); 762 pre[i][j][0] = 1; 763 764 int res = 1, res2 = 1; 765 for(int k = 1; k <= n; ++k) { 766 res = 1LL * res * val % MX; 767 res2 = 1LL * res2 * val2 % MX; 768 pre[i][j][k] = (res + MX - res2) % MX; 769 } 770 } 771 } 772 773 void read() { 774 scanf("%d", &n); 775 precalc(); 776 777 vector <int> input(n); 778 for(auto &v: input) { 779 scanf("%d", &v); 780 v--; 781 } 782 783 vector <bool> vis(n); 784 vector <int> cycle_lengths; 785 786 for(int i = 0; i < n; ++i) { 787 if(vis[i]) 788 continue; 789 790 int cur = i; 791 int cycle_length = 0; 792 793 while(!vis[cur]) { 794 ++cycle_length; 795 vis[cur] = true; 796 cur = input[cur]; 797 } 798 799 cycle_lengths.push_back(cycle_length); 800 } 801 802 sort(cycle_lengths.begin(), cycle_lengths.end()); 803 for(auto v: cycle_lengths) { 804 if(cycles.size() && cycles.back().st == v) 805 cycles.back().nd++; 806 else 807 cycles.push_back({v, 1}); 808 } 809 } 810 811 int solve(state &cur) { 812 if(cur.sum_picked == n) 813 return 1; 814 815 if(dp.count(cur)) 816 return dp[cur]; 817 818 if(cur.iterator == (int)cur.lengths.size()) { 819 if(cur.cur_picked == 0) 820 return dp[cur] = 0; 821 822 state nxt = cur; 823 nxt.sum_picked += nxt.cur_picked; 824 nxt.last_picked = nxt.cur_picked; 825 nxt.cur_picked = 0; 826 nxt.iterator = 0; 827 return dp[cur] = solve(nxt); 828 } 829 830 state nxt = cur; 831 nxt.iterator++; 832 833 int ret = 0, tmp = 1; 834 auto [length, count] = cur.lengths[cur.iterator]; 835 836 for(int i = 0; i <= count; ++i) { 837 nxt.cur_picked = cur.cur_picked + i * length; 838 nxt.lengths[cur.iterator].nd = count - i; 839 ret = (ret + 1LL * solve(nxt) * tmp % MX * newt(count, i)) % MX; 840 tmp = 1LL * tmp * pre[cur.sum_picked][cur.last_picked][length] % MX; 841 } 842 843 return dp[cur] = ret; 844 } 845 846 int main() { 847 read(); 848 state start = state(cycles); 849 int ans = solve(start); 850 printf("%d\n", ans); 851 return 0; 852 } 853 ``` 854 855 [1466I - The Riddle of the Sphinx](/contest/1466/problem/I "Good Bye 2020") 856 857 * Authors: [gawry](/profile/gawry "Grandmaster gawry"), [Anadi](/profile/Anadi "International Grandmaster Anadi") 858 * Developer: [Anadi](/profile/Anadi "International Grandmaster Anadi") 859 * First solve: [fivedemands](/profile/fivedemands "International Grandmaster fivedemands") 860 861 **Tutorial** 862 863 Tutorial is loading... 864 865 **Solution** 866 867 ``` 868 #include <bits/stdc++.h> 869 870 using namespace std; 871 872 #define st first 873 #define nd second 874 875 int n, b; 876 877 void write(int i, string y){ 878 printf("%d ", i); 879 for(auto p: y) 880 printf("%c", p); 881 puts(""); 882 fflush(stdout); 883 } 884 885 bool ask(int i, string y){ 886 write(i, y); 887 string ans; 888 cin >> ans; 889 return ans == "yes"; 890 } 891 892 void solve(vector <int> cur, string pref){ 893 if(pref.size() == b){ 894 write(0, pref); 895 return; 896 } 897 898 stack <pair <int, string> > S; 899 S.push({0, pref}); 900 901 for(auto v: cur){ 902 while(S.size() > 1){ 903 auto prv = S.top().nd; 904 while(prv.size() < b) 905 prv.push_back('1'); 906 907 if(!ask(v, prv)) 908 break; 909 S.pop(); 910 } 911 912 if(S.top().nd.size() == b) 913 continue; 914 915 auto prv = S.top().nd; 916 prv.push_back('0'); 917 918 while(prv.size() < b) 919 prv.push_back('1'); 920 921 if(ask(v, prv)){ 922 prv = S.top().nd + "1"; 923 S.push({v, prv}); 924 } 925 else{ 926 prv = S.top().nd + "0"; 927 S.push({v, prv}); 928 } 929 } 930 931 vector <int> nxt; 932 string ans = S.top().nd; 933 934 while(S.size() > 1){ 935 auto p = S.top(); 936 S.pop(); 937 938 string tmp = ans; 939 while(tmp.size() < b) 940 tmp.push_back('1'); 941 942 if(ask(p.st, tmp)){ 943 nxt.clear(); 944 ans = p.nd; 945 } 946 947 nxt.push_back(p.st); 948 } 949 950 solve(nxt, ans); 951 } 952 953 int main(){ 954 scanf("%d %d", &n, &b); 955 vector <int> all_ids; 956 for(int i = 0; i < n; ++i) 957 all_ids.push_back(i + 1); 958 solve(all_ids, ""); 959 return 0; 960 } 961 ``` 962 963 I am really interested in solving this task using fewer queries or proving that $3 \cdot (n + b)$ is optimal. Does anyone have any idea how to answer these questions? 964 965 **UPD:** There are challenges added to some tasks.