Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl;
}
}
1487B - Круговорот котов в квартире
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
var (n, k) = readLine()!!.split(' ').map { it.toInt() }
k--
val floor = n / 2
println((k + (n % 2) * k / floor) % n + 1)
}
}
1487C - Как можно меньше ничьих
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
if(n % 2 == 1)
{
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(j - i <= n / 2)
cout << 1 << " ";
else
cout << -1 << " ";
cout << endl;
}
else
{
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(j - i < n / 2)
cout << 1 << " ";
else if(j - i == n / 2)
cout << 0 << " ";
else
cout << -1 << " ";
cout << endl;
}
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
for (int i = 3; i * i <= 2 * n - 1; i += 2)
++ans;
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int> ns(4);
for(int i = 0; i < 4; i++)
scanf("%d", &ns[i]);
vector<vector<int>> cs(4);
for(int i = 0; i < 4; i++)
{
cs[i].resize(ns[i]);
for(int j = 0; j < ns[i]; j++)
scanf("%d", &cs[i][j]);
}
vector<vector<vector<int>>> bad(3);
for(int i = 0; i < 3; i++)
{
bad[i].resize(ns[i + 1]);
int m;
scanf("%d", &m);
for(int j = 0; j < m; j++)
{
int x, y;
scanf("%d %d", &x, &y);
x--;
y--;
bad[i][y].push_back(x);
}
}
vector<vector<int>> dp(4);
dp[0] = cs[0];
for(int i = 0; i < 3; i++)
{
dp[i + 1].resize(ns[i + 1]);
multiset<int> s;
for(int j = 0; j < ns[i]; j++)
s.insert(dp[i][j]);
for(int j = 0; j < ns[i + 1]; j++)
{
for(auto k : bad[i][j])
s.erase(s.find(dp[i][k]));
if(s.empty())
dp[i + 1][j] = int(4e8 + 43);
else
dp[i + 1][j] = *s.begin() + cs[i + 1][j];
for(auto k : bad[i][j])
s.insert(dp[i][k]);
}
}
int ans = *min_element(dp[3].begin(), dp[3].end());
if(ans > int(4e8))
ans = -1;
cout << ans << endl;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 250;
const int M = 28;
const int INF = 1e9;
int dp[2][M * 2 + 1][N][N];
int main() {
string s;
cin >> s;
reverse(s.begin(), s.end());
s += "0";
forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF;
dp[0][M][N - 1][N - 1] = 0;
forn(i, sz(s)) {
forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF;
forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) {
if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]);
if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]);
int rcarry = carry - M;
int val = rcarry + cp - cn;
int digit = val % 10;
if (digit < 0) digit += 10;
int ncarry = val / 10;
if (val < 0 && digit != 0) --ncarry;
if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn);
}
swap(dp[0], dp[1]);
}
int ans = INF;
forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]);
cout << ans << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 402;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int c[26];
int dp[2][N][N][3][3];
int sumDp[N][N];
int p1[N][N];
int p2[N][N];
int n;
int main()
{
cin >> n;
for(int i = 0; i < 26; i++)
cin >> c[i];
for(int i = 0; i < 26; i++)
for(int j = 0; j < 26; j++)
for(int k = 0; k < 26; k++)
if(i != k)
{
multiset<int> s = {i, j, k};
dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++;
}
for(int i = 4; i <= n; i++)
{
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
for(int x = 0; x < 3; x++)
for(int y = 0; y < 3; y++)
{
dp[0][j][k][x][y] = dp[1][j][k][x][y];
dp[1][j][k][x][y] = 0;
}
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
for(int x = 0; x < 3; x++)
for(int y = 0; y < 3; y++)
{
int cur = dp[0][j][k][x][y];
if(cur == 0) continue;
for(int z = 0; z < 3; z++)
{
int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z];
nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0)));
}
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < 3; k++)
for(int l = 0; l < 3; l++)
sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]);
for(int i = 0; i < N; i++)
{
p1[i][N - 1] = sumDp[i][N - 1];
for(int j = N - 2; j >= 0; j--)
p1[i][j] = add(sumDp[i][j], p1[i][j + 1]);
}
for(int j = 0; j < N; j++)
{
p2[N - 1][j] = p1[N - 1][j];
for(int i = N - 2; i >= 0; i--)
p2[i][j] = add(p1[i][j], p2[i + 1][j]);
}
int ans = p2[0][0];
for(int i = 0; i < 26; i++)
{
for(int j = 0; j < N; j++)
for(int k = c[i] + 1; k < N; k++)
ans = sub(ans, sumDp[k][j]);
}
for(int i = 0; i < 26; i++)
for(int j = 0; j < i; j++)
ans = add(ans, p2[c[i] + 1][c[j] + 1]);
cout << ans << endl;
}