codeforces-scrape

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

1593.md (8173B)


      1 Source: https://codeforces.com/blog/entry/96034
      2 
      3 [1593A - Elections](/contest/1593/problem/A "Codeforces Round 748 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int solveSingle(int best, int other1, int other2)
     19 {
     20 	return max(0, max(other1, other2) + 1 - best);
     21 }
     22 
     23 int main()
     24 {
     25 	int t;
     26 	cin >> t;
     27 
     28 	while (t--)
     29 	{
     30 		int a, b, c;
     31 		cin >> a >> b >> c;
     32 
     33 		cout << solveSingle(a, b, c) << ' ' << solveSingle(b, a, c) << ' ' << solveSingle(c, a, b) << '\n';
     34 	}
     35 
     36 	return 0;
     37 }
     38 ```
     39 
     40 [1593B - Make it Divisible by 25](/contest/1593/problem/B "Codeforces Round 748 (Div. 3)")
     41 
     42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include <bits/stdc++.h>
     52 
     53 using namespace std;
     54 
     55 const string subseqs[] = { "00", "25", "50", "75" };
     56 
     57 const int INF = 100;
     58 
     59 int solve(string& s, string& t)
     60 {
     61 	int sptr = s.length() - 1;
     62 
     63 	int ans = 0;
     64 	while (sptr >= 0 && s[sptr] != t[1])
     65 	{
     66 		sptr--;
     67 		ans++;
     68 	}
     69 
     70 	if (sptr < 0) return INF;
     71 
     72 	sptr--;
     73 
     74 	while (sptr >= 0 && s[sptr] != t[0])
     75 	{
     76 		sptr--;
     77 		ans++;
     78 	}
     79 
     80 	return sptr < 0 ? INF : ans;
     81 }
     82 
     83 int main()
     84 {
     85 	int t;
     86 	cin >> t;
     87 
     88 	while (t--)
     89 	{
     90 		string n;
     91 		cin >> n;
     92 		
     93 		int ans = INF;
     94 		for (auto e : subseqs)
     95 			ans = min(ans, solve(n, e));
     96 
     97 		cout << ans << '\n';
     98 	}
     99 
    100 	return 0;
    101 }
    102 ```
    103 
    104 [1593C - Save More Mice](/contest/1593/problem/C "Codeforces Round 748 (Div. 3)")
    105 
    106 Idea: ITMO student team
    107 
    108 **Tutorial**
    109 
    110 Tutorial is loading...
    111 
    112 **Solution**
    113 
    114 ```
    115 #include <bits/stdc++.h>
    116 
    117 using namespace std;
    118 
    119 int main()
    120 {
    121 	int t;
    122 	cin >> t;
    123 
    124 	while (t--)
    125 	{
    126 		int n, k;
    127 		cin >> n >> k;
    128 
    129 		vector<int> x(k);
    130 		for (int i = 0; i < k; i++) cin >> x[i];
    131 		sort(x.rbegin(), x.rend());
    132 
    133 		int cnt = 0;
    134 		long long sum = 0;
    135 
    136 		while (cnt < x.size() && sum + n - x[cnt] < n)
    137 		{
    138 			sum += n - x[cnt++];
    139 		}
    140 
    141 		cout << cnt << '\n';
    142 	}
    143 
    144 	return 0;
    145 }
    146 ```
    147 
    148 [1593D1 - All are Same](/contest/1593/problem/D1 "Codeforces Round 748 (Div. 3)")
    149 
    150 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 int main()
    164 {
    165 	int t;
    166 	cin >> t;
    167 
    168 	while (t--)
    169 	{
    170 		int n;
    171 		cin >> n;
    172 
    173 		vector<int> a(n);
    174 		for (int i = 0; i < n; i++) cin >> a[i];
    175 
    176 		bool inf = true;
    177 		int minval = a[0];
    178 
    179 		for (int i = 1; i < n; i++)
    180 		{
    181 			if (a[i] != a[0])
    182 			{
    183 				inf = false;
    184 				break;
    185 			}
    186 			minval = min(minval, a[i]);
    187 		}
    188 
    189 		if (inf)
    190 		{
    191 			cout << "-1\n";
    192 			continue;
    193 		}
    194 
    195 		sort(a.begin(), a.end());
    196 
    197 		int ans = 0;
    198 		for (int i = 0; i < n; i++)
    199 			ans = gcd(ans, a[i] - minval);
    200 		cout << ans << '\n';
    201 	}
    202 
    203 	return 0;
    204 }
    205 ```
    206 
    207 [1593D2 - Half of Same](/contest/1593/problem/D2 "Codeforces Round 748 (Div. 3)")
    208 
    209 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 #define forn(i, n) for (int i = 0; i < int(n); i++)
    223 
    224 set<int> divs(int n) {  
    225     set<int> d;
    226     for (int dd = 1; dd * dd <= n; dd++)
    227         if (n % dd == 0) {
    228             d.insert(n / dd);
    229             d.insert(dd);
    230         }
    231     return d;
    232 }
    233 
    234 int main() {
    235     int t;
    236     cin >> t;
    237     forn(tt, t) {
    238         int n;
    239         cin >> n;
    240         vector<int> a(n);
    241         forn(i, n)
    242             cin >> a[i];
    243         int k = -1;
    244 
    245         forn(i, n) {
    246             int minv = a[i];
    247             int same = 0;
    248             vector<int> d;
    249             forn(j, n) {
    250                 if (a[j] == minv)
    251                     same++;
    252                 else if (a[j] > minv)
    253                     d.push_back(a[j] - minv);
    254             }
    255             if (same >= n / 2) {
    256                 k = INT_MAX;
    257                 continue;
    258             }
    259             map<int,int> div_counts;
    260             for (int di: d)
    261                 for (int dd: divs(di))
    262                     div_counts[dd]++;
    263             for (auto p: div_counts)
    264                 if (p.second >= n / 2 - same)
    265                     k = max(k, p.first);
    266         }
    267 
    268         cout << (k == INT_MAX ? -1 : k) << endl;
    269     }
    270 }
    271 ```
    272 
    273 [1593E - Gardener and Tree](/contest/1593/problem/E "Codeforces Round 748 (Div. 3)")
    274 
    275 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    276 
    277 **Tutorial**
    278 
    279 Tutorial is loading...
    280 
    281 **Solution**
    282 
    283 ```
    284 #include <bits/stdc++.h>
    285 
    286 using namespace std;
    287 
    288 int main()
    289 {
    290 	int t;
    291 	cin >> t;
    292 
    293 	while (t--)
    294 	{
    295 		int n, k;
    296 		cin >> n >> k;
    297 
    298 		vector<vector<int>> g(n, vector<int>());
    299 		vector<int> rem(n, 0);
    300 		vector<int> layer(n, 0);
    301 
    302 		for (int i = 1; i < n; i++)
    303 		{
    304 			int x, y;
    305 			cin >> x >> y;
    306 			x--;
    307 			y--;
    308 			g[x].push_back(y);
    309 			g[y].push_back(x);
    310 			rem[x]++;
    311 			rem[y]++;
    312 		}
    313 
    314 		queue<int> q;
    315 		for (int i = 0; i < n; i++)
    316 			if (rem[i] == 1)
    317 			{
    318 				q.push(i);
    319 				layer[i] = 1;
    320 			}
    321 
    322 		while (!q.empty())
    323 		{
    324 			int u = q.front();
    325 			q.pop();
    326 
    327 			for (int v : g[u])
    328 			{
    329 				if (rem[v] != 1)
    330 				{
    331 					rem[v]--;
    332 					if (rem[v] == 1)
    333 					{
    334 						layer[v] = layer[u] + 1;
    335 						q.push(v);
    336 					}
    337 				}
    338 			}
    339 		}
    340 
    341 		int ans = 0;
    342 		for (int i = 0; i < n; i++)
    343 			if (layer[i] > k)
    344 				ans++;
    345 
    346 		cout << ans << '\n';
    347 	}
    348 
    349 	return 0;
    350 }
    351 ```
    352 
    353 [1593F - Red-Black Number](/contest/1593/problem/F "Codeforces Round 748 (Div. 3)")
    354 
    355 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    356 
    357 **Tutorial**
    358 
    359 Tutorial is loading...
    360 
    361 **Solution**
    362 
    363 ```
    364 #include <bits/stdc++.h>
    365 
    366 using namespace std;
    367 
    368 const int MAX_N = 64;
    369 
    370 bool dp[MAX_N][MAX_N][MAX_N][MAX_N]; // (taken, red, mod A, mod B) -> may be
    371 pair<bool, int> sert[MAX_N][MAX_N][MAX_N][MAX_N]; // the same -> (true (red) | false(black), prev red/black)
    372 
    373 int main()
    374 {
    375 	int t;
    376 	cin >> t;
    377 
    378 	while (t--)
    379 	{
    380 		int n, a, b;
    381 		string x;
    382 		cin >> n >> a >> b >> x;
    383 
    384 		for (int i = 0; i <= n; i++)
    385 			for (int j = 0; j <= n; j++)
    386 				for (int k = 0; k < a; k++)
    387 					for (int l = 0; l < b; l++)
    388 						dp[i][j][k][l] = false;
    389 
    390 		dp[0][0][0][0] = true;
    391 
    392 		for(int taken = 0; taken < n; taken++)
    393 			for(int red = 0; red <= taken; red++)
    394 				for(int remA = 0; remA < a; remA++)
    395 					for(int remB = 0; remB < b; remB++)
    396 						if (dp[taken][red][remA][remB])
    397 						{
    398 							// red transition
    399 							dp[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = true;
    400 							sert[taken + 1][red + 1][(remA * 10 + (x[taken] - '0')) % a][remB] = { true, remA };
    401 
    402 							// black transition
    403 							dp[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = true;
    404 							sert[taken + 1][red][remA][(remB * 10 + (x[taken] - '0')) % b] = { false, remB };
    405 						}
    406 
    407 		int bestRed = 0;
    408 
    409 		for (int red = 1; red < n; red++)
    410 			if (dp[n][red][0][0] && abs(red - (n - red)) < abs(bestRed - (n - bestRed)))
    411 				bestRed = red;
    412 
    413 		if (bestRed == 0)
    414 		{
    415 			cout << "-1\n";
    416 		}
    417 		else
    418 		{
    419 			int taken = n;
    420 			int red = bestRed;
    421 			int remA = 0;
    422 			int remB = 0;
    423 			string ans = "";
    424 			
    425 			while (taken > 0)
    426 			{
    427 				auto way = sert[taken][red][remA][remB];
    428 				if (way.first)
    429 				{
    430 					red--;
    431 					remA = way.second;
    432 					ans.push_back('R');
    433 				}
    434 				else
    435 				{
    436 					remB = way.second;
    437 					ans.push_back('B');
    438 				}
    439 				taken--;
    440 			}
    441 
    442 			reverse(ans.begin(), ans.end());
    443 			cout << ans << '\n';
    444 		}
    445 	}
    446 
    447 	return 0;
    448 }
    449 ```
    450 
    451 [1593G - Changing Brackets](/contest/1593/problem/G "Codeforces Round 748 (Div. 3)")
    452 
    453 Idea: [nastya_ka](/profile/nastya_ka "Specialist nastya_ka")
    454 
    455 **Tutorial**
    456 
    457 Tutorial is loading...
    458 
    459 **Solution**
    460 
    461 ```
    462 #include <bits/stdc++.h>
    463 
    464 using namespace std;
    465 
    466 const int MAX_N = 1'000'000;
    467 
    468 int psumOdd[MAX_N + 1];
    469 int psumEven[MAX_N + 1];
    470 
    471 void solve()
    472 {
    473 	string s;
    474 	int q;
    475 	cin >> s >> q;
    476 	int n = s.length();
    477 
    478 	psumOdd[0] = psumEven[0] = 0;
    479 	for (int i = 0; i < n; i++)
    480 	{
    481 		psumOdd[i + 1] = psumOdd[i];
    482 		psumEven[i + 1] = psumEven[i];
    483 
    484 		if (s[i] == '[' || s[i] == ']')
    485 		{
    486 			if (i & 1)
    487 				psumOdd[i + 1]++;
    488 			else
    489 				psumEven[i + 1]++;
    490 		}
    491 	}
    492 
    493 	while (q--)
    494 	{
    495 		int l, r;
    496 		cin >> l >> r;
    497 		l--;
    498 		int odd = psumOdd[r] - psumOdd[l];
    499 		int even = psumEven[r] - psumEven[l];
    500 		cout << abs(odd - even) << '\n';
    501 	}
    502 }
    503 
    504 int main()
    505 {
    506 	int t;
    507 	cin >> t;
    508 	while (t--)
    509 		solve();
    510 	return 0;
    511 }
    512 ```