Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val c = readLine()!!.groupingBy { it }.eachCount().maxBy { it.value }!!.key
println(c.toString().repeat(n))
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (p, f) = readLine()!!.split(' ').map { it.toInt() }
var (cntS, cntW) = readLine()!!.split(' ').map { it.toInt() }
var (s, w) = readLine()!!.split(' ').map { it.toInt() }
if (s > w) {
s = w.also { w = s }
cntS = cntW.also { cntW = cntS }
}
var ans = 0
for (s1 in 0..minOf((p / s), cntS)) {
val w1 = minOf(cntW, (p - s * s1) / w)
val s2 = minOf(cntS - s1, f / s)
val w2 = minOf(cntW - w1, (f - s * s2) / w)
ans = maxOf(ans, s1 + s2 + w1 + w2)
}
println(ans)
}
}
1400C - Восстановление бинарной строки
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
int t;
string s;
int x;
string f(string s) {
string res = s;
for (int i = 0; i < s.size(); ++i) {
if (i - x >= 0 && s[i - x] == '1' || i + x < s.size() && s[i + x] == '1')
res[i] = '1';
else
res[i] = '0';
}
return res;
}
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
cin >> s >> x;
int n = s.size();
string ns = string(n, '1');
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
if (i - x >= 0) ns[i - x] = '0';
if (i + x < n) ns[i + x] = '0';
}
}
if (f(ns) == s) cout << ns << endl;
else cout << -1 << endl;
}
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() - 1 }.toIntArray()
val cntLeft = IntArray(n) { 0 }
val cntRight = IntArray(n) { 0 }
var ans = 0L
for (j in a.indices) {
cntRight.fill(0)
for (k in n - 1 downTo j + 1) {
ans += cntLeft[a[k]] * cntRight[a[j]]
cntRight[a[k]]++
}
cntLeft[a[j]]++
}
println(ans)
}
}
1400E - Очистите мультимножество
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(5e3) + 9;
int n;
int a[N];
int dp[N][N];
int calc (int pos, int x) {
int &res = dp[pos][x];
if (res != -1) return res;
if (pos == n) return res = 0;
res = 1 + calc(pos + 1, n);
res = min(res, calc(pos + 1, pos) + a[pos]);
if (x != n) {
if (a[x] >= a[pos])
res = min(res, calc(pos + 1, pos));
else {
res = min(res, calc(pos + 1, pos) + a[pos] - a[x]);
res = min(res, 1 + calc(pos + 1, x));
}
}
return res;
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", a + i);
memset(dp, -1, sizeof(dp));
printf("%d\n", calc(0, n));
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 9;
const int N = 5000;
const int INF = 1e9;
string s;
int x;
struct node{
int nxt[AL];
int p;
char pch;
int link;
int go[AL];
bool term;
node(){
memset(nxt, -1, sizeof(nxt));
memset(go, -1, sizeof(go));
link = p = -1;
term = false;
}
int& operator [](int x){
return nxt[x];
}
};
vector<node> trie;
void add_string(string s){
int v = 0;
for (auto it : s){
int c = it - '1';
if (trie[v][c] == -1){
trie.push_back(node());
trie[trie.size() - 1].p = v;
trie[trie.size() - 1].pch = c;
trie[v][c] = trie.size() - 1;
}
v = trie[v][c];
}
trie[v].term = true;
}
int go(int v, int c);
int get_link(int v){
if (trie[v].link == -1){
if (v == 0 || trie[v].p == 0)
trie[v].link = 0;
else
trie[v].link = go(get_link(trie[v].p), trie[v].pch);
}
return trie[v].link;
}
int go(int v, int c) {
if (trie[v].go[c] == -1){
if (trie[v][c] != -1)
trie[v].go[c] = trie[v][c];
else
trie[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
}
return trie[v].go[c];
}
string t;
void brute(int i, int sum){
if (sum == x){
bool ok = true;
for (int l = 0; l < int(t.size()); ++l){
int cur = 0;
for (int r = l; r < int(t.size()); ++r){
cur += (t[r] - '0');
if (x % cur == 0 && cur != x)
ok = false;
}
}
if (ok){
add_string(t);
}
return;
}
for (int j = 1; j <= min(x - sum, 9); ++j){
t += '0' + j;
brute(i + 1, sum + j);
t.pop_back();
}
}
int main() {
cin >> s >> x;
trie.push_back(node());
brute(0, 0);
vector<vector<int>> dp(s.size() + 1, vector<int>(trie.size(), INF));
dp[0][0] = 0;
forn(i, s.size()) forn(j, trie.size()) if (dp[i][j] != INF){
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
int nxt = go(j, s[i] - '1');
if (!trie[nxt].term)
dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
}
printf("%d\n", *min_element(dp[s.size()].begin(), dp[s.size()].end()));
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
const int MOD = 998244353;
int add(int x, int y)
{
return ((x + y) % MOD + MOD) % MOD;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1)
z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int fact[N];
int rfact[N];
void prepare_fact()
{
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(i, fact[i - 1]);
for(int i = 0; i < N; i++)
rfact[i] = inv(fact[i]);
}
int c(int n, int k)
{
if(n < 0 || n < k || k < 0)
return 0;
return mul(fact[n], mul(rfact[k], rfact[n - k]));
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> l(n), r(n), a(m), b(m);
for(int i = 0; i < n; i++)
scanf("%d %d", &l[i], &r[i]);
for(int i = 0; i < m; i++)
scanf("%d %d", &a[i], &b[i]);
vector<int> cnt(n + 2);
for(int i = 0; i < n; i++)
{
cnt[l[i]]++;
cnt[r[i] + 1]--;
}
for(int i = 0; i < n + 1; i++)
cnt[i + 1] += cnt[i];
prepare_fact();
vector<vector<int> > p(2 * m + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 2 * m; j++)
p[j][i] = add(p[j][i - 1], c(cnt[i] - j, i - j));
int ans = 0;
for(int mask = 0; mask < (1 << m); mask++)
{
int sign = 1;
set<int> used;
for(int i = 0; i < m; i++)
if(mask & (1 << i))
{
sign = mul(sign, MOD - 1);
used.insert(a[i] - 1);
used.insert(b[i] - 1);
}
int L = 1, R = n;
for(auto x : used)
{
L = max(L, l[x]);
R = min(R, r[x]);
}
if(R < L) continue;
ans = add(ans, mul(sign, add(p[used.size()][R], -p[used.size()][L - 1])));
}
printf("%d\n", ans);
}