codeforces-scrape

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

1370.md (7266B)


      1 Source: https://codeforces.com/blog/entry/79107
      2 
      3 [1370A - Maximum GCD](/contest/1370/problem/A "Codeforces Round 651 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 #include < bits/stdc++.h >
     13 using namespace std;
     14  
     15 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     16 #define endl "\n"
     17 #define int long long
     18 
     19 const int N = 1e5 + 5;
     20 
     21 int32_t main()
     22 {
     23 	IOS;
     24 	int t;
     25 	cin >> t;
     26 	while(t--)
     27 	{
     28 		int n;
     29 		cin >> n;
     30 		cout << n / 2 << endl;
     31 	}
     32 	return 0;
     33 }
     34 ```
     35 
     36 This problem was prepared by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Expert the_hyp0cr1t3")
     37 
     38 [1370B - GCD Compression](/contest/1370/problem/B "Codeforces Round 651 (Div. 2)")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Code**
     45 
     46 ```
     47 #include < bits/stdc++.h >
     48 using namespace std;
     49  
     50 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     51 #define endl "\n"
     52 #define int long long
     53 
     54 const int N = 2e5 + 5;
     55 
     56 int n;
     57 int a[N];
     58 
     59 int32_t main()
     60 {
     61 	IOS;
     62 	int t;
     63 	cin >> t;
     64 	while(t--)
     65 	{
     66 		cin >> n;
     67 		vector< int > even, odd;
     68 		for(int i = 1; i <= 2 * n; i++)
     69 		{
     70 			cin >> a[i];
     71 			if(a[i] % 2)
     72 				odd.push_back(i);
     73 			else
     74 				even.push_back(i);
     75 		}
     76 		vector< pair< int, int > > ans;
     77 		for(int i = 0; i + 1 < odd.size(); i += 2)
     78 			ans.push_back({odd[i], odd[i + 1]});
     79 		for(int i = 0; i + 1 < even.size(); i += 2)
     80 			ans.push_back({even[i], even[i + 1]});
     81 		for(int i = 0; i < n - 1; i++)
     82 			cout << ans[i].first << " " << ans[i].second << endl;
     83 	}
     84 	return 0;
     85 }
     86 ```
     87 
     88 This problem was prepared by [Ashishgup](/profile/Ashishgup "International Master Ashishgup") and [ridbit10](/profile/ridbit10 "Expert ridbit10")
     89 
     90 [1370C - Number Game](/contest/1370/problem/C "Codeforces Round 651 (Div. 2)")
     91 
     92 **Tutorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Code**
     97 
     98 ```
     99 #include< bits/stdc++.h >
    100 using namespace std;
    101 
    102 const int N = 50000;
    103 
    104 void player_1(){
    105 	cout << "Ashishgup" << endl;
    106 }
    107 
    108 void player_2(){
    109 	cout << "FastestFinger" << endl;
    110 }
    111 
    112 bool check_prime(int n){
    113 	for(int i = 2; i < min(N, n); i++)
    114 		if(n % i == 0)
    115 			return 0;
    116 	return 1;
    117 }
    118 
    119 int main(){
    120 	int tc;
    121 	cin >> tc;
    122 	while(tc--){
    123 		int n;
    124 		cin >> n;
    125 		bool lose = (n == 1);
    126 		if(n > 2 && n % 2 == 0){
    127 			if((n & (n — 1)) == 0)
    128 				lose = 1;
    129 			else if(n % 4 != 0 && check_prime(n / 2))
    130 				lose = 1;
    131 		}
    132 		if(lose)
    133 			player_2();
    134 		else player_1();
    135 	}
    136 }
    137 ```
    138 
    139 **Relevant Meme**
    140 
    141 ![ ](/predownloaded/39/39/393940bb7f6d81615f01986e2329f668a181beac.png)
    142 
    143 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger") and [Ashishgup](/profile/Ashishgup "International Master Ashishgup")
    144 
    145 [1370D - Odd-Even Subsequence](/contest/1370/problem/D "Codeforces Round 651 (Div. 2)")
    146 
    147 **Tutorial**
    148 
    149 Tutorial is loading...
    150 
    151 **Code**
    152 
    153 ```
    154 #include < bits/stdc++.h >
    155 using namespace std;
    156  
    157 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    158 #define endl "\n"
    159 #define int long long
    160 
    161 const int N = 2e5 + 5;
    162 
    163 int n, k;
    164 int a[N];
    165 
    166 bool check(int x, int cur)
    167 {
    168 	int ans = 0;
    169 	for(int i = 1; i <= n; i++)
    170 	{
    171 		if(!cur)
    172 		{
    173 			ans++;
    174 			cur ^= 1;
    175 		}
    176 		else
    177 		{
    178 			if(a[i] <= x)
    179 			{
    180 				ans++;
    181 				cur ^= 1;
    182 			}
    183 		}
    184 	}
    185 	return ans >= k;
    186 }
    187 
    188 int binsearch(int lo, int hi)
    189 {
    190 	while(lo < hi)
    191 	{
    192 		int mid = (lo + hi) / 2;
    193 		if(check(mid, 0) || check(mid, 1))
    194 			hi = mid;
    195 		else
    196 			lo = mid + 1;
    197 	}
    198 	return lo;
    199 }
    200 
    201 int32_t main()
    202 {
    203 	IOS;
    204 	cin >> n >> k;
    205 	for(int i = 1; i <= n; i++)
    206 		cin >> a[i];
    207 	int ans = binsearch(1, 1e9);
    208 	cout << ans;
    209 	return 0;
    210 }
    211 ```
    212 
    213 This problem was prepared by [Ashishgup](/profile/Ashishgup "International Master Ashishgup")
    214 
    215 [1370E - Binary Subsequence Rotation](/contest/1370/problem/E "Codeforces Round 651 (Div. 2)")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Code**
    222 
    223 ```
    224 #include < bits/stdc++.h >
    225 using namespace std;
    226  
    227 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    228 #define endl "\n"
    229 #define int long long
    230 
    231 const int N = 1e6 + 5;
    232 
    233 int n;
    234 string s, t;
    235 int a[N];
    236 
    237 int get(int x)
    238 {
    239 	int cur = 0, mx = 0;
    240 	for(int i = 1; i <= n; i++)
    241 	{
    242 		cur += x * a[i];
    243 		mx = max(mx, cur);
    244 		if(cur < 0)
    245 			cur = 0;
    246 	}
    247 	return mx;
    248 }
    249 
    250 int32_t main()
    251 {
    252 	IOS;
    253 	cin >> n >> s >> t;
    254 	int sum = 0;
    255 	for(int i = 1; i <= n; i++)
    256 	{
    257 		if(s[i - 1] != t[i - 1])
    258 		{
    259 			if(s[i - 1] == '1')
    260 				a[i] = -1;
    261 			else
    262 				a[i] = 1;
    263 		}
    264 		sum += a[i];
    265 	}
    266 	if(sum != 0)
    267 	{
    268 		cout << -1;
    269 		return 0;
    270 	}
    271 	int ans = max(get(1), get(-1));
    272 	cout << ans;
    273 	return 0;
    274 }
    275 ```
    276 
    277 This problem was prepared by [smartnj](/profile/smartnj "Candidate Master smartnj")
    278 
    279 [1370F2 - The Hidden Pair (Hard Version)](/contest/1370/problem/F2 "Codeforces Round 651 (Div. 2)")
    280 
    281 **Tutorial**
    282 
    283 Tutorial is loading...
    284 
    285 **Code**
    286 
    287 ```
    288 #include< bits/stdc++.h >
    289 using namespace std;
    290 
    291 const int N = 1001;
    292 
    293 vector< int > adj[N], depth(N), max_depth(N);
    294 
    295 int n, root, dist;
    296 
    297 void dfs(int i, int par){
    298 	max_depth[i] = depth[i];
    299 	for(int j : adj[i]){
    300 		if(j == par)
    301 			continue;
    302 		depth[j] = 1 + depth[i], dfs(j, i);
    303 		max_depth[i] = max(max_depth[i], max_depth[j]);
    304 	}
    305 }
    306 
    307 void find_nodes(int i, int par, int req_depth, vector< int > &nodes){
    308 	if(depth[i] == req_depth){
    309 		nodes.push_back(i);
    310 		return;
    311 	}
    312 	for(int j : adj[i])
    313 		if(j != par && max_depth[j] <= n / 2)
    314 			find_nodes(j, i, req_depth, nodes);
    315 }
    316 
    317 pair query(vector< int > nodes){
    318 	cout << "? " << nodes.size() << ' ';
    319 	for(int i : nodes)
    320 		cout << i << ' ';
    321 	cout << endl;
    322 	fflush(stdout);
    323 
    324 	int x, dist;
    325 	cin >> x >> dist;
    326 
    327 	return {x, dist};
    328 }
    329 
    330 int main(){
    331 	int t;
    332 	cin >> t;
    333 	while(t--){
    334 		cin >> n;
    335 
    336 		for(int i = 1; i <= n; i++)
    337 			adj[i].clear(), depth[i] = 0, max_depth[i] = 0;
    338 
    339 		for(int i = 1; i < n; i++){
    340 			int u, v;
    341 			cin >> u >> v;
    342 			adj[u].push_back(v);
    343 			adj[v].push_back(u);
    344 		}
    345 
    346 		vector< int > nodes;
    347 		for(int i = 1; i <= n; i++)
    348 			nodes.push_back(i);
    349 
    350 		pair< int, int > res = query(nodes);
    351 		root = res.first, dist = res.second;
    352 
    353 		dfs(root, 0);
    354 
    355 		int st = 0, en = n / 2, first_node = root;
    356 		while(st <= en){
    357 			int mid = st + en >> 1;
    358 
    359 			vector< int > node_set;
    360 			find_nodes(root, 0, mid, node_set);
    361 
    362 			if(node_set.empty())
    363 				en = mid — 1;
    364 			else{
    365 				pair< int, int > res = query(node_set);
    366 				if(res.second == dist)
    367 					first_node = res.first, st = mid + 1;
    368 				else en = mid — 1;
    369 			}
    370 		}
    371 		vector< int > candidate_second;
    372 		queue< pair< int, int > > q;
    373 		vector< int > vis(n + 1);
    374 		q.push({first_node, 0});
    375 		while(!q.empty()){
    376 			pair< int, int > node = q.front();
    377 			q.pop();
    378 			vis[node.first] = 1;
    379 			if(node.second == dist)
    380 				candidate_second.push_back(node.first);
    381 
    382 			for(int j : adj[node.first])
    383 				if(!vis[j])
    384 					vis[j] = 1, q.push({j, node.second + 1});
    385 		}
    386 		pair< int, int > second_node = query(candidate_second);
    387 		cout << "! " << first_node << ' ' << second_node.first << endl;
    388 
    389 		string correct;
    390 		cin >> correct;
    391 	}
    392 }
    393 ```
    394 
    395 **Relevant Memes**
    396 
    397 ![ ](/predownloaded/36/ef/36ef27fd3d8eeae4e3f463d091df361e797d3197.jpg)
    398 
    399 ![ ](/predownloaded/1b/e0/1be0cf271fbd08ae7e9315492d669eb042d8897c.jpg)
    400 
    401 ![ ](/predownloaded/38/66/38662625645b4ac7cc032334b76e7379867b1932.png)
    402 
    403 This problem was prepared by [FastestFinger](/profile/FastestFinger "Master FastestFinger") and [Ashishgup](/profile/Ashishgup "International Master Ashishgup")
    404 
    405 Meme credits: [ridbit10](/profile/ridbit10 "Expert ridbit10") and [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Expert the_hyp0cr1t3") and [FastestFinger](/profile/FastestFinger "Master FastestFinger")