codeforces-scrape

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

1354.md (17028B)


      1 Source: https://codeforces.com/blog/entry/77593
      2 
      3 [1354A - Alarm Clock](/contest/1354/problem/A "Educational Codeforces Round 87 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (pikmike)**
     12 
     13 ```
     14 t = int(input())
     15 for _ in range(t):
     16 	a, b, c, d = map(int, input().split())
     17 	if b >= a:
     18 		print(b)
     19 		continue
     20 	if c <= d:
     21 		print(-1)
     22 		continue
     23 	a -= b
     24 	dif = c - d
     25 	print(b + (a + dif - 1) // dif * c)
     26 ```
     27 
     28 [1354B - Ternary String](/contest/1354/problem/B "Educational Codeforces Round 87 (Rated for Div. 2)")
     29 
     30 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     31 
     32 **Tutorial**
     33 
     34 Tutorial is loading...
     35 
     36 **Solution (BledDest)**
     37 
     38 ```
     39 #include<bits/stdc++.h>
     40 
     41 using namespace std;
     42 
     43 char buf[200043];
     44 
     45 int main()
     46 {
     47 	int t;
     48 	scanf("%d", &t);
     49 	for(int i = 0; i < t; i++)
     50 	{
     51 		scanf("%s", buf);
     52 		string s = buf;
     53 		int ans = int(1e9);
     54 		int n = s.size();
     55 		vector<pair<char, int> > c;
     56 		for(auto x : s)
     57 		{
     58 			if(c.empty() || c.back().first != x)
     59 				c.push_back(make_pair(x, 1));
     60 			else
     61 				c.back().second++;
     62 		}
     63 		int m = c.size();
     64 		for(int i = 1; i < m - 1; i++)
     65 			if(c[i - 1].first != c[i + 1].first)
     66 				ans = min(ans, c[i].second + 2);
     67 		if(ans > n)
     68 			ans = 0;
     69 		printf("%d\n", ans);
     70 	}
     71 }
     72 ```
     73 
     74 [1354C1 - Simple Polygon Embedding](/contest/1354/problem/C1 "Educational Codeforces Round 87 (Rated for Div. 2)")
     75 
     76 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 [1354C2 - Not So Simple Polygon Embedding](/contest/1354/problem/C2 "Educational Codeforces Round 87 (Rated for Div. 2)")
     83 
     84 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution (adedalic)**
     91 
     92 ```
     93 import kotlin.math.*
     94 
     95 fun main() {
     96     val PI = acos(-1.0)
     97     val T = readLine()!!.toInt()
     98     for (tc in 1..T) {
     99         val n = readLine()!!.toInt()
    100         var ans : Double
    101         if (n % 2 == 0) {
    102             ans = 1.0 / tan(PI / (2 * n))
    103         } else {
    104             ans = cos(PI / (4 * n)) / sin(PI / (2 * n))
    105         }
    106         println("%.9f".format(ans))
    107     }
    108 }
    109 ```
    110 
    111 [1354D - Multiset](/contest/1354/problem/D "Educational Codeforces Round 87 (Rated for Div. 2)")
    112 
    113 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    114 
    115 **Tutorial**
    116 
    117 Tutorial is loading...
    118 
    119 **Solution (BledDest)**
    120 
    121 ```
    122 #include<bits/stdc++.h>
    123 
    124 using namespace std;
    125 
    126 int n, q;
    127 vector<int> a, k;
    128 
    129 int count_le(int x)
    130 {
    131 	int cnt = 0;
    132 	for(auto y : a)
    133 		if(y <= x)
    134 			cnt++;
    135 	for(auto y : k)
    136 	{
    137 		if(y > 0 && y <= x)
    138 			cnt++;
    139 		if(y < 0 && abs(y) <= cnt)
    140 			cnt--;
    141 	}
    142 	return cnt;
    143 }
    144 
    145 int main()
    146 {
    147 	scanf("%d %d", &n, &q);
    148 	a.resize(n);
    149 	k.resize(q);
    150 	for(int i = 0; i < n; i++)
    151 		scanf("%d", &a[i]);
    152 	for(int i = 0; i < q; i++)
    153 		scanf("%d", &k[i]);
    154 	if(count_le(int(1e9)) == 0)
    155 	{
    156 		puts("0");
    157 		return 0;
    158 	}
    159 	int lf = 0;
    160 	int rg = int(1e6) + 1;
    161 	while(rg - lf > 1)
    162 	{
    163 		int mid = (lf + rg) / 2;
    164 		if(count_le(mid) > 0)
    165 			rg = mid;
    166 		else
    167 			lf = mid;
    168 	}
    169 	printf("%d\n", rg);
    170 	return 0;
    171 }
    172 ```
    173 
    174 [1354E - Graph Coloring](/contest/1354/problem/E "Educational Codeforces Round 87 (Rated for Div. 2)")
    175 
    176 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    177 
    178 **Tutorial**
    179 
    180 Tutorial is loading...
    181 
    182 **Solution (pikmike)**
    183 
    184 ```
    185 #include <bits/stdc++.h>
    186 
    187 using namespace std;
    188 
    189 #define x first
    190 #define y second
    191 #define mp make_pair
    192 #define pb push_back
    193 #define sqr(a) ((a) * (a))
    194 #define sz(a) int(a.size())
    195 #define all(a) a.begin(), a.end()
    196 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    197 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    198 
    199 typedef long long li;
    200 typedef long double ld;
    201 typedef pair<int, int> pt;
    202 
    203 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    204 	return out << "(" << a.x << ", " << a.y << ")";
    205 }
    206 
    207 template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    208 	out << "[";
    209 	forn(i, sz(v)) {
    210 		if(i) out << ", ";
    211 		out << v[i];
    212 	}
    213 	return out << "]";
    214 }
    215 
    216 mt19937 rnd(time(NULL));
    217 
    218 const int INF = int(1e9);
    219 const li INF64 = li(1e18);
    220 const int MOD = int(1e9) + 7;
    221 const ld EPS = 1e-9;
    222 const ld PI = acos(-1.0);
    223 
    224 const int N = 5000 + 7;
    225 
    226 int n, m;
    227 int a[3];
    228 vector<int> g[N];
    229 
    230 bool read () {
    231 	if (scanf("%d%d", &n, &m) != 2)
    232 		return false;
    233 	forn(i, 3) scanf("%d", &a[i]);
    234 	forn(i, n)
    235 		g[i].clear();
    236 	forn(i, m){
    237 		int v, u;
    238 		scanf("%d%d", &v, &u);
    239 		--v, --u;
    240 		g[v].pb(u);
    241 		g[u].pb(v);
    242 	}
    243 	return true;
    244 }
    245 
    246 int tot0, tot1;
    247 int clr[N];
    248 vector<vector<int>> vts[2];
    249 bool ok;
    250 
    251 void dfs(int v){
    252 	tot0 += clr[v] == 0;
    253 	tot1 += clr[v] == 1;
    254 	vts[clr[v]].back().pb(v);
    255 	for (auto u : g[v]){
    256 		if (clr[u] == -1){
    257 			clr[u] = clr[v] ^ 1;
    258 			dfs(u);
    259 		}
    260 		else if (clr[u] == clr[v]){
    261 			ok = false;
    262 		}
    263 	}
    264 }
    265 
    266 int dp[N][N];
    267 int res[N];
    268 
    269 void solve() {
    270 	vector<pt> siz;
    271 	memset(clr, -1, sizeof(clr));
    272 	vts[0].clear();
    273 	vts[1].clear();
    274 	forn(i, n) if (clr[i] == -1){
    275 		tot0 = tot1 = 0;
    276 		clr[i] = 0;
    277 		ok = true;
    278 		vts[0].pb(vector<int>());
    279 		vts[1].pb(vector<int>());
    280 		dfs(i);
    281 		if (!ok){
    282 			puts("NO");
    283 			return;
    284 		}
    285 		siz.pb(mp(tot0, tot1));
    286 	}
    287 	
    288 	memset(dp, -1, sizeof(dp));
    289 	dp[0][0] = 0;
    290 	forn(i, sz(siz)) forn(j, N) if (dp[i][j] != -1){
    291 		dp[i + 1][j + siz[i].x] = 0;
    292 		dp[i + 1][j + siz[i].y] = 1;
    293 	}
    294 	
    295 	if (dp[sz(siz)][a[1]] == -1){
    296 		puts("NO");
    297 		return;
    298 	}
    299 	
    300 	puts("YES");
    301 	memset(res, -1, sizeof(res));
    302 	int cur = a[1];
    303 	for (int i = sz(siz); i > 0; --i){
    304 		for (auto it : vts[dp[i][cur]][i - 1])
    305 			res[it] = 2;
    306 		cur -= sz(vts[dp[i][cur]][i - 1]);
    307 	}
    308 	
    309 	forn(i, n) if (res[i] == -1){
    310 		if (a[0] > 0){
    311 			res[i] = 1;
    312 			--a[0];
    313 		}
    314 		else{
    315 			res[i] = 3;
    316 			--a[2];
    317 		}
    318 	}
    319 	
    320 	forn(i, n) printf("%d", res[i]);
    321 	puts("");
    322 }
    323 
    324 int main() {
    325 #ifdef _DEBUG
    326 	freopen("input.txt", "r", stdin);
    327 //	freopen("output.txt", "w", stdout);
    328 	
    329 	int tt = clock();
    330 	
    331 #endif
    332 	
    333 	cerr.precision(15);
    334 	cout.precision(15);
    335 	cerr << fixed;
    336 	cout << fixed;
    337 
    338 	while(read()) {	
    339 		solve();
    340 		
    341 #ifdef _DEBUG
    342 	cerr << "TIME = " << clock() - tt << endl;
    343 	tt = clock();
    344 #endif
    345 
    346 	}
    347 }
    348 ```
    349 
    350 [1354F - Summoning Minions](/contest/1354/problem/F "Educational Codeforces Round 87 (Rated for Div. 2)")
    351 
    352 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    353 
    354 **Tutorial**
    355 
    356 Tutorial is loading...
    357 
    358 **Solution 1 (BledDest)**
    359 
    360 ```
    361 #include<bits/stdc++.h>
    362 
    363 using namespace std;
    364 
    365 const int N = 243;
    366 
    367 struct edge
    368 {
    369     int y, c, f, cost;
    370     edge() {};
    371     edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {};
    372 };
    373 
    374 int s, t, V;
    375 vector<int> g[N];
    376 vector<edge> e;
    377 
    378 void add(int x, int y, int c, int cost)
    379 {
    380     g[x].push_back(e.size());
    381     e.push_back(edge(y, c, 0, cost));
    382     g[y].push_back(e.size());
    383     e.push_back(edge(x, 0, 0, -cost));
    384 }
    385 
    386 int rem(int num)
    387 {
    388     return e[num].c - e[num].f;
    389 }   
    390 
    391 int p[N];
    392 int d[N];
    393 int pe[N];
    394 int inq[N];
    395 
    396 bool enlarge()
    397 {
    398     for(int i = 0; i < V; i++)
    399     {
    400         d[i] = int(1e9);
    401         p[i] = -1;
    402         pe[i] = -1;
    403         inq[i] = 0;
    404     }
    405     d[s] = 0;
    406     queue<int> q;
    407     q.push(s);
    408     inq[s] = 1;
    409     while(!q.empty())
    410     {
    411         int k = q.front();
    412         q.pop();
    413         inq[k] = 0;
    414         for(auto z : g[k])
    415         {
    416             if(!rem(z)) continue;
    417             if(d[e[z].y] > d[k] + e[z].cost)
    418             {
    419                 p[e[z].y] = k;
    420                 pe[e[z].y] = z;
    421                 d[e[z].y] = d[k] + e[z].cost;
    422                 if(!inq[e[z].y])
    423                 {
    424                     q.push(e[z].y);
    425                     inq[e[z].y] = 1;
    426                 }
    427             }
    428         }
    429     }
    430     if(p[t] == -1)
    431         return false;
    432     int cur = t;
    433     while(cur != s)
    434     {
    435         e[pe[cur]].f++;
    436         e[pe[cur] ^ 1].f--;
    437         cur = p[cur];
    438     }
    439     return true;
    440 }
    441 
    442 void process_test()
    443 {
    444 	int n, k;
    445 	cin >> n >> k;
    446 	vector<int> a(n), b(n);
    447 	for(int i = 0; i < n; i++)
    448 	{
    449 		cin >> a[i] >> b[i];
    450 	}
    451 	s = 2 * n;
    452 	t = 2 * n + 1;
    453 	V = 2 * n + 2;
    454 	for(int i = 0; i < n; i++)
    455 	{
    456 		add(s, i, 1, 0);
    457 		add(i + n, t, 1, 0);
    458 	}
    459 	for(int i = 0; i < n; i++)
    460 		for(int j = 0; j < n; j++)
    461 		{
    462 			if(j < k - 1)
    463 				add(i, j + n, 1, -(a[i] + b[i] * j));
    464 			else if(j == n - 1)
    465 				add(i, j + n, 1, -(a[i] + b[i] * (k - 1)));
    466 			else
    467 				add(i, j + n, 1, -(b[i] * (k - 1)));
    468 		}
    469 	for(int i = 0; i < n; i++)
    470 		enlarge();
    471 	vector<int> order(n);
    472 	for(int i = 0; i < n; i++)
    473 		for(auto x : g[i])
    474 		{
    475 			int to = e[x].y;
    476 			if(to >= n && to < 2 * n && e[x].f == 1)
    477 				order[to - n] = i;
    478 		}
    479 	cout << k + (n - k) * 2 << endl;
    480 	for(int i = 0; i < n; i++)
    481 	{
    482 		cout << order[i] + 1 << " ";
    483 		if(i >= k - 1 && i < n - 1)
    484 			cout << -(order[i] + 1) << " ";
    485 	}
    486 	cout << endl;
    487 	e.clear();
    488 	for(int i = 0; i < V; i++)
    489 		g[i].clear();
    490 }
    491 
    492 int main()
    493 {                       
    494     int t;
    495 	cin >> t;
    496 	for(int i = 0; i < t; i++)
    497 		process_test();
    498 }
    499 ```
    500 
    501 **Solution 2 (neal)**
    502 
    503 ```
    504 #include <algorithm>
    505 #include <array>
    506 #include <cassert>
    507 #include <iostream>
    508 #include <vector>
    509 using namespace std;
    510 
    511 template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
    512 template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
    513 
    514 void dbg_out() { cerr << endl; }
    515 template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
    516 
    517 #ifdef NEAL_DEBUG
    518 #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
    519 #else
    520 #define dbg(...)
    521 #endif
    522 
    523 template<typename T>
    524 void output_vector(const vector<T> &v, bool add_one = false, int start = -1, int end = -1) {
    525     if (start < 0) start = 0;
    526     if (end < 0) end = int(v.size());
    527 
    528     for (int i = start; i < end; i++)
    529         cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
    530 }
    531 
    532 const int64_t INF64 = int64_t(2e18) + 5;
    533 
    534 vector<int> assignment;
    535 
    536 template<typename T>
    537 int64_t hungarian(vector<vector<T>> costs) {
    538     int n = int(costs.size());
    539     int m = costs.empty() ? 0 : int(costs[0].size());
    540 
    541     if (n > m) {
    542         vector<vector<T>> new_costs(m, vector<T>(n));
    543 
    544         for (int i = 0; i < n; i++)
    545             for (int j = 0; j < m; j++)
    546                 new_costs[j][i] = costs[i][j];
    547 
    548         swap(costs, new_costs);
    549         swap(n, m);
    550     }
    551 
    552     vector<int64_t> u(n + 1), v(m + 1);
    553     vector<int> p(m + 1), way(m + 1);
    554 
    555     for (int i = 1; i <= n; i++) {
    556         vector<int64_t> min_v(m + 1, INF64);
    557         vector<bool> used(m + 1, false);
    558         p[0] = i;
    559         int j0 = 0;
    560 
    561         do {
    562             used[j0] = true;
    563             int i0 = p[j0], j1 = 0;
    564             int64_t delta = INF64;
    565 
    566             for (int j = 1; j <= m; j++)
    567                 if (!used[j]) {
    568                     int64_t cur = costs[i0 - 1][j - 1] - u[i0] - v[j];
    569 
    570                     if (cur < min_v[j]) {
    571                         min_v[j] = cur;
    572                         way[j] = j0;
    573                     }
    574 
    575                     if (min_v[j] < delta) {
    576                         delta = min_v[j];
    577                         j1 = j;
    578                     }
    579                 }
    580 
    581             for (int j = 0; j <= m; j++)
    582                 if (used[j]) {
    583                     u[p[j]] += delta;
    584                     v[j] -= delta;
    585                 } else {
    586                     min_v[j] -= delta;
    587                 }
    588 
    589             j0 = j1;
    590         } while (p[j0] != 0);
    591 
    592         do {
    593             int j1 = way[j0];
    594             p[j0] = p[j1];
    595             j0 = j1;
    596         } while (j0 != 0);
    597     }
    598 
    599     // Note that p[j] is the row assignment of column j (both 1-based). If p[j] = 0, the column is unassigned.
    600     assignment = p;
    601     return -v[0];
    602 }
    603 
    604 void run_case() {
    605     int N, K;
    606     cin >> N >> K;
    607     vector<int> A(N), B(N);
    608 
    609     for (int i = 0; i < N; i++)
    610         cin >> A[i] >> B[i];
    611 
    612     vector<vector<int>> costs(N, vector<int>(N, 0));
    613 
    614     for (int i = 0; i < N; i++)
    615         for (int position = 0; position < N; position++)
    616             if (position < K)
    617                 costs[i][position] = -(A[i] + position * B[i]);
    618             else
    619                 costs[i][position] = -((K - 1) * B[i]);
    620 
    621     int64_t score = -hungarian(costs);
    622     dbg(score);
    623     vector<int> solution;
    624 
    625     for (int k = 1; k < K; k++)
    626         solution.push_back(assignment[k]);
    627 
    628     for (int k = K + 1; k <= N; k++) {
    629         solution.push_back(assignment[k]);
    630         solution.push_back(-assignment[k]);
    631     }
    632 
    633     solution.push_back(assignment[K]);
    634     assert(int(solution.size()) == 2 * N - K);
    635     cout << solution.size() << '\n';
    636     output_vector(solution);
    637 }
    638 
    639 int main() {
    640     ios::sync_with_stdio(false);
    641 #ifndef NEAL_DEBUG
    642     cin.tie(nullptr);
    643 #endif
    644 
    645     int tests;
    646     cin >> tests;
    647 
    648     while (tests-- > 0)
    649         run_case();
    650 }
    651 ```
    652 
    653 **Solution 3 (pikmike)**
    654 
    655 ```
    656 #include <bits/stdc++.h>
    657  
    658 using namespace std;
    659  
    660 #define x first
    661 #define y second
    662 #define mp make_pair
    663 #define pb push_back
    664 #define sqr(a) ((a) * (a))
    665 #define sz(a) int(a.size())
    666 #define all(a) a.begin(), a.end()
    667 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    668 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    669  
    670 typedef long long li;
    671 typedef long double ld;
    672 typedef pair<int, int> pt;
    673  
    674 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    675 	return out << "(" << a.x << ", " << a.y << ")";
    676 }
    677  
    678 template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
    679 	out << "[";
    680 	forn(i, sz(v)) {
    681 		if(i) out << ", ";
    682 		out << v[i];
    683 	}
    684 	return out << "]";
    685 }
    686  
    687 mt19937 rnd(time(NULL));
    688  
    689 const int INF = int(1e9);
    690 const li INF64 = li(1e18);
    691 const int MOD = int(1e9) + 7;
    692 const ld EPS = 1e-9;
    693 const ld PI = acos(-1.0);
    694  
    695 const int N = 100;
    696  
    697 int n, k;
    698 pair<pt, int> a[N];
    699  
    700 bool read () {
    701 	if (scanf("%d%d", &n, &k) != 2)
    702 		return false;
    703 	forn(i, n){
    704 		scanf("%d%d", &a[i].x.x, &a[i].x.y);
    705 		a[i].y = i;
    706 	}
    707 	return true;
    708 }
    709  
    710 int dp[N][N];
    711 int p[N][N];
    712  
    713 void solve() {
    714 	sort(a, a + n, [](const pair<pt, int> &a, const pair<pt, int> &b){
    715 		if (a.x.y != b.x.y)
    716 			return a.x.y < b.x.y;
    717 		return a.x.x < b.x.x;
    718 	});
    719 	
    720 	forn(i, N) forn(j, N)
    721 		dp[i][j] = -INF;
    722 	dp[0][0] = 0;
    723 	forn(i, n) forn(j, N) if (dp[i][j] >= 0){
    724 		if (dp[i + 1][j] < dp[i][j] + a[i].x.y * (k - 1)){
    725 			dp[i + 1][j] = dp[i][j] + a[i].x.y * (k - 1);
    726 			p[i + 1][j] = j;
    727 		}
    728 		if (dp[i + 1][j + 1] < dp[i][j] + a[i].x.y * j + a[i].x.x){
    729 			dp[i + 1][j + 1] = dp[i][j] + a[i].x.y * j + a[i].x.x;
    730 			p[i + 1][j + 1] = j;
    731 		}
    732 	}
    733 	
    734 	vector<int> ans1, ans2;
    735 	int cur = k;
    736 	for (int i = n; i > 0; --i){
    737 		if (p[i][cur] == cur)
    738 			ans2.pb(a[i - 1].y + 1);
    739 		else
    740 			ans1.pb(a[i - 1].y + 1);
    741 		cur = p[i][cur];
    742 	}
    743 	
    744 	reverse(all(ans1));
    745 	reverse(all(ans2));
    746 	printf("%d\n", sz(ans1) + sz(ans2) * 2);
    747 	forn(i, sz(ans1) - 1)
    748 		printf("%d ", ans1[i]);
    749 	for (auto it : ans2)
    750 		printf("%d %d ", it, -it);
    751 	printf("%d\n", ans1.back());
    752 }
    753  
    754 int main() {
    755 #ifdef _DEBUG
    756 	freopen("input.txt", "r", stdin);
    757 //	freopen("output.txt", "w", stdout);
    758 	
    759 	int tt = clock();
    760 	
    761 #endif
    762 	
    763 	cerr.precision(15);
    764 	cout.precision(15);
    765 	cerr << fixed;
    766 	cout << fixed;
    767  
    768 	int tc;
    769 	scanf("%d", &tc);
    770 	while(tc--) {	
    771 		read();
    772 		solve();
    773 		
    774 #ifdef _DEBUG
    775 	cerr << "TIME = " << clock() - tt << endl;
    776 	tt = clock();
    777 #endif
    778  
    779 	}
    780 }
    781 ```
    782 
    783 [1354G - Find a Gift](/contest/1354/problem/G "Educational Codeforces Round 87 (Rated for Div. 2)")
    784 
    785 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    786 
    787 **Tutorial**
    788 
    789 Tutorial is loading...
    790 
    791 **Solution (adedalic)**
    792 
    793 ```
    794 #include<bits/stdc++.h>
    795 
    796 using namespace std;
    797 
    798 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    799 #define sz(a) int((a).size())
    800 
    801 #define x first
    802 #define y second
    803 
    804 typedef long long li;
    805 typedef pair<int, int> pt;
    806 
    807 const int MAG = 30;
    808 int lst;
    809 
    810 int n, k;
    811 
    812 inline bool read() {
    813 	if(!(cin >> n >> k))
    814 		return false;
    815 	return true;
    816 }
    817 
    818 int ask(int l1, int r1, int l2, int r2) {
    819 	assert(l1 < r1 && l2 < r2);
    820 	assert(r1 <= l2 || r2 <= l1);
    821 	
    822 	cout << "? " << r1 - l1 << " " << r2 - l2 << endl;
    823 	fore(i, l1, r1) {
    824 		if (i > l1) cout << " ";
    825 		cout << i + 1;
    826 	}
    827 	cout << endl;
    828 	fore(i, l2, r2) {
    829 		if (i > l2) cout << " ";
    830 		cout << i + 1;
    831 	}
    832 	cout << endl;
    833 	cout.flush();
    834 	
    835 	string resp;
    836 	cin >> resp;
    837 	
    838 	if (resp == "FIRST")
    839 		return -1;
    840 	if (resp == "SECOND")
    841 		return 1;
    842 	if (resp == "EQUAL")
    843 		return 0;
    844 	
    845 	exit(0);
    846 }
    847 
    848 inline void solve() {
    849 	//check first position
    850 	mt19937 rnd(lst ^ (n * 1024 + k));
    851 	for(int q = 0; q < MAG; q++) {
    852 		int cur = 1 + rnd() % (n - 1);
    853 		
    854 		int resp = ask(0, 1, cur, cur + 1);
    855 		if (resp == 1) {
    856 			cout << "! 1" << endl;
    857 			cout.flush();
    858 			return;
    859 		}
    860 	}
    861 	
    862 	int len = 1;
    863 	while(true) {
    864 		int cnt = min(len, n - len);
    865 		int resp = ask(0, cnt, len, len + cnt);
    866 		if (resp != 0) {
    867 			assert(resp == -1);
    868 			break;
    869 		}
    870 		len <<= 1;
    871 	}
    872 	
    873 	int lf = len, rg = min(2 * len, n);
    874 	while(rg - lf > 1) {
    875 		int mid = (lf + rg) >> 1;
    876 		int resp = ask(0, mid - lf, lf, mid);
    877 		assert(resp != 1);
    878 		
    879 		if (resp == 0)
    880 			lf = mid;
    881 		else
    882 			rg = mid;
    883 	}
    884 	cout << "! " << lf + 1 << endl;
    885 	cout.flush();
    886 	
    887 	lst = lf + 1;
    888 }
    889 
    890 int main() {
    891 	int tc;
    892 	cin >> tc;
    893 	
    894 	lst = tc;
    895 	while(tc--) {
    896 		assert(read());
    897 		solve();
    898 	}
    899 	return 0;
    900 }
    901 ```