A Very Very Primitive Game
int main()
{
int a, b, c;
cin >> a >> b >> c;
if(c == 0)
{
if(a <= b) puts("Aoki");
else puts("Takahashi");
}
if(c == 1)
{
if(b <= a) puts("Takahashi");
else puts("Aoki");
}
return 0;
}
B Magic 3
int main()
{
int n, s, d;
scanf("%d%d%d", &n, &s, &d);
int flag = 0;
for(int i = 1; i <= n; ++ i)
{
int x, y;
scanf("%d%d", &x, &y);
if(x < s && y > d) flag = 1;
}
puts(flag ? "Yes" : "No");
return 0;
}
C Bowls and Dishes
int n, m, k;
int a[N], b[N];
int c[N], d[N];
int st[N];
int ans;void check()
{
int res = 0;
for(int i = 1; i <= m; ++ i)
if(st[a[i]] && st[b[i]]) res ++;
ans = max(ans, res);
}void dfs(int t)
{
if(t == k + 1) check();
else
{
st[d[t]] ++;
dfs(t + 1);
st[d[t]] --;
st[c[t]] ++;
dfs(t + 1);
st[c[t]] --;
}
}int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i) scanf("%d%d", &a[i], &b[i]);
scanf("%d", &k);
for(int i = 1; i <= k; ++ i) scanf("%d%d", &c[i], &d[i]);
dfs(1);
printf("%d\n", ans);
return 0;
}
D Staircase Sequences
LL n;int main()
{
IOS;
cin >> n;
LL res = 0;
n *= 2;
for(LL i = 1; i <= n / i; ++ i)
{
if(n % i == 0)
{
LL a = i, b = n / i;
if(a % 2 != b % 2) res ++;
}
}
cout << res * 2 << endl;
return 0;
}
E Magical Ornament
const int N = 2e5 + 10;
const int M = 17;int n, m, k;
struct Edge
{
int to, nxt;
}line[N];
int fist[N], idx;
int c[N], d[N];
int f[1 << M][M];
int w[M][M];void add(int x, int y)
{
line[idx] = {y, fist[x]};
fist[x] = idx ++;
}void bfs(int x)
{
queue > q;
q.push({x, 0});
while(!q.empty())
{
auto u = q.front(); q.pop();
for(int i = fist[u.first]; i != -1; i = line[i].nxt)
{
int v = line[i].to;
if(d[v] == -1)
{
d[v] = u.second + 1;
q.push({v, d[v]});
}
}
}
}int main()
{
memset(fist, -1, sizeof fist);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
scanf("%d", &k);
for(int i = 0; i < k; ++ i) scanf("%d", &c[i]);
for(int i = 0; i < k; ++ i)
{
for(int j = 1; j <= n; ++ j) d[j] = -1;
d[c[i]] = 0;
bfs(c[i]);
for(int j = 0; j < k; ++ j)
w[i][j] = (d[c[j]] == -1) ? INF : d[c[j]];
}
// for(int i = 0; i < k; ++ i)
// {
// for(int j = 0; j < k; ++ j)
// printf("%d ", w[i][j]);
// puts("");
// }
memset(f, 0x3f, sizeof f);
for(int i = 0; i < k; ++ i) f[1 << i][i] = 1;for(int i = 1; i < (1 << k); ++ i)
for(int j = 0; j < k; ++ j) if(i >> j & 1)
for(int t = 0; t < k; ++ t) if((i ^ 1 << j) >> t & 1)
f[i][j] = min(f[i][j], f[i ^ 1 << j][t] + w[t][j]);
int res = INF;
for(int i = 0; i < k; ++ i) res = min(res, f[(1 << k) - 1][i]);
if(res >= INF) puts("-1");
else printf("%d\n", res);
return 0;
}
F Shift and Inversions
int n;
int tr[N];
int a[N];int lowbit(int x) { return x & -x; }
void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
int sum(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) { scanf("%d", &a[i]); a[i] ++; }
LL res = 0;
for(int i = 1; i <= n; ++ i)
{
res += sum(n) - sum(a[i]);;
add(a[i], 1);
}
printf("%lld\n", res);
for(int i = 1; i < n; ++ i)
{
res -= sum(a[i] - 1);
res += sum(n) - sum(a[i]);
printf("%lld\n", res);
}
return 0;
}
2021.2.2
