Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
n, m, k = map(int, input().split())
max_color = (n + m - 1) / m
if max_color + k >= n:
print('NO')
else:
print('YES')
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
lst = -1
ans = n
for i in range(n):
if a[i] != a[0]:
ans = min(ans, i - lst - 1)
lst = i
ans = min(ans, n - lst - 1)
if ans == n:
print(-1)
else:
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string x, y;
cin >> x >> y;
int n = x.size();
bool f = false;
for (int i = 0; i < n; ++i) {
if ((x[i] > y[i]) == f) swap(x[i], y[i]);
f |= (x[i] != y[i]);
}
cout << x << '\n' << y << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
return x;
}
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int s = accumulate(a.begin(), a.end(), 0);
vector<int> dp(s + 1);
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = s - a[i]; j >= 0; --j)
dp[j + a[i]] = add(dp[j + a[i]], dp[j]);
int ans = 0;
for (int j = 0; j <= s; ++j)
ans = add(ans, mul((j + 1) / 2, dp[j]));
for (int i = 0; i < n; ++i)
for (int j = 0; j < a[i]; ++j)
ans = add(ans, mul(a[i] - (a[i] + j + 1) / 2, dp[j]));
cout << ans << '\n';
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int divup(int a, int b){
return (a + b - 1) / b;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
forn(i, n) cin >> a[i];
int mx = *max_element(a.begin(), a.end());
vector<long long> ans(mx + 1);
forn(i, n){
int coef = 0;
if (i == 0 || a[i] > a[i - 1]) ++coef;
if (i + 1 < n && a[i] < a[i + 1]) --coef;
int r = a[i];
ans[r] += coef;
while (r > 0){
int val = divup(a[i], r);
int l = divup(a[i], val);
ans[l - 1] += coef * val;
ans[r] -= coef * val;
r = l - 1;
}
}
forn(i, mx) ans[i + 1] += ans[i];
forn(i, mx) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
Решение 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
forn(i, n) cin >> a[i];
int mx = *max_element(a.begin(), a.end());
vector<long long> pr(mx + 1);
forn(i, n){
int coef = 0;
if (i == 0 || a[i] > a[i - 1]) ++coef;
if (i + 1 < n && a[i] < a[i + 1]) --coef;
pr[a[i]] += coef;
}
forn(i, mx) pr[i + 1] += pr[i];
for (int k = 1; k <= mx; ++k){
long long ans = 0;
for (int l = 1, val = 1; l <= mx; l += k, ++val)
ans += val * 1ll * (pr[min(mx, l + k - 1)] - pr[l - 1]);
cout << ans << ' ';
}
cout << '\n';
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int MOD = int(1e9) + 7;
int add(int a, int b) {
a += b;
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
void upd(int &ans, int val) {
ans = add(ans, val);
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int binPow(int a, int k) {
int ans = 1;
while (k > 0) {
if (k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int N = 3055;
int f[N], invf[N];
void precalcFact() {
f[0] = invf[0] = 1;
fore (i, 1, N) {
f[i] = mul(f[i - 1], i);
invf[i] = binPow(f[i], MOD - 2);
}
}
int C(int n, int k) {
if (k < 0 || k > n)
return 0;
return mul(f[n], mul(invf[k], invf[n - k]));
}
int n, c, k;
inline bool read() {
if(!(cin >> n >> c >> k))
return false;
return true;
}
int d[N][N], sum[N][N];
// d[z][l] - number of strings of length l, with z zeroes and blocks of 1-s shorter than mx
void precalcShort(int mx) {
memset(d, 0, sizeof d);
d[0][0] = 1;
fore (z, 0, n) {
fore (l, 0, n) {
if (d[z][l] == 0)
continue;
upd(d[z + 1][l + 1], +d[z][l]);
upd(d[z + 1][min(n, l + mx) + 1], -d[z][l]);
}
fore (l, 0, n + 1)
upd(d[z + 1][l + 1], d[z + 1][l]);
}
memset(sum, 0, sizeof sum);
fore (z, 0, n + 1) fore (l, 0, n + 1)
sum[z][l + 1] = add(sum[z][l], d[z][l]);
}
//[lf, rg)
int getSum(int z, int lf, int rg) {
if (z < 0 || z > n || lf >= rg)
return 0;
return add(sum[z][rg], -sum[z][lf]);
}
// cnt[g] is a number of x <= n with gcd(x, n) = g
vector<int> precalcCnt(int n) {
vector<int> cnt(n + 1, 0);
fore (x, 1, n + 1)
cnt[gcd(x, n)]++;
return cnt;
}
int calcFixedPoints(int g) {
if (c >= g)
return c + k >= n;
int cntOnes = (c + k) / (n / g);
int cntZeros = g - cntOnes;
int all = 0;
fore (ones, 0, cntOnes + 1)
upd(all, C(g, ones));
int bad = 0;
fore (pref, 0, c) {
int minZeros = max(0, cntZeros - 1);
int minMid = g - c;
int sufLen = g - pref - 1;
fore (z, minZeros, sufLen + 1)
upd(bad, getSum(z, minMid, sufLen + 1));
}
return add(all, -bad);
}
inline void solve() {
precalcFact();
precalcShort(c);
auto cnt = precalcCnt(n);
int ans = 0;
fore (g, 1, n + 1) {
if (n % g != 0)
continue;
int cntFP = calcFixedPoints(g);
// cerr << "g = " << g << " += " << cnt[g] << " * " << cntFP << endl;
upd(ans, mul(cnt[g], cntFP));
}
// cerr << "ans/n = " << ans << " " << n << endl;
cout << mul(ans, binPow(n, MOD - 2)) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}