Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
string s;
cin >> s;
vector<int> cnt(10);
for (auto c : s) ++cnt[c - '0'];
int mx = *max_element(cnt.begin(), cnt.end());
if (mx == 4) cout << -1;
else if (mx == 3) cout << 6;
else cout << 4;
cout << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (adedalic)
fun main() {
repeat(readln().toInt()) {
val n = readln().toLong()
var l = (-1).toLong()
var r = 1e9.toLong()
while (r - l > 1) {
val mid = (l + r) / 2
if (mid * mid >= n)
r = mid
else
l = mid
}
println(r - 1)
}
}
Решение 2 (adedalic)
import kotlin.math.sqrt
fun main() {
repeat(readln().toInt()) {
val n = readln().toLong()
var ans = sqrt(n.toDouble()).toLong()
while (ans * ans > n)
ans--
while (ans * ans < n)
ans++
println(ans - 1)
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
def solve(n, k):
if n == 0:
return []
if k < n:
a = [-1 for i in range(n)]
if k > 0:
a[k - 1] = 200
a[k] = -400
else:
a = solve(n - 1, k - n)
a.append(1000)
return a
t = int(input())
for i in range(t):
n, k = map(int, input().split())
b = solve(n, k)
print(*b)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const long long pw10 = 1e12;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
string s;
cin >> s;
int n = s.size();
int cnt0 = 0, cnt1 = count(s.begin(), s.end(), '1');
long long ans = 1e18;
if (n == 1) ans = 0;
for (int i = 0; i < n - 1; ++i) {
cnt0 += s[i] == '0';
cnt1 -= s[i] == '1';
int k = cnt0 + cnt1 + (s[i] == '1') + (s[i + 1] == '0');
long long cur = (n - k) * (pw10 + 1);
if (s[i] > s[i + 1]) cur += pw10;
ans = min(ans, cur);
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
vector<int> v(n);
forn(i, n) scanf("%d", &v[i]);
vector<vector<int>> ans(a + 1, vector<int>(b + 1));
forn(cd, a + b + 1){
int l = max(0, cd - b), r = min(a, cd);
int sum = 0;
for (int x : v){
sum += x;
l = max({l, sum, cd + sum - b});
r = min({r, a + sum, sum + cd});
}
if (l > r) l = r = max(0, cd - b);
int res = l;
for (int x : v){
if (x > 0)
res -= min({res, x, b - (cd - res)});
else
res += min({cd - res, -x, a - res});
}
forn(c, cd + 1) if (c <= a && cd - c <= b){
ans[c][cd - c] = (c < l ? res : (c > r ? res + r - l : res + c - l));
}
}
forn(i, a + 1){
forn(j, b + 1)
printf("%d ", ans[i][j]);
puts("");
}
return 0;
}
Идея: BledDest
Разбор (Neon)
Tutorial is loading...
Решение (awoo)
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve(){
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<int> b(n);
forn(i, n) scanf("%d", &b[i]);
vector<long long> pr(2 * n + 1);
forn(i, 2 * n) pr[i + 1] = pr[i] + a[i % n];
vector<long long> dist(n);
vector<long long> cost(n);
int cnt = 0;
for (int i = 2 * n - 1; i >= 0; --i){
if (i < n){
if (b[i] == 2){
dist[i] = 1;
cost[i] = a[i] * 2;
}
else if (cnt == 0){
dist[i] = 1;
cost[i] = a[i];
}
else{
int j = lower_bound(pr.begin() + i, pr.begin() + i + cnt + 1, pr[i] + k) - pr.begin();
assert(j > i);
dist[i] = j - i;
if (pr[j] - pr[i] <= k)
cost[i] = pr[j] - pr[i];
else
cost[i] = 2 * (pr[j] - pr[i]) - k;
}
}
if (b[i % n] == 2) ++cnt;
else cnt = 0;
}
int pw = 0;
while ((1 << pw) <= n) ++pw;
vector<vector<long long>> distk(pw, dist);
vector<vector<long long>> costk(pw, cost);
for (int j = 1; j < pw; ++j) forn(i, n){
distk[j][i] = distk[j - 1][i] + distk[j - 1][(i + distk[j - 1][i]) % n];
costk[j][i] = costk[j - 1][i] + costk[j - 1][(i + distk[j - 1][i]) % n];
}
forn(i, n){
int pos = i;
long long tot = 0;
long long ans = 0;
for (int j = pw - 1; j >= 0; --j) if (tot + distk[j][pos] <= n){
tot += distk[j][pos];
ans += costk[j][pos];
pos = (pos + distk[j][pos]) % n;
}
if (tot < n) ans += pr[i + n] - pr[i + tot];
printf("%lld ", ans);
}
puts("");
}
int main(){
int tc;
scanf("%d", &tc);
while (tc--) solve();
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
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)
{
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 divide(int x, int y)
{
return mul(x, inv(y));
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
reverse(a.begin(), a.end());
vector<int> fact(n + 1);
fact[0] = 1;
for(int i = 1; i <= n; i++)
fact[i] = mul(fact[i - 1], i);
// for each player, we find the first player which doesn't conflict with them
vector<int> first_no_conflict(n);
for(int i = 0; i < n; i++)
{
if(i) first_no_conflict[i] = first_no_conflict[i - 1];
while(first_no_conflict[i] < n && a[first_no_conflict[i]] >= a[i] - k)
first_no_conflict[i]++;
}
vector<int> dp(n + 1);
if(a[0] - a[1] > k) dp[1] = 1;
for(int i = 1; i < n; i++)
{
// first choice: put a[i] on the first position
// then we put all which conflict with a[i] on any position other than 1
int no_of_conflicting = first_no_conflict[i] - i - 1;
// put all conflicting with a[i] on any position other than 1
// the first one chooses from i positions, the second - from i+1 positions, and so on
// so the number of ways is fact[i + no_of_conflicting - 1] / fact[i - 1]
dp[i + no_of_conflicting + 1] = add(dp[i + no_of_conflicting + 1], mul(dp[i], divide(fact[i + no_of_conflicting - 1], fact[i - 1])));
// second choice: put a[i] on any other position
dp[i + 1] = add(dp[i + 1], mul(dp[i], i));
}
printf("%d\n", dp[n]);
}