1312A - Два правильных многоугольника
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
for i in range(int(input())):
n, m = map(int, input().split())
print('YES' if n % m == 0 else 'NO')
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
n = input()
print(*sorted(map(int, input().split()))[::-1])
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun getMask(a: Long, k: Long): Long? {
var (tmp, res) = listOf(a, 0L)
var cnt = 0
while (tmp > 0) {
if (tmp % k > 1)
return null
res = res or ((tmp % k) shl cnt)
tmp /= k
cnt++
}
return res
}
fun main() {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val (n, k) = readLine()!!.split(' ').map { it.toLong() }
val a = readLine()!!.split(' ').map { getMask(it.toLong(), k) }
val b = a.filterNotNull()
if (b.size < n) {
println("NO")
continue
} else {
val res = b.reduce { acc, l -> if (acc < 0 || (acc and l) > 0) -1 else acc or l }
println(if (res < 0) "NO" else "YES")
}
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 200043;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
int fact[N];
void precalc()
{
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(fact[i - 1], i);
}
int C(int n, int k)
{
return divide(fact[n], mul(fact[k], fact[n - k]));
}
int main()
{
precalc();
int n, m;
cin >> n >> m;
int ans = 0;
if(n > 2)
ans = mul(C(m, n - 1), mul(n - 2, binpow(2, n - 3)));
cout << ans << endl;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution (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())
#define x first
#define y second
typedef long long li;
typedef long double ld;
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) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const int N = 555;
int n, a[N];
inline bool read() {
if(!(cin >> n))
return false;
fore(i, 0, n)
cin >> a[i];
return true;
}
int dp[N][N];
int calcDP(int l, int r) {
assert(l < r);
if(l + 1 == r)
return dp[l][r] = a[l];
if(dp[l][r] != 0)
return dp[l][r];
dp[l][r] = -1;
fore(mid, l + 1, r) {
int lf = calcDP(l, mid);
int rg = calcDP(mid, r);
if(lf > 0 && lf == rg)
return dp[l][r] = lf + 1;
}
return dp[l][r];
}
int dp2[N];
inline void solve() {
fore(i, 0, N)
dp2[i] = INF;
dp2[0] = 0;
fore(i, 0, n) {
fore(j, i + 1, n + 1) {
if(calcDP(i, j) > 0)
dp2[j] = min(dp2[j], dp2[i] + 1);
}
}
cout << dp2[n] << 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;
}
1312F - Атака на Красное Королевство
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
const int K = 5;
int x, y, z, n;
long long a[N];
typedef vector<vector<int> > state;
map<state, int> d;
int cnt;
int p;
vector<vector<int> > state_log;
int mex(const vector<int>& a)
{
for(int i = 0; i < a.size(); i++)
{
bool f = false;
for(auto x : a)
if(x == i)
f = true;
if(!f)
return i;
}
return a.size();
}
state go(state s)
{
int f1 = mex({s[0][K - x], s[1][K - y], s[2][K - z]});
int f2 = mex({s[0][K - x], s[2][K - z]});
int f3 = mex({s[0][K - x], s[1][K - y]});
state nw = s;
nw[0].push_back(f1);
nw[1].push_back(f2);
nw[2].push_back(f3);
for(int i = 0; i < 3; i++)
nw[i].erase(nw[i].begin());
return nw;
}
void precalc()
{
d.clear();
state cur(3, vector<int>(K, 0));
cnt = 0;
state_log.clear();
while(!d.count(cur))
{
d[cur] = cnt;
state_log.push_back({cur[0].back(), cur[1].back(), cur[2].back()});
cur = go(cur);
cnt++;
}
p = cnt - d[cur];
}
int get_grundy(long long x, int t)
{
if(x < cnt)
return state_log[x][t];
else
{
int pp = cnt - p;
x -= pp;
return state_log[pp + (x % p)][t];
}
}
void read()
{
scanf("%d %d %d %d", &n, &x, &y, &z);
for(int i = 0; i < n; i++)
scanf("%lld", &a[i]);
}
int check(int x, int y)
{
return x == y ? 1 : 0;
}
void solve()
{
precalc();
int ans = 0;
for(int i = 0; i < n; i++)
ans ^= get_grundy(a[i], 0);
int res = 0;
for(int i = 0; i < n; i++)
{
ans ^= get_grundy(a[i], 0);
res += check(ans, get_grundy(max(0ll, a[i] - x), 0));
res += check(ans, get_grundy(max(0ll, a[i] - y), 1));
res += check(ans, get_grundy(max(0ll, a[i] - z), 2));
ans ^= get_grundy(a[i], 0);
}
printf("%d\n", res);
}
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
read();
solve();
}
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 1000043;
map<char, int> nxt[N];
bool term[N];
int n, k;
char buf[3];
int dp[N];
int dict[N];
int T[4 * N];
int f[4 * N];
void build(int v, int l, int r)
{
T[v] = int(1e9);
if(l != r - 1)
{
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
}
}
int getVal(int v)
{
return T[v] + f[v];
}
void push(int v, int l, int r)
{
T[v] += f[v];
if(l != r - 1)
{
f[v * 2 + 1] += f[v];
f[v * 2 + 2] += f[v];
}
f[v] = 0;
}
void upd(int v, int l, int r)
{
if(l != r - 1)
{
T[v] = min(getVal(v * 2 + 1), getVal(v * 2 + 2));
}
}
int get(int v, int l, int r, int L, int R)
{
if(L >= R)
return int(1e9);
if(l == L && r == R)
return getVal(v);
push(v, l, r);
int m = (l + r) / 2;
int ans = min(get(v * 2 + 1, l, m, L, min(m, R)), get(v * 2 + 2, m, r, max(L, m), R));
upd(v, l, r);
return ans;
}
void add(int v, int l, int r, int L, int R, int val)
{
if(L >= R)
return;
if(l == L && r == R)
{
f[v] += val;
return;
}
push(v, l, r);
int m = (l + r) / 2;
add(v * 2 + 1, l, m, L, min(m, R), val);
add(v * 2 + 2, m, r, max(L, m), R, val);
upd(v, l, r);
}
void setVal(int v, int l, int r, int pos, int val)
{
if(l == r - 1)
{
f[v] = 0;
T[v] = val;
return;
}
push(v, l, r);
int m = (l + r) / 2;
if(pos < m)
setVal(v * 2 + 1, l, m, pos, val);
else
setVal(v * 2 + 2, m, r, pos, val);
upd(v, l, r);
}
void dfs(int v, int d, int last)
{
dp[v] = last + 1;
if(term[v])
dp[v] = min(dp[v], get(0, 0, n + 1, 0, d));
setVal(0, 0, n + 1, d, dp[v] + 1);
if(term[v])
add(0, 0, n + 1, 0, d + 1, 1);
for(auto x : nxt[v])
dfs(x.second, d + 1, dp[v]);
setVal(0, 0, n + 1, d, int(1e9));
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
int p;
scanf("%d %s", &p, buf);
char c = buf[0];
nxt[p][c] = i + 1;
}
scanf("%d", &k);
for(int i = 0; i < k; i++)
{
scanf("%d", &dict[i]);
term[dict[i]] = true;
}
build(0, 0, n + 1);
dfs(0, 0, -1);
for(int i = 0; i < k; i++)
printf("%d ", dp[dict[i]]);
puts("");
}