#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        string n;
        cin >> n;
        if (n.size() == 2) {
            cout << n[1] << '\n';
        } else {
            cout << *min_element(n.begin(), n.end()) << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << " " << b + c << " " << c << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<int>> &a) {
    int n = a.size(), m = a[0].size();
    vector<int> bad;
    for (int i = 0; i < n && bad.empty(); i++) {
        vector<int> b = a[i];
        sort(b.begin(), b.end());
        for (int j = 0; j < m; j++) {
            if (a[i][j] != b[j]) bad.push_back(j);
        }
    }
    if ((int)bad.size() == 0) {
    	cout << 1 << " " << 1 << "\n";
    	return;
    }
    if ((int)bad.size() > 2) {
    	cout << -1 << "\n";
    	return;
    }
    for (int i = 0; i < n; i++) {
        swap(a[i][bad[0]], a[i][bad[1]]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (a[i][j] < a[i][j - 1]) {
            	cout << -1 << "\n";
            	return;
           	}
        }
    }
    cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
    return;
}

int main() {
	#ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> a(n, vector<int>(m));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> a[i][j];
			}
		}
		solve(a);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

void solve() {
    int n, k;
    cin >> n >> k;
    long long ans = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ans += a[i];
        a[i] += i + 1;
    }
    sort(all(a));
    reverse(all(a));
    for (int i = 0; i < k; i++) ans -= a[i];
    for (int i = 0; i < k; i++) {
        ans += n;
        ans -= i;
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    map<int, int> cnt;
    for (auto &c : a) cnt[c]++;
    set<pii> s1, s2;
    int sum1 = 0;
    for (auto &c : cnt) s2.insert(mp(c.se, c.fi));
    int ans = INF;
    int skip = 0;
    for (int x = 0; x <= n; x++) {
        if (s1.find(mp(cnt[x - 1], x - 1)) != s1.end()) {
            sum1 -= cnt[x - 1];
            s1.erase(mp(cnt[x - 1], x - 1));
        }
        if (s2.find(mp(cnt[x - 1], x - 1)) != s2.end()) {
            s2.erase(mp(cnt[x - 1], x - 1));
        }
        while (s2.size() && sum1 + s2.begin()->fi <= k) {
            s1.insert(*s2.begin());
            sum1 += s2.begin()->fi;
            s2.erase(s2.begin());
        }
        if (k < skip) break;
        int now = x + s2.size();
        if (x == 0) {
            now = max(1, (int)s2.size());
        }
        ans = min(ans, now - x);
        if (cnt[x] == 0) skip++;
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

vector<int> f;

void incr(int x, int d) {
    for (; x < (int)f.size(); x |= (x + 1)) f[x] = max(f[x], d);
}

int get(int x) {
    int ans = -1;
    for (; x >= 0; x = (x & (x + 1)) - 1) ans = max(ans, f[x]);
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    map<int, vector<int>> gist;
    for (int i = 0; i < n; i++) gist[a[i]].pb(i);
    vector<pii> seg(m);
    f.assign(n, -1);
    for (auto &c : seg) {
        cin >> c.fi >> c.se; c.fi--; c.se--;
        incr(c.fi, c.se);
    }
    vector<int> mnl(n);
    set<int> s;
    int l = n;
    for (int r = n - 1; r >= 0; r--) {
        while (l - 1 >= 0 && !s.count(a[l - 1])) {
            l--;
            s.insert(a[l]);
        }
        mnl[r] = l;
        s.erase(a[r]);
    }
    int mnr = -1;
    for (auto &c : seg) {
        int l = c.fi, r = c.se;
        if (mnl[r] <= l) continue;
        mnr = max(mnr, mnl[r] - 1);
    }
    if (mnr == -1) {
        cout << 0 << "\n";
        return;
    }
    int ans = mnr + 1;
    for (int l = 0; l + 1 < n; l++) {
        if (gist[a[l]][0] != l) {
            int id = lower_bound(all(gist[a[l]]), l) - gist[a[l]].begin() - 1;
            int pr = gist[a[l]][id];
            if (get(pr) >= l) {
                break;
            }
        }
        int id = upper_bound(all(gist[a[l]]), mnr) - gist[a[l]].begin();
        if (id != (int)gist[a[l]].size()) {
            int nxt = gist[a[l]][id];
            if (get(l) >= nxt) {
                mnr = nxt;
            }
        }
        mnr = max(mnr, l + 1);
        ans = min(ans, mnr - l);
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>
#define int ll

const int INF = 1e9 + 1;
const ll INFLL = 1e18;
 
vector<vector<int>> g;
vector<int> with;
vector<int> usd;
 
int dfs(int v) {
    if (usd[v]) return 0;
    usd[v] = 1;
    for (auto &to : g[v]) {
        if (with[to] == -1) {
            with[to] = v;
            return 1;
        }
    }
    for (auto &to : g[v]) {
        if (dfs(with[to])) {
            with[to] = v;
            return 1;
        }
    }
    return 0;
}

signed main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int n, A;
    cin >> n >> A;
    vector<int> a(n);
    vector<int> l, r;
    for (auto &c : a) {
        cin >> c;
        if (3 * c > A) {
            l.pb(c);
        } else {
            r.pb(c);
        }
    }
    g.resize(l.size());
    with.resize(r.size(), -1);
    for (int i = 0; i < (int)l.size(); i++) {
        for (int j = 0; j < (int)r.size(); j++) {
            if (l[i] % r[j] == 0 && 2 * l[i] + r[j] <= A) {
                g[i].pb(j);
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < (int)l.size(); i++) {
        usd.assign(l.size(), 0);
        cnt += dfs(i);
    }
    if (cnt < (int)l.size()) {
        cout << -1;
        return 0;
    }
    vector<pii> ans;
    for (int j = 0; j < (int)r.size(); j++) {
        if (with[j] == -1) {
            ans.pb(3 * r[j], 2 * r[j]);
        } else {
            ans.pb(2 * l[with[j]] + r[j], l[with[j]] + r[j]);
        }
    }
    cout << ans.size() << "\n";
    for (auto &c : ans) cout << c.fi << " " << c.se << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;
int g[MAXN + 1];
string s;

vector<pair<int, int>> segments; // [l, r]

int get(int k, int i) { // get k-th '1' on [i, |s|)
	--i;
	while (k --> 0) i = s.find('1', i + 1);
	return i;
}

void five() {
	int first = get(1, 0), last = get(5, 0);
	int r = (int)s.size() - 1;
	if (last - first + 1 == 5) { // creating 16: ['001111', '1', '0000']
		segments.emplace_back(0, last - 1);
		segments.emplace_back(last, last);
		if (last < r) segments.emplace_back(last + 1, r);
	} else { // creating 8: cut out '101' or '100' and cut everything in single digits
		int pos = s.find("101");
		if (pos == string::npos) pos = s.find("100");
		for (int i = 0; i < pos; ++i) segments.emplace_back(i, i);
		segments.emplace_back(pos, pos + 2);
		for (int i = pos + 3; i <= r; ++i) segments.emplace_back(i, i);
	}
}

void solve(int l, int r, int k, int n) { // [l; r]
	if (k == n) { // cutting into single digits
		for (int i = l; i <= r; ++i) segments.emplace_back(i, i);

	} else if (k == 2 && n == 3) {
		int pos = get(1, l);
		if (s[pos + 1] == '1') { // ['11', '00...00']
			segments.emplace_back(l, pos + 1);
			if (pos + 2 <= r) segments.emplace_back(pos + 2, r);

		} else { // ['10', '0001', '00000']
			int newpos = get(1, pos + 1);
			segments.emplace_back(l, pos + 1);
			segments.emplace_back(pos + 2, newpos);
			if (newpos + 1 <= r) segments.emplace_back(newpos + 1, r);
		}

	} else if (3 * k / 2 >= n) { // using previous if technique
		int pos = get(2, l);
		solve(l, pos, 2, 3);
		if (k > 2) solve(pos + 1, r, k - 2, n - 3);

	} else if ((k == 4 && n == 8) || (k == 9 && n == 16)) {
		int pos = get(1, l);
		string sub = s.substr(pos, 3);
		segments.emplace_back(l, pos + 2);
		if (sub == "100") solve(pos + 3, r, k - 1, n - 4);
		if (sub == "101") solve(pos + 3, r, k - 2, n - 5);
		if (sub == "110") solve(pos + 3, r, k - 2, n - 6);
		if (sub == "111") solve(pos + 3, r, k - 3, n - 7);

	} else if ((k == 7 && n == 11) || (k == 10 && n == 16)) {
		int mid = get(4, l);
		solve(l, mid, 4, 8);
		solve(mid + 1, r, k - 4, n - 8);

	} else { // common case
		int mid = get(k / 2, l);
		solve(l, mid, k / 2, n / 2);
		solve(mid + 1, r, k - k / 2, n / 2);

	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	g[1] = 1;
	for (int i = 2; i <= MAXN; ++i) g[i] = g[(i + 1) / 2] * 2;
	int T;
	cin >> T;
	while (T --> 0) {
		cin >> s;
		int k = count(s.begin(), s.end(), '1');
		if (!k) {
			cout << -1 << '\n';
			continue;
		}
		segments.clear();
		if (k == 5) five();
		else solve(0, (int)s.size() - 1, k, g[k]);
		cout << segments.size() << '\n';
		for (auto &[l, r] : segments) {
			cout << l + 1 << ' ' << r + 1 << '\n';
		}
	}
	return 0;
}

In this problem it is enough to print $$$n - 3$$$, $$$1$$$, $$$1$$$, $$$1$$$. It is easy to see that this answer is correct for any $$$n \ge 4$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
    }
    return 0;
}

We will use a greedy technique. Let's find the most common element in the array. Let it be $$$x$$$ and let it occur $$$k$$$ times in the array. Then let's make a copy where all elements are $$$x$$$. To do that we can make a copy of the given array and put all $$$x$$$ in one array. Now we will repeat the algorithm for the new array until we get a copy with $$$n$$$ numbers $$$x$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        map<int, int> q;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            ++q[x];
        }
        int am = 0;
        for (auto &[x, y] : q) {
            am = max(am, y);
        }
        int ans = 0;
        while (am < n) {
            int d = min(n - am, am);
            ans += 1 + d;
            am += d;
        }
        cout << ans << '\n';
    }
    return 0;
}

Firstly, we can see that for any two different vertices, their children are independent. It means that infection can not spread from children of one vertex to children of another. Also it does not matter how the infection spreads among the children of some vertex, so we only need to know the amount of vertices with the same parent.

Using this knowledge we can reduce the problem to this one: You are given an array of $$$k$$$ positive integers, each integer denotes the amount of healthy vertices with the same parent. Each second you can infect an integer in this array (by injection). Also each second all infected integers decrease by 1 (because of spreading).

Let's now use a greedy algorithm. We will sort this array in the decreasing order and infect all integers one by one. These injections are always needed because the integers are independent. After that each second all numbers decrease by 1 and we can choose one number to be decreased once more in the same second. This should be the max number.

This problem can be solved by simulating the whole process, because the sum of all integers in the beginning is $$$n$$$.

#include <bits/stdc++.h>
using namespace std;

int ans;

void proc(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    int last = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == a[0]) {
            last = i;
        } else {
            break;
        }
    }
    --a[last];
    for (int i = 0; i < n; ++i) --a[i];
    ++ans;
    while (!a.empty() && a.back() <= 0) {
        a.pop_back();
    }
    proc(a);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        vector<int> a(n);
        ans = 0;
        for (int i = 1; i < n; ++i) {
            int x;
            cin >> x;
            ++a[--x];
        }
        a.emplace_back(1);
        sort(a.rbegin(), a.rend());
        while (!a.empty() && a.back() <= 0) a.pop_back();
        n = a.size();
        for (int i = 0; i < n; ++i) {
            a[i] = a[i] - (n - i);
            ++ans;
        }
        sort(a.rbegin(), a.rend());
        while (!a.empty() && a.back() <= 0) a.pop_back();
        proc(a);
        cout << ans << '\n';
    }
    return 0;
}

Solution 1

Let's iteratively find the remainder of $$$x \bmod$$$ each power of $$$2$$$. Initially, we know that $$$x \bmod 2^0 = x \bmod 1 = 0$$$. If we know that $$$x \bmod 2^k = r$$$, then how do we find $$$x \bmod 2^{k + 1}$$$? To do that let's ask $$$\gcd(x + 2^k - r, 2^{k + 1}) = \gcd(x + 2^k - r, x + 2^k - r + 2^{k + 1})$$$. If $$$\gcd = 2^{k + 1}$$$, then $$$x \bmod 2^{k + 1} = r + 2^{k - 1}$$$ else $$$x \bmod 2^{k + 1} = r$$$. Using this algorithm we will find $$$x \bmod 2^{30}$$$ which is just $$$x$$$. It takes exactly $$$30$$$ queries.

Solution 2

Let's consider a set of pairwise coprime numbers $$${23, 19, 17, 13, 11, 9, 7, 5, 4}$$$. Their $$$\text{lcm} > 10^9$$$ that's why $$$x \bmod \text{lcm} = x$$$. Let's find $$$x \bmod$$$ each of these numbers. To do that, for each $$$1 \le i \le 23$$$ we can ask $$$\gcd(x + i, x + \text{lcm} + i)$$$ (the query is $$$(i, \text{lcm} + i)$$$). If the $$$\gcd$$$ is a multiple of some number from our set then $$$x \bmod$$$ this number is $$$-i$$$. After that we can use the chinese remainder theorem to find $$$x$$$ that gives the same remainders for numbers from the set. This solution asks only $$$23$$$ queries.

Observation 1: It's enough to make only $$$22$$$ queries, because if we did not find anything for $$$1 \le i \le 22$$$ then we can guarantee that $$$i = 23$$$ will do.

Observation 2: All moduli are small, that's why it is possible to use a simplified CRT (check the implementation).

#include<bits/stdc++.h>

using namespace std;

int ask(int a, int b) {
    cout << '?' << " " << a << " " << a + b << endl;
    int ans;
    cin >> ans;
    return ans;
}

void solve() {
    int r = 0;
    for (int i = 1; i <= 30; i++) {
        int ans = ask((1 << (i - 1)) - r, (1 << i));
        if (ans == (1 << i)) r += (1 << (i - 1));
    }
    cout << '!' << " " << r << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define lc 1338557220
 
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll x, rs[maxn], p;
vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
 
ll ask(ll a, ll b) {
    cout << "?" _ a _ b << nf;
    ll x; cin >> x; return x;
}
 
void clm(ll x) {
    cout << "!" _ x << nf;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    /* #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif */
 
    // kudos for automatic wa
 
    cin >> t;
    while (t--) {
        for (i = 1; i <= 23; i++) {
            k = ask(x + i, lc + i);
            for (j = 0; j < 9; j++) {
                if (k % pw[j] == 0) rs[j] = i % pw[j];
            }
        }
 
        k = 1; p = 1;
        for (j = 0; j < 9; j++) {
            // cout << "p =" _ p << nf;
            while (p % pw[j] != rs[j]) p += k;
            k *= pw[j];
        }
 
        clm(lc - p);
    }
 
    return 0;
}

The key idea for the solution is that the answer always lies among no more than 31 minimal numbers. According to this idea, it is possible to build a segment tree for minimum on a segment. After that we only need to find no more than 31 minimums on the segment (each time we find one we change it to $$$\infty$$$) and, finally, we can find all $OR$s pairwise among these 31 numbers.

It is also possible to use the Merge Sort Tree and the same idea.

Now let's prove the key idea: let's prove by induction that if all numbers are less than $$$2^k$$$ then it's enough to consider $$$k + 1$$$ minimal numbers.

Base case: $$$k=1$$$, all numbers are from $$$0$$$ to $$$1$$$ and the proof is obvious.

Inductive step:

Let's show that for any $$$k \ge 1$$$ if for $$$k$$$ the statement is true then it's true for $$$k + 1$$$.

If all numbers have 1 in $$$k$$$-th bit then the $$$k$$$-th bit of the answer is also 1, that's why we only have to minimize the remaining bits. For these bits we can apply the induction hypothesis that $$$k + 1$$$ minimal numbers are enough. If at least two numbers have 0 in their $$$k$$$-th bit then the $$$k$$$-th bit in the answer is also 0. That's why we only consider only numbers with 0 in $$$k$$$-th bit and we have to minimize the remaining bits. Again applying the induction hypothesis, $$$k + 1$$$ minimal numbers are enough. If there is exactly one number with 0 in $$$k$$$-th bit then the $$$k$$$-th bit in the answer is 1 and we have to find $$$k + 1$$$ minimal numbers over $$$k$$$ bits. They are among $$$k + 2$$$ minimal numbers over $$$k + 1$$$ bits, so $$$k + 2$$$ minimal numbers are enough.

#include<bits/stdc++.h>

using namespace std;

const int MAXK = 31;
const int INF = (1 << 30);

vector<pair<int, int>> t;

pair<int, int> get(int v, int vl, int vr, int l, int r) {
    if (vl >= l && vr <= r) return t[v];
    if (r <= vl || l >= vr) return make_pair(INF, INF);
    int vm = (vl + vr) / 2;
    return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
}

void mod(int v, int vl, int vr, int id, int val) {
    if (vr - vl == 1) {
        t[v] = make_pair(val, id);
        return;
    }
    int vm = (vl + vr) / 2;
    if (id < vm) mod(2 * v + 1, vl, vm, id, val);
    else mod(2 * v + 2, vm, vr, id, val);
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    t.resize(4 * n);
    for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        vector<pair<int, int>> b;
        for (int i = 0; i < min(r - l, MAXK); i++) {
            auto now = get(0, 0, n, l, r);
            b.push_back(now);
            mod(0, 0, n, now.second, INF);
        }
        int ans = (1LL << 31) - 1;
        for (int i = 0; i < (int)b.size(); i++) {
            for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first);
        }
        for (auto &c : b) mod(0, 0, n, c.second, c.first);
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}