codeforces-scrape

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

2196.md (19346B)


      1 Source: https://codeforces.com/blog/entry/151052
      2 
      3 Thank you for participating! We hope you enjoyed the problems.
      4 
      5 [2197A - Friendly Numbers](/contest/2197/problem/A "Codeforces Round 1079 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 t = int(input())
     15 for tt in range(t):
     16     n = int(input())
     17     ans = 0
     18  
     19     def dig_sum(n):
     20         s = str(n)
     21         sum = 0
     22         for j in s:
     23             sum += ord(j) - ord('0')
     24         return sum
     25  
     26     for i in range(n, n + 200):
     27         if i - dig_sum(i) == n:
     28             ans += 1
     29     print(ans)
     30 ```
     31 
     32 [2197B - Array and Permutation](/contest/2197/problem/B "Codeforces Round 1079 (Div. 2)")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution**
     39 
     40 ```
     41 #include <bits/stdc++.h>
     42  
     43 #define all(a) a.begin(), a.end()
     44 #define rall(a) a.rbegin(), a.rend()
     45 #define len(a) int(a.size())
     46 using ll = long long;
     47 using ull = unsigned long long;
     48 using ld = long double;
     49  
     50 using namespace std;
     51  
     52 const int mod = 998244353;
     53  
     54 const int N = 1e6 + 228;
     55  
     56 pair<int, int> zero = {-1, N};
     57  
     58  
     59 void solve() {
     60     int n;
     61     cin >> n;
     62     map<int, int> pos;
     63     for (int i = 0; i < n; ++i) {
     64         int a;
     65         cin >> a;
     66         pos[a] = i;
     67     }
     68     int lst = -1;
     69     vector<int> b(n);
     70     for (int i = 0; i < n; ++i) cin >> b[i];
     71     for (int i = 0; i < n; ++i) {
     72         if (lst > pos[b[i]]) {
     73             cout << "NO\n";
     74             return;
     75         }
     76         lst = pos[b[i]];
     77     }
     78     cout << "YES\n";
     79 }
     80  
     81 int main(int argc, char* argv[]) {
     82     ios_base::sync_with_stdio(0);
     83     cin.tie(0);
     84  
     85     int t = 1;
     86     cin >> t;
     87     while (t--) solve();
     88 }
     89 ```
     90 
     91 [2196A - Game with a Fraction](/contest/2196/problem/A "Codeforces Round 1079 (Div. 1)")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 **Solution**
     98 
     99 ```
    100 #include<bits/stdc++.h>
    101 using namespace std;
    102  
    103 #define int long long
    104  
    105 void solve(){
    106 	int p, q;
    107 	cin >> p >> q;
    108 	if (p < q && min(p / 2, q / 3) >= q - p){
    109 		cout << "Bob\n";
    110 	}
    111 	else{
    112 		cout << "Alice\n";
    113 	}
    114 }
    115  
    116 signed main()
    117 {
    118 #ifdef FELIX
    119 	auto _clock_start = chrono::high_resolution_clock::now();
    120 #endif
    121 	ios_base::sync_with_stdio(false);
    122 	cin.tie(0);
    123 	cout.tie(0);
    124  
    125 	int t = 1;
    126 	cin >> t;
    127 	while(t--){
    128 		solve();
    129 	}
    130  
    131 #ifdef FELIX
    132 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    133 		chrono::high_resolution_clock::now()
    134 			- _clock_start).count() << "ms." << endl;
    135 #endif
    136 	return 0;
    137 }
    138 ```
    139 
    140 [2196B - Another Problem about Beautiful Pairs](/contest/2196/problem/B "Codeforces Round 1079 (Div. 1)")
    141 
    142 **Tutorial**
    143 
    144 Tutorial is loading...
    145 
    146 **Solution**
    147 
    148 ```
    149 #include <bits/stdc++.h>
    150  
    151 using namespace std;
    152  
    153 #define int long long
    154  
    155 const int SQ = 500;
    156  
    157 void solve(){
    158   int n;
    159   cin >> n;
    160   vector<int> a(n);
    161   for (int i = 0; i < n; i++){
    162     cin >> a[i];
    163   }
    164  
    165   int ans = 0;
    166  
    167   for (int i = 0; i < n; i++){
    168     if (a[i] >= SQ){
    169       for (int j = 1; i + a[i] * j < n; j++){
    170         if (a[i + a[i] * j] == j){
    171           ans++;
    172         }
    173       }
    174       for (int j = 1; i - a[i] * j >= 0; j++){
    175         if (a[i - a[i] * j] == j){
    176           ans++;
    177         }
    178       }
    179     }
    180     else{
    181       for (int j = 1; i + a[i] * j < n && j < SQ; j++){
    182         if (a[i + a[i] * j] == j){
    183           ans++;
    184         }
    185       }
    186     }
    187   }
    188  
    189   cout << ans << '\n';
    190 }
    191  
    192 signed main()
    193 {
    194 #ifdef FELIX
    195 	auto _clock_start = chrono::high_resolution_clock::now();
    196 #endif
    197 	ios_base::sync_with_stdio(false);
    198 	cin.tie(0);
    199 	cout.tie(0);
    200  
    201 	int t = 1;
    202 	cin >> t;
    203 	while(t--){
    204 		solve();
    205 	}
    206  
    207 #ifdef FELIX
    208 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    209 		chrono::high_resolution_clock::now()
    210 			- _clock_start).count() << "ms." << endl;
    211 #endif
    212 	return 0;
    213 }
    214 ```
    215 
    216 [2196C1 - Interactive Graph (Simple Version)](/contest/2196/problem/C1 "Codeforces Round 1079 (Div. 1)")
    217 
    218 **Tutorial**
    219 
    220 Tutorial is loading...
    221 
    222 **Solution**
    223 
    224 ```
    225 #include<bits/stdc++.h>
    226 using namespace std;
    227  
    228 #define int long long
    229  
    230 const int INF = 1'000'000'007;
    231  
    232 vector<int> ask(int k){
    233 	cout << "? " << k << endl;
    234 	int l;
    235 	cin >> l;
    236 	if (l == -1){
    237 		exit(0);
    238 	}
    239 	vector<int> res(l);
    240 	for (int i = 0; i < l; i++){
    241 		cin >> res[i];
    242 	}
    243 	return res;
    244 }
    245  
    246 void solve(){
    247 	int n;
    248 	cin >> n;
    249  
    250 	vector<pair<int, int>> edges;
    251  
    252 	for (int i = 0; i < n; i++){
    253 		int prev = -1;
    254 		while(1){
    255 			int l = 1, r = (1 << 30);
    256 			while(l <= r){
    257 				int m = l + (r - l) / 2;
    258 				auto path = ask(m);
    259 				if (!path.empty() && path[0] < i + 1){
    260 					l = m + 1;
    261 					continue;
    262 				}
    263 				if (path.empty() || path[0] > i + 1 || (path.size() > 1 && path[1] > prev)){
    264 					r = m - 1;
    265 				}
    266 				else{
    267 					l = m + 1;
    268 				}
    269 			}
    270  
    271 			auto path = ask(l);
    272 			if (path.size() > 1){
    273 				edges.emplace_back(path[0], path[1]);
    274 				prev = path[1];
    275 			}
    276 			else{
    277 				break;
    278 			}
    279 		}
    280 	}
    281  
    282 	cout << "! " << edges.size() << endl;
    283 	for (auto [u, v] : edges){
    284 		cout << u << ' ' << v << endl;
    285 	}
    286 }
    287  
    288 signed main()
    289 {
    290 #ifdef FELIX
    291 	auto _clock_start = chrono::high_resolution_clock::now();
    292 #endif
    293 	ios_base::sync_with_stdio(false);
    294 	cin.tie(0);
    295 	cout.tie(0);
    296  
    297 	int t = 1;
    298 	cin >> t;
    299 	while(t--){
    300 		solve();
    301 	}
    302  
    303 #ifdef FELIX
    304 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    305 		chrono::high_resolution_clock::now()
    306 			- _clock_start).count() << "ms." << endl;
    307 #endif
    308 	return 0;
    309 }
    310 ```
    311 
    312 [2196C2 - Interactive Graph (Hard Version)](/contest/2196/problem/C2 "Codeforces Round 1079 (Div. 1)")
    313 
    314 **Tutorial**
    315 
    316 Tutorial is loading...
    317 
    318 **Solution**
    319 
    320 ```
    321 #include<bits/stdc++.h>
    322  
    323 using namespace std;
    324  
    325 vector<int> ask(int k){
    326 	cout << "? " << k << endl;
    327 	int cnt;
    328 	cin >> cnt;
    329 	vector<int> res(cnt);
    330 	for (int i = 0; i < cnt; i++){
    331 		cin >> res[i];
    332 		res[i]--;
    333 	}
    334 	return res;
    335 }
    336  
    337 void solve(){
    338 	int n;
    339 	cin >> n;
    340  
    341 	int m = 0;
    342 	vector<vector<int>> g(n);
    343 	vector<int> cnt(n, -1);
    344  
    345 	function<void(int)> calc = [&](int v){
    346 		if (cnt[v] != -1){
    347 			return;
    348 		}
    349 		cnt[v] = 1;
    350 		for (int to : g[v]){
    351 			calc(to);
    352 			cnt[v] += cnt[to];
    353 		}
    354 	};
    355  
    356 	vector<int> prev = {0};
    357 	int k = 2;
    358  
    359 	while(1){
    360 		auto cur = ask(k);
    361 		if (cur.size() == 0){
    362 			break;
    363 		}
    364 		int com_pref = 0;
    365 		for (int i = 0; i < min(prev.size(), cur.size()); i++){
    366 			if (prev[i] != cur[i]){
    367 				break;
    368 			}
    369 			com_pref++;
    370 		}
    371 		if (prev.size() > com_pref){
    372 			calc(prev[com_pref]);
    373 		}
    374  
    375 		if (com_pref > 0){
    376 			g[cur[com_pref - 1]].push_back(cur[com_pref]);
    377 			m++;
    378 		}
    379 		if (cnt[cur[com_pref]] == -1){
    380 			k++;
    381 		}
    382 		else{
    383 			k += cnt[cur[com_pref]];
    384 		}
    385 		prev = cur;
    386 	}
    387  
    388 	cout << "! " << m << endl;
    389 	for (int i = 0; i < n; i++){
    390 		for (int to : g[i]){
    391 			cout << i + 1 << ' ' << to + 1 << endl;
    392 		}
    393 	}
    394 }
    395  
    396 signed main()
    397 {
    398 #ifdef FELIX
    399 	auto _clock_start = chrono::high_resolution_clock::now();
    400 #endif
    401 	ios_base::sync_with_stdio(false);
    402 	cin.tie(0);
    403 	cout.tie(0);
    404  
    405 	int tests = 1;
    406 	cin >> tests;
    407 	for (int test = 0; test < tests; test++){
    408 		solve();
    409 	}
    410 #ifdef FELIX
    411 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    412 		chrono::high_resolution_clock::now()
    413 			- _clock_start).count() << "ms." << endl;
    414 #endif
    415 	return 0;
    416 }
    417 ```
    418 
    419 [2196D - Double Bracket Sequence](/contest/2196/problem/D "Codeforces Round 1079 (Div. 1)")
    420 
    421 **Tutorial**
    422 
    423 Tutorial is loading...
    424 
    425 **Solution**
    426 
    427 ```
    428 #include<bits/stdc++.h>
    429 using namespace std;
    430  
    431 #define int long long
    432  
    433 const int INF = 1'000'000'007;
    434  
    435 void solve(){
    436 	int n;
    437 	cin >> n;
    438 	string s;
    439 	cin >> s;
    440  
    441 	vector<int> stay(n);
    442  
    443 	auto delete_cbs = [&](char open, char close){
    444 		vector<int> st;
    445 		for (int i = 0; i < n; i++){
    446 			if (s[i] == close){
    447 				if (!st.empty() && s[st.back()] == open){
    448 					st.pop_back();
    449 				}
    450 				else{
    451 					st.push_back(i);
    452 				}
    453 			}
    454 			else if (s[i] == open){
    455 				st.push_back(i);
    456 			}
    457 		}
    458 		for (int x : st){
    459 			stay[x] = 1;
    460 		}
    461 	};
    462  
    463 	delete_cbs('(', ')');
    464 	delete_cbs('[', ']');
    465  
    466 	int last_open = 0;
    467 	int cnt_open = 0, cnt_close = 0;
    468 	int ans = 1;
    469  
    470 	for (int i = 0; i < n; i++){
    471 		if (!stay[i]){
    472 			continue;
    473 		}
    474 		if (s[i] == '(' || s[i] == '['){
    475 			cnt_open++;
    476 			last_open = 1;
    477 		}
    478 		else{
    479 			cnt_close++;
    480 			if (last_open){
    481 				ans = 0;
    482 			}
    483 			last_open = 0;
    484 		}
    485 	}
    486 	if (cnt_open % 2 == 0 || cnt_close % 2 == 0){
    487 		ans = 0;
    488 	}
    489 	ans += (cnt_open + cnt_close) / 2;
    490 	cout << ans << '\n';
    491 }
    492  
    493 signed main()
    494 {
    495 #ifdef FELIX
    496 	auto _clock_start = chrono::high_resolution_clock::now();
    497 #endif
    498 	ios_base::sync_with_stdio(false);
    499 	cin.tie(0);
    500 	cout.tie(0);
    501  
    502 	int t = 1;
    503 	cin >> t;
    504 	while(t--){
    505 		solve();
    506 	}
    507  
    508 #ifdef FELIX
    509 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    510 		chrono::high_resolution_clock::now()
    511 			- _clock_start).count() << "ms." << endl;
    512 #endif
    513 	return 0;
    514 }
    515 ```
    516 
    517 [2196E1 - Fuzzy Concatenation (Easy Version)](/contest/2196/problem/E1 "Codeforces Round 1079 (Div. 1)")
    518 
    519 **Tutorial**
    520 
    521 Tutorial is loading...
    522 
    523 [2196E2 - Fuzzy Concatenation (Hard version)](/contest/2196/problem/E2 "Codeforces Round 1079 (Div. 1)")
    524 
    525 **Tutorial**
    526 
    527 Tutorial is loading...
    528 
    529 **Solution**
    530 
    531 ```
    532 #include <bits/stdc++.h>
    533  
    534 using namespace std;
    535  
    536 template <typename T>
    537 struct SparseTable{
    538 	int n, r;
    539 	vector<vector<T>> t;
    540 	void build(vector<T> &a) {
    541 		n = a.size();
    542 		r = 32 - __builtin_clz(n);
    543 		t.resize(r, vector<T>(n + 1));
    544 		for(int i = 1; i <= n; ++i) t[0][i] = a[i - 1];
    545 		for(int k = 1; k < r; ++k) {
    546 			for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
    547 				t[k][i] = f(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
    548 			}
    549 		}
    550 	}
    551  
    552 	T query(int l, int r) {
    553 		int k = 31 - __builtin_clz(r - l + 1);
    554 		return f(t[k][l], t[k][r - (1 << k) + 1]);
    555 	}
    556  
    557 	inline T f(T x, T y){
    558 		return min(x, y);
    559 	}
    560 };
    561  
    562 struct SuffixArray{
    563     int n;
    564     vector<int> sa;
    565     vector<int> lcp;
    566  
    567     vector<int> _s;
    568     vector<int> _inv_sa;
    569     SparseTable<int> _st_lcp;
    570  
    571     SuffixArray(){}
    572  
    573     void build(const string& s){
    574         _s.assign(s.size(), 0);
    575         for (int i = 0; i < s.size(); i++){
    576             _s[i] = s[i];
    577         }
    578         _build(_s);
    579         _build_lcp_array();
    580         _st_lcp.build(lcp);
    581     }
    582  
    583     void build(const vector<int>& s){
    584         _s.assign(s.size(), 0);
    585         for (int i = 0; i < s.size(); i++){
    586             _s[i] = s[i];
    587         }
    588         _build(_s);
    589         _build_lcp_array();
    590         _st_lcp.build(lcp);
    591     }
    592  
    593     void _build(const vector<int>& s){
    594         map<int, int> mp;
    595         for (int ch : s){
    596             mp[ch] = 0;
    597         }
    598         int cc = 1;
    599         for (auto& [key, val]: mp){
    600             val = cc++;
    601         }
    602  
    603         n = s.size() + 1;
    604         vector<int> c(n);
    605         sa.assign(n, 0);
    606  
    607         for (int i = 0; i < s.size(); i++){
    608             c[i] = mp[s[i]];
    609             sa[i] = i;
    610         }
    611         c[n - 1] = 0;
    612         sa[n - 1] = n - 1;
    613  
    614         for (int i = 1; (i >> 1) < n; i <<= 1){
    615             if (i != 1){
    616                 for (int j = 0; j < n; j++){
    617                     sa[j] = (sa[j] - (i >> 1) + n) % n;
    618                 }
    619             }
    620             vector<int> cnt(n);
    621             for (int j = 0; j < n; j++){
    622                 cnt[c[sa[j]]]++;
    623             }
    624             int su = 0;
    625             for (int j = 0; j < n; j++){
    626                 su += cnt[j];
    627                 cnt[j] = su - cnt[j];
    628             }
    629             vector<int> new_sa(n);
    630             for (int j = 0; j < n; j++){
    631                 new_sa[cnt[c[sa[j]]]++] = sa[j];
    632             }
    633             sa.swap(new_sa);
    634  
    635             if (i != 1){
    636                 vector<int> new_c(n);
    637                 new_c[sa[0]] = 0;
    638                 for (int j = 1; j < n; j++){
    639                     if (c[sa[j]] > c[sa[j - 1]] || c[(sa[j] + (i >> 1)) % n] > c[(sa[j - 1] + (i >> 1)) % n]){
    640                         new_c[sa[j]] = new_c[sa[j - 1]] + 1;
    641                     }
    642                     else{
    643                         new_c[sa[j]] = new_c[sa[j - 1]];
    644                     }
    645                 }
    646                 c.swap(new_c);
    647             }
    648         }
    649     }
    650  
    651     void _build_lcp_array(){
    652         lcp.assign(n - 1, 0);
    653         _inv_sa.assign(n, 0);
    654         for (int i = 0; i < n; i++){
    655             _inv_sa[sa[i]] = i;
    656         }
    657         for (int i = 0; i < n; i++){
    658             if (_inv_sa[i] == n - 1){
    659                 continue;
    660             }
    661             lcp[_inv_sa[i]] = 0;
    662             if (i > 0 && _inv_sa[i - 1] != n - 1){
    663                 lcp[_inv_sa[i]] = max(0, lcp[_inv_sa[i - 1]] - 1);
    664             }
    665  
    666             int len = min(n - 1 - i, n - 1 - sa[_inv_sa[i] + 1]);
    667             while (lcp[_inv_sa[i]] < len && _s[i + lcp[_inv_sa[i]]] == _s[sa[_inv_sa[i] + 1] + lcp[_inv_sa[i]]]){
    668                 lcp[_inv_sa[i]]++;
    669             }
    670         }
    671     }
    672  
    673     int get_lcp(int i, int j){
    674         assert(i != j);
    675         i = _inv_sa[i];
    676         j = _inv_sa[j];
    677         if (i > j){
    678             swap(i, j);
    679         }
    680         j--;
    681         return _st_lcp.query(i + 1, j + 1);
    682     }
    683 };
    684  
    685 void solve(){
    686     int n, m;
    687     cin >> n >> m;
    688     string s, t;
    689     cin >> s >> t;
    690  
    691     string all = s + "%" + t;
    692     SuffixArray suff_array;
    693     suff_array.build(all);
    694     all += '#';
    695  
    696     vector<int> from_s;
    697     for (int i = 0; i < n + m + 2; i++){
    698         if (suff_array.sa[i] < n){
    699             from_s.push_back(i);
    700         }
    701     }
    702  
    703     function<pair<int, int>(int, int, char, int)> compare_suff = [&](int start, int pos, char ch, int suff_num){
    704         if (suff_num == 0 || suff_num > n){
    705             return pair<int, int>{1, 0};
    706         }
    707         pos -= start;
    708         suff_num--;
    709         suff_num = suff_array.sa[from_s[suff_num]];
    710         
    711         int lcp1 = suff_array.get_lcp(suff_num, n + 1 + start);
    712         if (lcp1 < pos){
    713             char ch1 = all[suff_num + lcp1];
    714             char ch2 = all[n + 1 + start + lcp1];
    715             if (ch1 < ch2){
    716                 return pair<int, int>{1, lcp1};
    717             }
    718             else{
    719                 return pair<int, int>{-1, lcp1};
    720             }
    721         }
    722         else if (lcp1 > pos){
    723             char ch1 = all[suff_num + pos];
    724             char ch2;
    725             int len = pos;
    726             if (ch1 != ch){
    727                 ch2 = ch;
    728             }
    729             else{
    730                 len = lcp1;
    731                 ch1 = all[suff_num + lcp1];
    732                 ch2 = all[n + 1 + start + lcp1];
    733             }
    734             if (ch1 < ch2){
    735                 return pair<int, int>{1, len};
    736             }
    737             else{
    738                 return pair<int, int>{-1, len};
    739             }
    740         }
    741  
    742         char ch1 = all[suff_num + lcp1];
    743         char ch2 = ch;
    744         if (ch1 < ch2){
    745             return pair<int, int>{1, pos};
    746         }
    747         else if (ch1 > ch2){
    748             return pair<int, int>{-1, pos};
    749         }
    750  
    751         int lcp2 = suff_array.get_lcp(suff_num + lcp1 + 1, n + 1 + start + lcp1 + 1);
    752  
    753         ch1 = all[suff_num + lcp1 + 1 + lcp2];
    754         ch2 = all[n + 1 + start + lcp1 + 1 + lcp2];
    755  
    756         if (ch1 < ch2){
    757             return pair<int, int>{1, pos + 1 + lcp2};
    758         }
    759         else{
    760             return pair<int, int>{-1, pos + 1 + lcp2};
    761         }
    762     };
    763  
    764     function<int(int, int, char)> get_max_len = [&](int start, int pos, char ch){
    765         int suff_len = n + 1 + start;
    766  
    767         int l = 0, r = from_s.size();
    768         while(l <= r){
    769             int m = l + (r - l) / 2;
    770             if (compare_suff(start, pos, ch, m).first == -1){
    771                 r = m - 1;
    772             }
    773             else{
    774                 l = m + 1;
    775             }
    776         }
    777         int res = 0;
    778         res = max(res, compare_suff(start, pos, ch, l - 1).second);
    779         res = max(res, compare_suff(start, pos, ch, l).second);
    780         return res;
    781     };
    782  
    783     int ans = 0;
    784     int start = 0;
    785     int pred = -1;
    786  
    787     for (int i = 0; i < m; i++){
    788         int mx_len = 0;
    789         for (char ch = 'a'; ch <= 'z'; ch++){
    790             mx_len = max(mx_len, get_max_len(start, i, ch));
    791         }
    792         pred = max(pred, mx_len);
    793         if (mx_len < i - start + 1){
    794             ans++;
    795             start += pred;
    796             pred = -1;
    797             i = start - 1;
    798             continue;
    799         }
    800     }
    801     if (start != m){
    802         ans++;
    803     }
    804  
    805     cout << ans << '\n';
    806 }
    807  
    808 signed main()
    809 {
    810 #ifdef FELIX
    811 	auto _clock_start = chrono::high_resolution_clock::now();
    812 #endif
    813 	ios_base::sync_with_stdio(false);
    814 	cin.tie(0);
    815 	cout.tie(0);
    816  
    817 	int t = 1;
    818 	cin >> t;
    819 	while(t--){
    820 		solve();
    821 	}
    822  
    823 #ifdef FELIX
    824 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    825 		chrono::high_resolution_clock::now()
    826 			- _clock_start).count() << "ms." << endl;
    827 #endif
    828 	return 0;
    829 }
    830 ```
    831 
    832 [2196F - Indivisible](/contest/2196/problem/F "Codeforces Round 1079 (Div. 1)")
    833 
    834 **Tutorial**
    835 
    836 Tutorial is loading...
    837 
    838 **Solution**
    839 
    840 ```
    841 #include <bits/stdc++.h>
    842  
    843 #define int long long
    844 #define pb push_back
    845 #define all(x) x.begin(), (x).end()
    846 #define rall(x) x.rbegin(), (x).rend()
    847 using namespace std;
    848  
    849 vector<pair<int, int>> theSolve(int n, int m) {
    850   if (m == 1 || m == 2 || m == 4 || m == 6) {
    851     return {};
    852   }
    853   if (m == 12) {
    854     vector<pair<int, int>> e;
    855     for (int x = 1; x <= 6; x++) {
    856       for (int y = x + 1; y <= 6; y++) {
    857         if (max(x, y) >= 4) {
    858           e.pb({x, y});
    859         }
    860       }
    861     }
    862     return e;
    863   }
    864   if (n == 6 && m == 11) {
    865     return {{1, 2},
    866             {1, 3},
    867             {2, 4},
    868             {2, 5},
    869             {2, 6},
    870             {3, 4},
    871             {3, 5},
    872             {3, 6},
    873             {4, 5},
    874             {4, 6},
    875             {5, 6}};
    876   }
    877   if (n == 8 && m == 22) {
    878     vector<pair<int, int>> e;
    879     for (int v = 1; v <= 7; v++) {
    880       for (int u = v + 1; u <= 7; u++) {
    881         e.pb({v, u});
    882       }
    883     }
    884     e.pb({7, 8});
    885     return e;
    886   }
    887   if (n == 10 && m == 39) {
    888     vector<pair<int, int>> e;
    889     for (int x = 1; x <= n - 1; x++) {
    890       for (int y = x + 1; y <= n - 1; y++) {
    891         e.pb({x, y});
    892       }
    893     }
    894     for (int x = 1; x <= 3; x++) {
    895       e.pb({n, x});
    896     }
    897     return e;
    898   }
    899   vector<pair<int, int>> edges;
    900   if (n % 2 == 1) {
    901     while (m <= (n - 2) * (n - 3) / 2) {
    902       n -= 2;
    903     }
    904     int q = (2 * m) / n, r = (2 * m) % n;
    905     if (q % 2 == 0) {
    906       for (int v = 0; v < n; v++) {
    907         for (int p = 0; p < q / 2; p++) {
    908           int u = (v + 1 + p) % n;
    909           edges.pb({v + 1, u + 1});
    910         }
    911       }
    912       for (int v = 0; v < r / 2; v++) {
    913         edges.pb({v + 1, (v + n / 2) % n + 1});
    914       }
    915     } else {
    916       int d = (n - r) / 2;
    917       for (int v = 0; v < n; v++) {
    918         for (int p = 0; p < (q + 1) / 2; p++) {
    919           if (v % 2 == 0 && p == 0 && d) {
    920             d--;
    921             continue;
    922           }
    923           int u = (v + 1 + p) % n;
    924           edges.pb({v + 1, u + 1});
    925         }
    926       }
    927     }
    928     return edges;
    929   }
    930  
    931   int rest = n * (n - 1) / 2 - m;
    932   if (rest == 0 || rest == 1 || rest == 2 || rest == 4 || rest == 6) {
    933     return {};
    934   }
    935   if (m <= (n - 1) * (n - 2) / 2) {
    936     return theSolve(n - 1, m);
    937   }
    938   vector<pair<int, int>> inv_e = theSolve(n - 1, n * (n - 1) / 2 - m);
    939   for (auto &p : inv_e) {
    940     if (p.first > p.second) {
    941       swap(p.first, p.second);
    942     }
    943   }
    944   sort(all(inv_e));
    945   int i = 0;
    946   vector<pair<int, int>> e;
    947   for (int v = 1; v <= n; v++) {
    948     for (int u = v + 1; u <= n; u++) {
    949       if (i < (int) inv_e.size() && inv_e[i] == (pair<int, int>) {v, u}) {
    950         i++;
    951         continue;
    952       }
    953       e.pb({v, u});
    954     }
    955   }
    956   return e;
    957 }
    958  
    959 void solve() {
    960   int n, m;
    961   cin >> n >> m;
    962   vector<pair<int, int>> e = theSolve(n, m);
    963   if (e.empty()) {
    964     cout << "No\n";
    965   } else {
    966     cout << "Yes\n";
    967     for (auto &[a, b] : e) {
    968       cout << a << ' ' << b << '\n';
    969     }
    970   }
    971 }
    972  
    973 signed main() {
    974   ios::sync_with_stdio(false);
    975   cin.tie(nullptr);
    976   cout.tie(nullptr);
    977   int t;
    978   cin >> t;
    979   while (t--) {
    980     solve();
    981   }
    982 }
    983 ```
    984 
    985 For those who come after.