# ICPC North Vietnam 2022

**Problem B:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define Task "B"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))

const int N = 1e6 + 2, T = 5e3 + 2, mod = 1e9 + 7;
const ll MAX = 1e18, MOD = 1000000000000000009;

int m, n, s0, a[12], b[12];
vector <int> dis(N, -1);

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	if(fopen(Task".inp", "r"))
	{
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> m >> n >> s0;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	
	queue <int> q;
	q.push(s0); dis[s0] = 0;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 1; i <= n; i++)
		{
			int v = (1ll * u * a[i] + b[i]) % m;
			if(dis[v] != -1) continue;
			
			q.push(v);
			dis[v] = dis[u] + 1;
		}
	}
	cout << dis[0];
}

**Problem D:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define Task "D"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))

const int N = 2e5 + 2, T = 5e3 + 2, mod = 1e9 + 7;
const ll MAX = 1e18, MOD = 1000000000000000009;

int y, fac[12];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	if(fopen(Task".inp", "r"))
	{
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}

	cin >> y;
	if(y == 1) return cout << 0, 0;
	
	fac[0] = 1;
	for(int i = 1; i <= 9; i++) fac[i] = fac[i - 1] * i;
	string ans;
	while(y != 0)
	{
		int idx = 1;
		while(idx < 9 && fac[idx + 1] <= y) idx += 1;
		ans += char(idx + 48);
		y -= fac[idx];
	}
	
	reverse(ans.begin(), ans.end());
	cout << ans;
}

**Problem G:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define Task "G"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))

const int N = 5e5 + 2, T = 5e3 + 2, mod = 1e9 + 7;
const ll MAX = 1e18, MOD = 1000000000000000009;

ll SumSqr[N];
string s;

void solve()
{
	cin >> s; int n = s.size();
	s = '#' + s;
	vector <ll> fR(n + 3);
	for(ll i = n; i >= 1; i--)
		fR[i] = (fR[i + 1] + (n - i + 1) * i) % mod;
	
	ll beauty = 0;
	for(int i = 1; i <= n; i++)
	{
		int l = i, r = n - i + 1;
		ll Mn = min(l, r), Mx = max(l, r);
		ll cnt = (SumSqr[Mn] + Mn * (Mn + 1 + Mx - 1) * (Mx - Mn - 1) / 2 + fR[Mx]) % mod;
		beauty = (beauty + (s[i] - 96) * cnt) % mod;
//		cout << cnt << "\n";
	}
	cout << beauty << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	if(fopen(Task".inp", "r"))
	{
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
	
	for(ll i = 1; i <= 5e5; i++)
		SumSqr[i] = (SumSqr[i - 1] + i * i) % mod;
	
	int q; cin >> q;
	while(q--)
		solve();
}

**Problem H:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define Task "H"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))
 
const int N = 2e1, T = 4e5 + 2, mod = 1e9 + 7;
const ll maximum = 1e18, MOD = 1000000000000000009;

multiset <int> p1, p2;

void solve()
{
	string s; int x;
	cin >> s;
	
	if(s == "IN")
	{
		cin >> x;
		if(p1.size() == p2.size()) // -> p1.size > p2.size
		{
			if(x <= *p2.begin()) p1.insert(x);
			else
			{
				int val = *p2.begin();
				p1.insert(val);
				p2.erase(p2.find(val)); p2.insert(x);
			}
		}
		else if(p1.size() > p2.size()) // -> p1.size = p2.size
		{
			if(x >= *p1.rbegin()) p2.insert(x);
			else
			{
				int val = *p1.rbegin();
				p1.erase(p1.find(val)); p1.insert(x);
				p2.insert(val);
			}
		}
	}
	else if(s == "OUT")
	{
		cin >> x;
		if(p1.size() == p2.size()) // -> p1.size > p2.size
		{
			if(p2.find(x) != p2.end()) p2.erase(p2.find(x));
			else
			{
				int val = *p2.begin();
				p1.erase(p1.find(x)); p1.insert(val);
				p2.erase(p2.find(val));
			}
		}
		else if(p1.size() > p2.size()) // -> p1.size = p2.size
		{
			if(p1.find(x) != p1.end()) p1.erase(p1.find(x));
			else
			{
				int val = *p1.rbegin();
				p1.erase(p1.find(val));
				p2.erase(p2.find(x)); p2.insert(val);
			}
		}
	}
	else
	{
		if(p1.size() > p2.size()) cout << *p1.rbegin() << "\n";
		else cout << (*p1.rbegin() + *p2.begin()) / 2.0 << "\n";
	}
	
//	if(p1.size() < p2.size() || (!p1.empty() && !p2.empty() && *p1.rbegin() > *p2.begin()))
//		cout << "ERROR: " << s << " " << x << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	if(fopen(Task".inp", "r"))
	{
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
	
	p1.insert(0); p2.insert(2e9);
	
	int q; cin >> q;
	while(q--)
		solve();
}

# ICPC Central Vietnam 2022

**Problem A:**

#include<bits/stdc++.h>
using namespace std;
int n, k, p[305], f[305][305][305]; 
string s;
bool dp(int l, int r, int c){
    if(c == 0) return false;
    if(l > r) return c > 0;
    if(r == l) return c - s[l] > 0;
    int sum = p[n] - p[r] + p[l - 1];
    if(sum - (k - c) >= k) return true;
    int& res = f[l][r][c];
    if(res != -1) return res;
    return res = ((dp(l + 2, r, c - s[l]) && dp(l + 1, r - 1, c - s[l])) || (dp(l, r - 2, c - s[r]) && dp(l + 1, r - 1, c - s[r])));
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("A.inp", "r", stdin);
    cin >> n >> k >> s; s = '#' + s; p[0] = 0;
    for(int i = 1; i <= n; i++) s[i] = (s[i] == 'B'), p[i] = p[i - 1] + (int)s[i];
    memset(f, -1, sizeof(f));
    cout << (dp(1, n, k) ? "YES" : "NO");
}

**Problem B:**

**Problem C:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define fi first
#define se second
#define Task "C"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))
 
const int N = 2e5 + 2, T = 2e5 + 2, mod = 1e9 + 7;
const ll maximum = 1e18, MOD = 1000000000000000009;

struct TSegmentTree
{
	ll f[4 * N][12];
	
	void Update(int id, int low, int high, int i, int k, ll d)
	{
		if(low > i || high < i) return;
		if(low == high)
		{
			f[id][k] = d;
			return;
		}
		
		int mid = (low + high) / 2;
		if(i <= mid) Update(id * 2, low, mid, i, k, d);
		else Update(id * 2 + 1, mid + 1, high, i, k, d);
		
		f[id][k] = f[id * 2][k] + f[id * 2 + 1][k];
	}
	
	ll GetF(int id, int low, int high, int L, int R, int k)
	{
		if(low > R || high < L) return 0;
		if(L <= low && high <= R) return f[id][k];
		
		int mid = (low + high) / 2;
		return GetF(id * 2, low, mid, L, R, k) + GetF(id * 2 + 1, mid + 1, high, L, R, k);
	}
};

TSegmentTree Tree;
pair <int, int> p[N];
int n, k;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	if(fopen(Task".inp", "r"))
	{
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
	
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> p[i].fi >> p[i].se;
	sort(p + 1, p + 1 + n);
	
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{
		Tree.Update(1, 1, n, p[i].se, 1, 1);
		if(k == 1) ans += 1;
		for(int j = 2; j <= k; j++)
		{
			ll S = Tree.GetF(1, 1, n, 1, p[i].se - 1, j - 1);
			Tree.Update(1, 1, n, p[i].se, j, S);
			if(j == k) ans += S;
		}
	}
	cout << ans;
}

**Problem D:**

**Problem G:**

**Problem H:**

**Problem I:**

**Problem N:**

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define ld long double
#define ull unsigned long long
#define bigint __int128
#define pb push_back
#define Task "N"

#define testBit(a, k) ((a >> k) & 1)
#define flipBit(a, k) (a ^ (1ll << k))
 
const int N = 2e1, T = 4e5 + 2, mod = 1e9 + 7;
const ll maximum = 1e18, MOD = 1000000000000000009;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    if(fopen(Task".inp", "r"))
    {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }

    int q; cin >> q;
    while(q--)
    {
        double n; cin >> n;
        double ans = 1000000000.0 / (n + 1);
        cout << fixed << setprecision(9) << ans << "\n";
    }
}

# ICPC South Vietnam 2022