codeforces-scrape

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

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.