Tutorial
Tutorial is loading...
Solution (Roms)
for _ in range(int(input())):
x, y = map(int, input().split())
a, b = map(int, input().split())
b = min(b, a + a)
if x < y:
x, y= y, x
print(y * b + (x - y) * a)
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val t = readLine()!!
val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
println(s)
}
}
1342C - Yet Another Counting Problem
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 40043;
int len;
int p[N];
void build(int a, int b)
{
len = a * b;
p[0] = 0;
for(int i = 1; i <= len; i++)
{
p[i] = p[i - 1];
if((i % a) % b != (i % b) % a)
p[i]++;
}
}
long long query(long long l)
{
long long cnt = l / len;
int rem = l % len;
return p[len] * 1ll * cnt + p[rem];
}
long long query(long long l, long long r)
{
return query(r) - query(l - 1);
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int a, b, q;
cin >> a >> b >> q;
build(a, b);
long long l, r;
for(int j = 0; j < q; j++)
{
cin >> l >> r;
cout << query(l, r) << " ";
}
cout << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<int> c(k + 1);
forn(i, k) scanf("%d", &c[i + 1]);
sort(a.begin(), a.end(), greater<int>());
int ans = 0;
for (int i = k, g = 0; i >= 1; --i){
while (g < n && a[g] == i) ++g;
ans = max(ans, (g + c[i] - 1) / c[i]);
}
vector<vector<int>> res(ans);
forn(i, n) res[i % ans].push_back(a[i]);
printf("%d\n", ans);
forn(i, ans){
printf("%d", int(res[i].size()));
for (auto it : res[i])
printf(" %d", it);
puts("");
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 200043;
int add(int x, int y)
{
return (x + y) % MOD;
}
int sub(int x, int y)
{
return add(x, MOD - y);
}
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 C(int n, int k)
{
return mul(fact[n], inv(mul(fact[k], fact[n - k])));
}
int main()
{
int n, k;
cin >> n >> k;
if(k > n - 1)
{
cout << 0 << endl;
return 0;
}
fact[0] = 1;
for(int i = 1; i <= n; i++)
fact[i] = mul(i, fact[i - 1]);
int ans = 0;
int c = n - k;
for(int i = c; i >= 0; i--)
if(i % 2 == c % 2)
ans = add(ans, mul(binpow(i, n), C(c, i)));
else
ans = sub(ans, mul(binpow(i, n), C(c, i)));
ans = mul(ans, C(n, c));
if(k > 0)
ans = mul(ans, 2);
cout << ans << endl;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int INF = 1e9;
const int N = 15;
int n;
int a[N];
int sum[1 << N];
int dp[N + 1][1 << N][N + 1];
pt p[N + 1][1 << N][N + 1];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%d", &a[i]);
forn(mask, 1 << n) {
sum[mask] = 0;
forn(i, n) if (mask & (1 << i))
sum[mask] += a[i];
}
forn(cnt, n + 1) forn(mask, 1 << n) forn(pos, n + 1)
dp[cnt][mask][pos] = INF;
dp[0][0][0] = 0;
forn(cnt, n) forn(mask, 1 << n) forn(pos, n) if (dp[cnt][mask][pos] < INF) {
int rmask = mask ^ ((1 << n) - 1);
for (int nmask = rmask; nmask; nmask = (nmask - 1) & rmask) {
if (sum[nmask] <= dp[cnt][mask][pos])
continue;
if ((nmask >> pos) == 0)
continue;
int npos = pos + __builtin_ctz(nmask >> pos) + 1;
if (dp[cnt + 1][mask | nmask][npos] > sum[nmask]) {
dp[cnt + 1][mask | nmask][npos] = sum[nmask];
p[cnt + 1][mask | nmask][npos] = mp(mask, pos);
}
}
}
int acnt = 0, apos = 0;
forn(cnt, n + 1) forn(pos, n + 1) if (dp[cnt][(1 << n) - 1][pos] < INF)
acnt = cnt, apos = pos;
vector<pt> ans;
int mask = (1 << n) - 1, pos = apos;
for (int cnt = acnt; cnt > 0; --cnt) {
int nmask = p[cnt][mask][pos].x;
int npos = p[cnt][mask][pos].y;
forn(i, n) if ((nmask ^ mask) & (1 << i))
if (i != pos - 1) ans.pb(mp(i, pos - 1));
mask = nmask, pos = npos;
}
printf("%d\n", sz(ans));
forn(i, sz(ans)) {
int from = ans[i].x;
forn(j, i) from -= ans[j].x < ans[i].x;
int to = ans[i].y;
forn(j, i) to -= ans[j].x < ans[i].y;
printf("%d %d\n", from + 1, to + 1);
}
}
int main() {
int tc;
scanf("%d", &tc);
forn(i, tc) solve();
}