codeforces-scrape

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

1551.md (7537B)


      1 Source: https://codeforces.com/blog/entry/93149
      2 
      3 Ideas: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov").
      4 
      5 [1551A - Polycarp and Coins](/contest/1551/problem/A "Codeforces Round 734 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 for i in range(0, int(input())):
     15     n = int(input())
     16     c1 = n // 3;
     17     c2 = c1;
     18     if n % 3 == 1:
     19         c1 += 1
     20     elif n % 3 == 2:
     21         c2 += 1
     22     print(c1, c2)
     23 ```
     24 
     25 [1551B1 - Wonderful Coloring - 1](/contest/1551/problem/B1 "Codeforces Round 734 (Div. 3)")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution**
     32 
     33 ```
     34 #include <bits/stdc++.h>
     35 
     36 using namespace std;
     37 
     38 const int L = 26;
     39 int cnt[L];
     40 
     41 int main()
     42 {
     43 	int t;
     44 	cin >> t;
     45 	while (t--)
     46 	{
     47 		string s;
     48 		cin >> s;
     49 		memset(cnt, 0, sizeof(cnt));
     50 		for (auto c : s) cnt[c - 'a']++;
     51 		int cnt1 = 0;
     52 		int cnt2 = 0;
     53 		for (int i = 0; i < L; i++)
     54 			if (cnt[i] == 1)
     55 				cnt1++;
     56 			else if (cnt[i] > 0)
     57 				cnt2++;
     58 		cout << (cnt2 + cnt1 / 2) << endl;
     59 	}
     60 	return 0;
     61 }
     62 ```
     63 
     64 [1551B2 - Wonderful Coloring - 2](/contest/1551/problem/B2 "Codeforces Round 734 (Div. 3)")
     65 
     66 **Tutorial**
     67 
     68 Tutorial is loading...
     69 
     70 **Solution**
     71 
     72 ```
     73 #include <bits/stdc++.h>
     74 using namespace std;
     75 const int MAX_N = 200 * 1000 + 13;
     76 
     77 int ans[MAX_N];
     78 map<int, vector<int>> indices;
     79 
     80 int main()
     81 {
     82 	int t;
     83 	cin >> t;
     84 	while (t--)
     85 	{
     86 		int n, k;
     87 		cin >> n >> k;
     88 		indices.clear();
     89 		memset(ans, 0, n * sizeof(ans[0]));
     90 		for (int i = 0; i < n; i++)
     91 		{
     92 			int x;
     93 			cin >> x;
     94 			if (indices[x].size() < k)
     95 				indices[x].push_back(i);
     96 		}
     97 		int m = 0;
     98 		for (auto e : indices) m += e.second.size();
     99 		m -= m % k;
    100 		int color = 0;
    101 		for (auto e : indices)
    102 			for (auto i : e.second)
    103 			{
    104 				ans[i] = ++color;
    105 				color %= k;
    106 				if (--m == 0) goto _output;
    107 			}
    108 	_output:
    109 		for (int i = 0; i < n; i++)
    110 			cout << ans[i] << ' ';
    111 		cout << '\n';
    112 	}
    113 
    114 	return 0;
    115 }
    116 ```
    117 
    118 [1551C - Interesting Story](/contest/1551/problem/C "Codeforces Round 734 (Div. 3)")
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Solution**
    125 
    126 ```
    127 #include <bits/stdc++.h>
    128 using namespace std;
    129 const int MAX_N = 2 * 100 * 1000 + 13;
    130 const int L = 26;
    131 
    132 vector<int> balance[L];
    133 
    134 int main()
    135 {
    136 	int t;
    137 	cin >> t;
    138 	while (t--)
    139 	{
    140 		int n;
    141 		cin >> n;
    142 		for (int i = 0; i < L; i++)
    143 			balance[i].clear();
    144 		for (int i = 1; i <= n; i++)
    145 		{
    146 			string s;
    147 			cin >> s;
    148 			int initBalance = -(int)s.length();
    149 			for (int j = 0; j < L; j++)
    150 				balance[j].push_back(initBalance);
    151 			for (auto c : s)
    152 				balance[c - 'a'].back() += 2;
    153 		}
    154 		int bestCount = 0;
    155 		int bestLetter = 0;
    156 		for (int i = 0; i < L; i++)
    157 		{
    158 			auto& b = balance[i];
    159 			sort(b.begin(), b.end());
    160 			reverse(b.begin(), b.end());
    161 			if (b[0] <= 0) continue;
    162 			int sumBalance = b[0];
    163 			int j = 1;
    164 			for (; j < n && sumBalance > 0; j++)
    165 				sumBalance += b[j];
    166 			if (sumBalance <= 0) j--;
    167 			if (j > bestCount)
    168 			{
    169 				bestCount = j;
    170 				bestLetter = i;
    171 			}
    172 		}
    173 
    174 		cout << bestCount << endl;
    175 	}
    176 	return 0;
    177 }
    178 ```
    179 
    180 [1551D1 - Domino (easy version)](/contest/1551/problem/D1 "Codeforces Round 734 (Div. 3)")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 using namespace std;
    191 
    192 int main()
    193 {
    194 	int t;
    195 	cin >> t;
    196 	while (t--)
    197 	{
    198 		int n, m, kh;
    199 		cin >> n >> m >> kh;
    200 		int kv = n * m / 2 - kh;
    201 		if (n & 1)
    202 		{
    203 			kh -= m / 2;
    204 			if (kh < 0)
    205 			{
    206 				cout << "NO\n";
    207 				continue;
    208 			}
    209 		}
    210 		else if (m & 1)
    211 		{
    212 			kv -= n / 2;
    213 			if (kv < 0)
    214 			{
    215 				cout << "NO\n";
    216 				continue;
    217 			}
    218 		}
    219 		if ((kh & 1) || (kv & 1))
    220 		{
    221 			cout << "NO\n";
    222 			continue;
    223 		}
    224 		cout << "YES\n";
    225 	}
    226 	return 0;
    227 }
    228 ```
    229 
    230 [1551D2 - Domino (hard version)](/contest/1551/problem/D2 "Codeforces Round 734 (Div. 3)")
    231 
    232 **Tutorial**
    233 
    234 Tutorial is loading...
    235 
    236 **Solution**
    237 
    238 ```
    239 #include <bits/stdc++.h>
    240 using namespace std;
    241 
    242 char field[128][128];
    243 
    244 int main()
    245 {
    246 	int t;
    247 	cin >> t;
    248 	while (t--)
    249 	{
    250 		int n, m, kh;
    251 		cin >> n >> m >> kh;
    252 		int kv = n * m / 2 - kh;
    253 		if (n & 1)
    254 		{
    255 			kh -= m / 2;
    256 			if (kh < 0)
    257 			{
    258 				cout << "NO\n";
    259 				continue;
    260 			}
    261 
    262 			for (int i = 0; i < m / 2; i++)
    263 				field[n - 1][i * 2] = field[n - 1][i * 2 + 1] = ((i & 1) ? 'x' : 'y');
    264 		}
    265 		else if (m & 1)
    266 		{
    267 			kv -= n / 2;
    268 			if (kv < 0)
    269 			{
    270 				cout << "NO\n";
    271 				continue;
    272 			}
    273 
    274 			for (int i = 0; i < n / 2; i++)
    275 				field[i * 2][m - 1] = field[i * 2 + 1][m - 1] = ((i & 1) ? 'x' : 'y');
    276 		}
    277 		if ((kh & 1) || (kv & 1))
    278 		{
    279 			cout << "NO\n";
    280 			continue;
    281 		}
    282 		for(int i = 0; i < n / 2; i++)
    283 			for (int j = 0; j < m / 2; j++)
    284 			{
    285 				if (kh)
    286 				{
    287 					kh -= 2;
    288 					field[2 * i][2 * j] = field[2 * i][2 * j + 1] = (((i + j) & 1) ? 'a' : 'b');
    289 					field[2 * i + 1][2 * j] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
    290 				}
    291 				else
    292 				{
    293 					field[2 * i][2 * j] = field[2 * i + 1][2 * j] = (((i + j) & 1) ? 'a' : 'b');
    294 					field[2 * i][2 * j + 1] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
    295 				}
    296 			}
    297 
    298 		cout << "YES\n";
    299 		for (int i = 0; i < n; i++)
    300 		{
    301 			field[i][m] = 0;
    302 			cout << field[i] << '\n';
    303 		}
    304 	}
    305 	return 0;
    306 }
    307 ```
    308 
    309 [1551E - Fixed Points](/contest/1551/problem/E "Codeforces Round 734 (Div. 3)")
    310 
    311 **Tutorial**
    312 
    313 Tutorial is loading...
    314 
    315 **Solution**
    316 
    317 ```
    318 #include <bits/stdc++.h>
    319 using namespace std;
    320 const int MAX_N = 6000;
    321 
    322 int dp[MAX_N][MAX_N];
    323 int a[MAX_N];
    324 
    325 int main()
    326 {
    327 	int t;
    328 	cin >> t;
    329 	while (t--)
    330 	{
    331 		int n, k;
    332 		cin >> n >> k;
    333 		for (int i = 1; i <= n; i++) cin >> a[i];
    334 		for (int i = 0; i <= n; i++)
    335 			for (int j = 0; j <= i; j++)
    336 				dp[i][j] = 0;
    337 		for(int i = 0; i < n; i++)
    338 			for (int j = 0; j <= i; j++)
    339 			{
    340 				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
    341 				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((a[i + 1] == j + 1) ? 1 : 0));
    342 			}
    343 		int ans = -1;
    344 		for(int i = n; i >= 0; i--)
    345 			if (dp[n][i] >= k)
    346 			{
    347 				ans = n - i;
    348 				break;
    349 			}
    350 		cout << ans << '\n';
    351 	}
    352 	return 0;
    353 }
    354 ```
    355 
    356 [1551F - Equidistant Vertices](/contest/1551/problem/F "Codeforces Round 734 (Div. 3)")
    357 
    358 **Tutorial**
    359 
    360 Tutorial is loading...
    361 
    362 **Solution**
    363 
    364 ```
    365 #include <bits/stdc++.h>
    366 using namespace std;
    367 const int MAX_N = 128;
    368 
    369 typedef long long ll;
    370 const ll mod = 1000 * 1000 * 1000 + 7;
    371 
    372 ll add(ll x, ll y) { return (x + y) % mod; }
    373 ll mul(ll x, ll y) { return x * y % mod; }
    374 
    375 vector<int> g[MAX_N];
    376 bool used[MAX_N];
    377 int cnt[MAX_N];
    378 ll dp[MAX_N][MAX_N];
    379 
    380 ll rundp(int m, int k)
    381 {
    382 	for (int i = 0; i <= m; i++)
    383 		for (int j = 0; j <= k; j++)
    384 			dp[i][j] = 0;
    385 	dp[0][0] = 1;
    386 	for (int i = 0; i < m; i++)
    387 		for (int j = 0; j <= k; j++)
    388 		{
    389 			dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);
    390 			dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], cnt[i]));
    391 		}
    392 	return dp[m][k];
    393 }
    394 
    395 void solve()
    396 {
    397 	int n, k;
    398 	cin >> n >> k;
    399 	for (int i = 0; i < n; i++)
    400 		g[i].clear();
    401 	for (int i = 1; i < n; i++)
    402 	{
    403 		int a, b;
    404 		cin >> a >> b;
    405 		g[--a].push_back(--b);
    406 		g[b].push_back(a);
    407 	}
    408 	if (k == 2)
    409 	{
    410 		cout << n * (n - 1LL) / 2 % mod << '\n';
    411 		return;
    412 	}
    413 	ll ans = 0;
    414 	for (int center = 0; center < n; center++)
    415 	{
    416 		memset(used, 0, n);
    417 		used[center] = true;
    418 
    419 		vector<pair<int, int>> layer;
    420 		int m = g[center].size();
    421 		for (int i = 0; i < m; i++)
    422 		{
    423 			int y = g[center][i];
    424 			layer.emplace_back(y, i);
    425 			cnt[i] = 1;
    426 			used[y] = true;
    427 		}
    428 		while (!layer.empty())
    429 		{
    430 			ans = add(ans, rundp(m, k));
    431 			vector<pair<int, int>> newlayer;
    432 			for (auto p : layer)
    433 			{
    434 				cnt[p.second]--;
    435 				for (auto y : g[p.first])
    436 					if (!used[y])
    437 					{
    438 						newlayer.emplace_back(y, p.second);
    439 						used[y] = true;
    440 						cnt[p.second]++;
    441 					}
    442 			}
    443 			layer = newlayer;
    444 		}
    445 	}
    446 	cout << ans << '\n';
    447 }
    448 
    449 int main()
    450 {
    451 	int t;
    452 	cin >> t;
    453 	while (t--) solve();
    454 	return 0;
    455 }
    456 ```