Ideas: MikeMirzayanov.
Tutorial
Tutorial is loading...
Solution
for i in range(0, int(input())):
n = int(input())
c1 = n // 3;
c2 = c1;
if n % 3 == 1:
c1 += 1
elif n % 3 == 2:
c2 += 1
print(c1, c2)
1551B1 - Wonderful Coloring - 1
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int L = 26;
int cnt[L];
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
memset(cnt, 0, sizeof(cnt));
for (auto c : s) cnt[c - 'a']++;
int cnt1 = 0;
int cnt2 = 0;
for (int i = 0; i < L; i++)
if (cnt[i] == 1)
cnt1++;
else if (cnt[i] > 0)
cnt2++;
cout << (cnt2 + cnt1 / 2) << endl;
}
return 0;
}
1551B2 - Wonderful Coloring - 2
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 * 1000 + 13;
int ans[MAX_N];
map<int, vector<int>> indices;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
indices.clear();
memset(ans, 0, n * sizeof(ans[0]));
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (indices[x].size() < k)
indices[x].push_back(i);
}
int m = 0;
for (auto e : indices) m += e.second.size();
m -= m % k;
int color = 0;
for (auto e : indices)
for (auto i : e.second)
{
ans[i] = ++color;
color %= k;
if (--m == 0) goto _output;
}
_output:
for (int i = 0; i < n; i++)
cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2 * 100 * 1000 + 13;
const int L = 26;
vector<int> balance[L];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 0; i < L; i++)
balance[i].clear();
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
int initBalance = -(int)s.length();
for (int j = 0; j < L; j++)
balance[j].push_back(initBalance);
for (auto c : s)
balance[c - 'a'].back() += 2;
}
int bestCount = 0;
int bestLetter = 0;
for (int i = 0; i < L; i++)
{
auto& b = balance[i];
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
if (b[0] <= 0) continue;
int sumBalance = b[0];
int j = 1;
for (; j < n && sumBalance > 0; j++)
sumBalance += b[j];
if (sumBalance <= 0) j--;
if (j > bestCount)
{
bestCount = j;
bestLetter = i;
}
}
cout << bestCount << endl;
}
return 0;
}
1551D1 - Domino (easy version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m, kh;
cin >> n >> m >> kh;
int kv = n * m / 2 - kh;
if (n & 1)
{
kh -= m / 2;
if (kh < 0)
{
cout << "NO\n";
continue;
}
}
else if (m & 1)
{
kv -= n / 2;
if (kv < 0)
{
cout << "NO\n";
continue;
}
}
if ((kh & 1) || (kv & 1))
{
cout << "NO\n";
continue;
}
cout << "YES\n";
}
return 0;
}
1551D2 - Domino (hard version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
char field[128][128];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m, kh;
cin >> n >> m >> kh;
int kv = n * m / 2 - kh;
if (n & 1)
{
kh -= m / 2;
if (kh < 0)
{
cout << "NO\n";
continue;
}
for (int i = 0; i < m / 2; i++)
field[n - 1][i * 2] = field[n - 1][i * 2 + 1] = ((i & 1) ? 'x' : 'y');
}
else if (m & 1)
{
kv -= n / 2;
if (kv < 0)
{
cout << "NO\n";
continue;
}
for (int i = 0; i < n / 2; i++)
field[i * 2][m - 1] = field[i * 2 + 1][m - 1] = ((i & 1) ? 'x' : 'y');
}
if ((kh & 1) || (kv & 1))
{
cout << "NO\n";
continue;
}
for(int i = 0; i < n / 2; i++)
for (int j = 0; j < m / 2; j++)
{
if (kh)
{
kh -= 2;
field[2 * i][2 * j] = field[2 * i][2 * j + 1] = (((i + j) & 1) ? 'a' : 'b');
field[2 * i + 1][2 * j] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
}
else
{
field[2 * i][2 * j] = field[2 * i + 1][2 * j] = (((i + j) & 1) ? 'a' : 'b');
field[2 * i][2 * j + 1] = field[2 * i + 1][2 * j + 1] = (((i + j) & 1) ? 'c' : 'd');
}
}
cout << "YES\n";
for (int i = 0; i < n; i++)
{
field[i][m] = 0;
cout << field[i] << '\n';
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 6000;
int dp[MAX_N][MAX_N];
int a[MAX_N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i; j++)
dp[i][j] = 0;
for(int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
{
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + ((a[i + 1] == j + 1) ? 1 : 0));
}
int ans = -1;
for(int i = n; i >= 0; i--)
if (dp[n][i] >= k)
{
ans = n - i;
break;
}
cout << ans << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 128;
typedef long long ll;
const ll mod = 1000 * 1000 * 1000 + 7;
ll add(ll x, ll y) { return (x + y) % mod; }
ll mul(ll x, ll y) { return x * y % mod; }
vector<int> g[MAX_N];
bool used[MAX_N];
int cnt[MAX_N];
ll dp[MAX_N][MAX_N];
ll rundp(int m, int k)
{
for (int i = 0; i <= m; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 0; i < m; i++)
for (int j = 0; j <= k; j++)
{
dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], cnt[i]));
}
return dp[m][k];
}
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
g[--a].push_back(--b);
g[b].push_back(a);
}
if (k == 2)
{
cout << n * (n - 1LL) / 2 % mod << '\n';
return;
}
ll ans = 0;
for (int center = 0; center < n; center++)
{
memset(used, 0, n);
used[center] = true;
vector<pair<int, int>> layer;
int m = g[center].size();
for (int i = 0; i < m; i++)
{
int y = g[center][i];
layer.emplace_back(y, i);
cnt[i] = 1;
used[y] = true;
}
while (!layer.empty())
{
ans = add(ans, rundp(m, k));
vector<pair<int, int>> newlayer;
for (auto p : layer)
{
cnt[p.second]--;
for (auto y : g[p.first])
if (!used[y])
{
newlayer.emplace_back(y, p.second);
used[y] = true;
cnt[p.second]++;
}
}
layer = newlayer;
}
}
cout << ans << '\n';
}
int main()
{
int t;
cin >> t;
while (t--) solve();
return 0;
}