Разбор
Tutorial is loading...
Решение (Vovuh)
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pos = 0
for i in a:
pos += (pos < len(b) and b[pos] >= i)
print(pos)
1009B - Минимальная троичная строка
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
string s;
cin >> s;
string ans;
int cnt = 0;
for (auto c : s) {
if (c == '1') ++cnt;
else ans += c;
}
int n = ans.size();
int pos = -1;
while (pos + 1 < n && ans[pos + 1] == '0') ++pos;
ans.insert(pos + 1, string(cnt, '1'));
cout << ans << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long li;
int main() {
int n, m;
scanf("%d%d", &n, &m);
li neg = ((n - 1) / 2) * li((n - 1) / 2 + 1);
if (n % 2 == 0) neg += n / 2;
li pos = n * li(n - 1) / 2;
li ans = 0;
forn(i, m){
int x, d;
scanf("%d%d", &x, &d);
ans += x * li(n);
if (d < 0)
ans += neg * d;
else
ans += pos * d;
}
printf("%.15f\n", double(ans) / n);
return 0;
}
Разбор
Tutorial is loading...
Решение (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 100000;
pair<int, int> ans[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
if (m < n - 1) {
puts("Impossible");
return 0;
}
int cur = 0;
forn(i, n) for (int j = i + 1; j < n; ++j){
if (cur == m)
break;
if (__gcd(i + 1, j + 1) == 1)
ans[cur++] = make_pair(j, i);
}
if (cur != m){
puts("Impossible");
return 0;
}
puts("Possible");
forn(i, m)
printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
return 0;
}
1009E - Междугороднее путешествие
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
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 main()
{
int n;
scanf("%d", &n);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int ans = 0;
vector<int> pw2(1, 1);
while(pw2.size() < n)
pw2.push_back(mul(pw2.back(), 2));
int cur = mul(pw2[n - 1], a[0]);
for(int i = 0; i < n; i++)
{
ans = add(ans, cur);
if(i < n - 1)
{
cur = add(cur, -mul(pw2[n - 2 - i], a[i]));
cur = add(cur, mul(pw2[n - 2 - i], a[i + 1]));
}
}
printf("%d\n", ans);
}
Разбор
Tutorial is loading...
Решение (BledDest)
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
// RJ? No, thanks
using namespace std;
const int N = 1000043;
struct state
{
vector<int>* a;
int cur_max;
int sz()
{
return a->size();
}
void add(int i, int val)
{
(*a)[i] += val;
if(make_pair((*a)[i], i) > make_pair((*a)[cur_max], cur_max))
cur_max = i;
}
};
state pull(state z)
{
if(z.sz() == 0)
{
state c;
c.a = new vector<int>(1, 1);
c.cur_max = 0;
return c;
}
else
{
state c;
c.a = z.a;
c.cur_max = z.cur_max;
c.a->push_back(0);
c.add(c.sz() - 1, 1);
return c;
}
}
state merge(state a, state b)
{
if(a.sz() < b.sz())
swap(a, b);
state c;
c.a = a.a;
c.cur_max = a.cur_max;
int as = c.sz();
int bs = b.sz();
for(int i = 0; i < bs; i++)
a.add(as - i - 1, (*(b.a))[bs - i - 1]);
return a;
}
state s[N];
int ans[N];
vector<int> g[N];
void dfs(int x, int p = -1)
{
s[x].a = new vector<int>(0);
s[x].cur_max = 0;
for(auto y : g[x])
if(y != p)
{
dfs(y, x);
s[x] = merge(s[x], s[y]);
}
s[x] = pull(s[x]);
ans[x] = s[x].sz() - s[x].cur_max - 1;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0);
for(int i = 0; i < n; i++)
printf("%d\n", ans[i]);
return 0;
}
Разбор
Tutorial is loading...
Решение (Bleddest)
#include<bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
struct edge
{
int y;
int c;
int f;
edge() {};
edge(int y, int c, int f) : y(y), c(c), f(f) {};
};
const int N = 100;
vector<edge> e;
vector<int> g[N];
int edge_num[N][N];
int char_vertex[6];
int mask_vertex[N];
int used[N];
int cc = 0;
int s, t;
void add_edge(int x, int y, int c)
{
edge_num[x][y] = sz(e);
g[x].push_back(sz(e));
e.push_back(edge(y, c, 0));
edge_num[y][x] = sz(e);
g[y].push_back(sz(e));
e.push_back(edge(x, 0, 0));
}
int rem(int num)
{
return e[num].c - e[num].f;
}
int dfs(int x, int mx)
{
if(x == t) return mx;
if(used[x] == cc) return 0;
used[x] = cc;
for(auto num : g[x])
{
if(rem(num))
{
int pushed = dfs(e[num].y, min(mx, rem(num)));
if(pushed)
{
e[num].f += pushed;
e[num ^ 1].f -= pushed;
return pushed;
}
}
}
return 0;
}
bool check(int ch, int mask)
{
if((mask & (1 << ch)) == 0)
return false;
int cv = char_vertex[ch];
int mv = mask_vertex[mask];
int e1 = edge_num[s][cv];
int e2 = edge_num[mv][t];
if(e[e1].f == 0 || e[e2].f == 0)
return false;
e[e1].f--;
e[e1 ^ 1].f++;
vector<int> affected_edges;
affected_edges.push_back(e1);
for(auto x : g[cv])
{
if((x & 1) == 0 && e[x].f > 0)
{
affected_edges.push_back(x);
e[x].f--;
e[x ^ 1].f++;
int y = e[x].y;
for(auto x2 : g[y])
{
if((x2 & 1) == 0)
{
affected_edges.push_back(x2);
e[x2].f--;
e[x2 ^ 1].f++;
break;
}
}
break;
}
}
if(e[e2].f < e[e2].c)
{
e[e1].c--;
e[e2].c--;
return true;
}
affected_edges.push_back(e2);
e[e2].f--;
e[e2 ^ 1].f++;
for(auto x : g[mv])
{
if((x & 1) == 1 && e[x].f < 0)
{
affected_edges.push_back(x ^ 1);
e[x].f++;
e[x ^ 1].f--;
int y = e[x].y;
for(auto x2 : g[y])
{
if((x2 & 1) == 1)
{
affected_edges.push_back(x2 ^ 1);
e[x2].f++;
e[x2 ^ 1].f--;
break;
}
}
break;
}
}
cc++;
e[e1].c--;
e[e2].c--;
if(dfs(s, 1))
return true;
else
{
e[e1].c++;
e[e2].c++;
for(auto x : affected_edges)
{
e[x].f++;
e[x ^ 1].f--;
}
return false;
}
}
char buf[100043];
string allowed[100043];
int allowed_mask[100043];
int main()
{
s = 70;
t = 71;
scanf("%s", buf);
string z = buf;
int n = sz(z);
int m;
scanf("%d", &m);
for(int i = 0; i < n; i++)
{
allowed[i] = "abcdef";
allowed_mask[i] = 63;
}
for(int i = 0; i < m; i++)
{
int idx;
scanf("%d", &idx);
--idx;
scanf("%s", buf);
allowed[idx] = buf;
allowed_mask[idx] = 0;
for(auto x : allowed[idx])
{
allowed_mask[idx] |= (1 << (x - 'a'));
}
}
for(int i = 0; i < 6; i++)
char_vertex[i] = i;
for(int i = 0; i < (1 << 6); i++)
mask_vertex[i] = i + 6;
for(int i = 0; i < (1 << 6); i++)
for(int j = 0; j < 6; j++)
if(i & (1 << j))
add_edge(char_vertex[j], mask_vertex[i], 100000);
for(int i = 0; i < 6; i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
if(z[j] == 'a' + i)
cnt++;
add_edge(s, char_vertex[i], cnt);
}
for(int i = 0; i < (1 << 6); i++)
{
int cnt = 0;
for(int j = 0; j < n; j++)
if(allowed_mask[j] == i)
cnt++;
add_edge(mask_vertex[i], t, cnt);
}
int flow = 0;
while(true)
{
cc++;
int p = dfs(s, 100000);
if(p)
flow += p;
else
break;
}
if(flow != n)
{
puts("Impossible");
return 0;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < 6; j++)
{
if(check(j, allowed_mask[i]))
{
printf("%c", j + 'a');
break;
}
}
puts("");
}