#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	cout << (n / 10) + (n % 10) << '\n';	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

def f(a, b):
    if (a > b): return 1
    if (a == b): return 0
    if (a < b): return -1
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    ans = 0
    if f(a, c) + f(b, d) > 0:
        ans += 1
    if f(a, d) + f(b, c) > 0:
        ans += 1
    if f(b, c) + f(a, d) > 0:
        ans += 1
    if f(b, d) + f(a, c) > 0:
        ans += 1
    print(ans)

def solve():
    n, s, m = map(int, input().split())
    segs = [[0, 0], [m, m]] + [list(map(int, input().split())) for i in range(n)]
    segs.sort()
    for i in range(1, n + 2):
        if segs[i][0] - segs[i - 1][1] >= s:
            print('YES')
            return
    print('NO')


#sys.stdin = open('in', 'r')
for _ in range(int(input())):
    solve()

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

int main() {
    int test_cases; cin >> test_cases;
    while(test_cases--) {
        string s, t; cin >> s >> t;
    	int idx = 0;
    
    	for(int i = 0; i < (int)s.size(); ++i) {
    		if(s[i] == '?') {
    			if(idx < (int)t.size()) s[i] = t[idx++];
    			else s[i] = 'a';
    		} else if(s[i] == t[idx]) ++idx;
    	}
    	if(idx >= t.size()) cout << "YES\n" << s << "\n";
    	else cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200'007;
const int MOD = 1'000'000'007;

int a[MAX], psum[MAX];

int f(int x) {
	int cnt = 0;
	while (x) {
		x /= 3;
		cnt++;
	}
	return cnt;
}

void solve() {
	int l, r;
	cin >> l >> r;
	cout << psum[r] - psum[l - 1] + a[l] << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	psum[0] = 0;
	for (int i = 1; i < MAX - 1; i++) {
		a[i] = f(i);
		psum[i] = psum[i - 1] + a[i];
	}
	
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

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

const int N = 2e5 + 5, mod = 1e9 + 7;
int64_t fact[N];
int64_t pw(int64_t a, int64_t b) {
	int64_t r = 1;
	while(b > 0) {
		if(b & 1) r = (r * a) % mod;
		b /= 2;
		a = (a * a) % mod; 
	}
	return r;
}
int64_t C(int64_t n, int64_t k) {
	if(n < k) return 0LL;
	return (fact[n] * pw((fact[n - k] * fact[k]) % mod, mod - 2)) % mod;
}
int main() {
	int t; cin >> t;
	fact[0] = 1;
	for(int64_t i = 1; i < N; ++i) fact[i] = (fact[i - 1] * i) % mod;
	while(t--) {
		int n, k; cin >> n >> k;
		vector<int> a(n);
		int ones = 0;
		for(int i = 0; i < n; ++i) {
			cin >> a[i];
			ones += a[i];
		}
		//at least k/2+1 ones
		int64_t ans = 0;
		for(int cnt_ones = k / 2 + 1; cnt_ones <= min(ones, k); ++cnt_ones) {
			ans += C(ones, cnt_ones) * C(n - ones, k - cnt_ones) % mod;
			ans %= mod;
		}
		cout << ans << "\n";
	}
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int l = 2, r = 1000;
	while (l < r) {
		int mid = l + (r - l) / 2;
		cout << "? 1 " << mid << endl;
		int resp; cin >> resp;
		
		if (resp == mid) {
			l = mid + 1;
		} 
		else {
			r = mid;
		}
	}
	cout << "! " << l << endl;	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int l = 1, r = 999;
	while (r - l > 2) {
		int a = (2 * l + r) / 3;
		int b = (2 * r + l) / 3;
		cout << "? " << a << ' ' << b << endl;
		int resp; cin >> resp;
		
		if (resp == (a + 1) * (b + 1)) {
			r = a;
		}
		else if (resp == a * b) {
			l = b;
		}
		else {
			l = a; r = b;
		}
	}
	if (r - l == 2) {
		cout << "? 1 " << l + 1 << endl;
		int resp; cin >> resp;
		
		if (resp == l + 1) {l = l + 1;}
		else {r = l + 1;}
		
	}
	cout << "! " << r << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

Have you seen the "are you a robot" boxes on websites?

1952A - Are You a Robot, Again?

If you select all the squares with traffic lights and read the corresponding letters from left-to-right, top-to-bottom, you get the text "$$$\texttt{print safety}$$$". So all you need to do is print the word $$$\texttt{safety}$$$.

• Based problem
• Based problem
• Based problem

Can you interpret the question in the title another way?

1952B - Is it stated?

You just need to check if there is a substring $$$\texttt{it}$$$ in the string. (That is, the question is asking, "is $$$\texttt{it}$$$ stated?")

• Based problem
• Based problem
• Based problem

They have fooled? Who have fooled?

The image says April. Could it be about April Fools?

The problem has $$$n \leq 12$$$. Where did you see the number $$$12$$$ before?

1952C - They Have Fooled

Looking at the announcement blog, it can be seen that the first April Fools Day Contest was $$$12$$$ years ago.

The problem asks for the problem count of the April Fools Day Contest that was $$$n$$$ years ago.

The sample that has $$$n = 9$$$ is also given as a hint as there was not an April Fools Day Contest on $$$2015$$$.

• Based problem
• Based problem
• Based problem

Are you a procrastinator?

You should be.

What? The checker does not trust you after you say yes? How can you make it believe you?

1952D - Are You a Procrastinator?

The problem asks you if you are procrastinator or not. You should output "yes" (or any other confirmation word that the checker can understand) to solve the problem. However, it does not seem to be enough as the checker responds with "I have no reason to believe you."

You should prove to the checker that you are a procrastinator. You can do this by submitting "yes" in the last $$$15$$$ mins of the contest.

Furthermore, the checker can give different responses depending on your output. Feel free to share what funny responses you got (there are many of them).

• Based problem
• Based problem
• Based problem

Almost everything in this problem is a hint.

The problem name is "Sweep Line". Does it sound familiar?

Look at the quote in the statement. When does a mistake force you to start all over again?

Why are the numbers in the note section are colored?

Why does the note section contain "I had to take a guess." and "I am literally going to explode."

Minesweeper. This is a slightly different version, since all cells are numbered. Why do the numbers only go up to $$$2$$$?

1952E - Sweep Line

The theme of the problem is Minesweeper.

In Minesweeper, the numbers represent the count of mines around them.

The array given in the input represents a Minesweeper game that is only a line (hence the name Sweep Line). The problem asks you to output the number of possible mine placements that is consistent with the given array.

Note that here each cell refers to the number of mines in the neighboring cells, but not including itself (since the input is only up to $$$2$$$).

The modulo $$$20240401$$$ part is unnecessary as the answer can be at most $$$2$$$ (try to prove this).

• Based problem
• Based problem
• Based problem

Can you convert a grid of 0s and 1s into a useful piece of data?

Look in the top-left, top-right, and bottom-left corners. What do you notice?

1952F - Grid

Replace 0 with white and 1 with black to get this QR code:

Scanning it tells you that you need to find the $$$4 \times 4$$$ grid with the maximum sum.

• Based problem
• Based problem
• Based problem

There is a function that has the same name but different definitions in math and computer science. What is it?

Try to fit a curve through the three points given in the problem. It can help you solve the previous question.

1952G - Mathematician Takeover

The problem is a joke about the function $$$\log$$$. For mathematicians, it means $$$\log_e$$$, but for computer scientists, it means $$$\log_2$$$. In particular, the samples all give the correct output for $$$\log_e(x)$$$, but we really want to output $$$\log_2(x)$$$.

• Based problem
• Based problem
• Based problem

Why are there two examples when each one already has multiple test cases?

A change of perspective might help you solve the problem.

1952H - Palindrome

One obvious weird thing in the statement is that there are 2 sample tests despite the multi-test input format. This implies that the lines ("tests") in each input might not be independent tests and are related in some way.

If we read very closely we might notice two weird things about the statement. First, instead of the usual "Each test case contains a line...", it says "The following t lines each contain...". This is because one line does not correspond to one test case. Another is the unusual definition of palindromes: "in both directions".

This problem is solved by seeing it in a different direction. If we read the third and fourth columns, we may notice that they are palindromes — which read the same in both directions, up and down. The solution is to read $$$t$$$ strings, vertically, from the input and determine whether they are palindromes. Empty strings count as palindromes as you can see in sample 2.

• Based problem
• Based problem
• Based problem

Something looks off with the text (literally).

1952I - Dark Matter

If you stare at the PDF hard enough, you'll notice that some of the text looks curved. Given the hint about "gravitational lensing", it should be clear that this is not a coincidence.

How can gravitational lensing distort text? If there's a lot of mass between you and the text, those matter can bend light going from text into your eyes, making straight text look curved. In addition, the meme image looks normal, implying such mass lies between the image and text (in other words, behind the image from your perspective). Here's a visualization of the configuration:

Now let's do the difficult and technical part: finding the dark matter. To do this we need to first grab some PDF/vector graphics editor like LibreOffice or Inkscape. We can see a lot of random objects behind the image:

These are probably the mass causing distorted text. Unfortunately, as the problem suggests, these objects are dark matter so are transparent because they don't interact with light. We can set their transparency to 0 (or opacity to max) and change their color to see them better:

Which gives the formula $$$(a^2 + b^2) + (a - b) + |a| \times 2b - (ab + 2)$$$. If we plug in $$$a$$$ and $$$b$$$ from the samples, we get $$$1$$$, which corresponds to the missing number in the image. Therefore the solution is to output $$$a + b + ((a^2 + b^2) + (a - b) + |a| \times 2b - (ab + 2))$$$.

• Based problem
• Based problem
• Based problem

1952J - Help, what does it mean to be "Based"

Update: You can find checker implementations here.

The recent April Fools contests all have problems related to mysterious languages. In this one, you are given several samples in a new, never been seen before constructed language, and your task is to learn it and solve a simple task with it. The idea of using internet slangs as a language was inspired by this meme. The problem format is similar to some Linguistics Olympiad problems.

This problem is rather straightforward: simply figure out what each line of code does, and try to combine known operations to solve the last task. Knowing the meaning of slangs might help in understanding them.

In task 1, we learn 4 operations:

1. yoink a: Input an integer a.
2. *slaps a on top of b*: Add a to b.
3. yeet b: Output the integer b.
4. go touch some grass: Return/exit the program.

In task 2 we learn:

1. bruh b is lowkey just 0: Assign the variable b to 0.
2. rip this b fell off by a: Subtract a from b.

And the less obvious:

1. vibe check a ratios b: Check if a is larger than b. If yes, execute the next line, otherwise don't.
2. simp for 7: Goto line 7.

In task 3 we learn new things:

1. yoink a: Input an entire array a.
2. Indexing operations: a[0]. We can also see that arrays are 0-indexed.

These are enough to solve task 4. There are two simple approaches.

• Sort the array and output $$$a[k-1]$$$. We may use bubble sort for easier implementation.

yoink n
yoink a
bruh i is lowkey just n
vibe check i ratios 1
simp for 7
simp for 22
bruh j is lowkey just 1
vibe check i ratios j
simp for 11
simp for 20
bruh k is lowkey just j
*slaps -1 on top of k*
vibe check a[k] ratios a[j]
simp for 18
bruh tmp is lowkey just a[j]
bruh a[j] is lowkey just a[k]
bruh a[k] is lowkey just tmp
*slaps 1 on top of j*
simp for 8
rip this i fell off by 1
simp for 4
yoink k
rip this k fell off by 1
yeet a[k]
go touch some grass

• Since the input integers are distinct, we can loop over each element to see whether exactly $$$k-1$$$ elements are smaller than it.

yoink n
yoink a
yoink k
bruh i is lowkey just 0
bruh m is lowkey just 1
bruh j is lowkey just 0
vibe check n ratios j
simp for 10
simp for 13
vibe check a[j] ratios a[i]
*slaps 1 on top of m*
simp for 19
vibe check m ratios k
simp for 21
vibe check k ratios m
simp for 21
yeet a[i]
go touch some grass
*slaps 1 on top of j*
simp for 7
*slaps 1 on top of i*
simp for 5

• Based problem
• Based problem
• Based problem

#include <iostream>

void solve() {
	int a, b, c;
	std::cin >> a >> b >> c;
	if(a < b && b < c) std::cout << "STAIR"<< "\n";
	else if(a < b && b > c) std::cout << "PEAK"<< "\n";
	else std::cout << "NONE" << "\n";
}

int main() {
	int tt; std::cin >> tt;
	while(tt--) 
	    solve();
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		for (int j = 0; j < 2 * n; j++) {
			cout << (i / 2 + j / 2 & 1 ? '.' : '#');
		}
		cout << '\n';
	}	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int h, m; char c;
    cin >> h >> c >> m;
    string am = (h < 12 ? " AM" : " PM");
    h = (h % 12 ? h % 12 : 12);
    cout << (h < 10 ? "0" : "") << h << c << (m < 10 ? "0" : "") << m << am << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100'007;
const int MOD = 1'000'000'007;

vector<int> binary_decimals;

bool ok(int n) {
	if (n == 1) {return true;}
	bool ans = false;
	for (int i : binary_decimals) {
		if (n % i == 0) {
			ans |= ok(n / i);
		}
	}
	return ans;
}

void solve() {
	int n;
	cin >> n;
	cout << (ok(n) ? "YES\n" : "NO\n");	
}

int main() {
	for (int i = 2; i < MAX; i++) {
		int curr = i;
		bool bad = false;
		while (curr) {
			if (curr % 10 > 1) {bad = true; break;}
			curr /= 10;
		}
		if (!bad) {binary_decimals.push_back(i);}
	}
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

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

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i = 1; i <= n; i++)
    {
        if(n%i == 0)
        {
            int satisfy = 2;
            for(int j = 0; j < i; j++)
            {
                for(int k = j+i; k < n; k+=i)
                {
                    if(s[k] != s[j])
                    {
                        satisfy--;
                    }
                }
            }
            if(satisfy > 0)
            {
                cout << i << endl;
                return;
            }
            satisfy = 2;
            for(int j = n-i; j < n; j++)
            {
                for(int k = j-i; k >= 0; k-=i)
                {
                    if(s[k] != s[j])
                    {
                        satisfy--;
                    }
                }
            }
            if(satisfy > 0)
            {
                cout << i << endl;
                return;
            }
        }
    }
}

int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + 1 != c) {cout << -1 << '\n'; return;}
	if (a + b + c == 1) {cout << 0 << '\n'; return;}
	int curr = 1, next = 0, res = 1;
	for (int i = 0; i < a + b; i++) {
		if (!curr) {
	        swap(next, curr);
	        res++;
	    }
	    curr--;
	    next++;
	    if (i < a) {next++;}
	}
	cout << res << '\n';
}

int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

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

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

void solve() {
    int n; cin >> n;
    vector<int> s(n), g(n);
    vector<string> aa(n), bb(n);
    vector<string> vals;
    for(int i = 0; i < n; ++i) {
        string a, b; cin >> a >> b;
        vals.push_back(a);
        vals.push_back(b);
        aa[i] = a, bb[i] = b;
    }
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for(int i = 0; i < n; ++i) {
        s[i] = lower_bound(all(vals), aa[i]) - vals.begin();
        g[i] = lower_bound(all(vals), bb[i]) - vals.begin();
    }
    vector<vector<int>> dp(1 << n, vector<int>(n, 0));
    for(int i = 0; i < n; ++i) dp[1 << i][i] = 1;
    for(int mask = 0; mask < (1 << n); ++mask) {
        for(int lst = 0; lst < n; ++lst) {
            if(!dp[mask][lst]) continue;
            for(int i = 0; i < n; ++i) {
                if(mask >> i & 1) continue;
                if(s[lst] == s[i] || g[lst] == g[i]) {
                    dp[mask | (1 << i)][i] |= dp[mask][lst];
                }
            }
        }
    }
    int ans = 0;
    for(int mask = 0; mask < (1 << n); ++mask) {
        for(int i = 0; i < n; ++i) {
            if(dp[mask][i]) {
                ans = max(ans, __builtin_popcount(mask));
            }
        }
    }
    cout << n - ans << "\n";
}   
 
main() {
    int t = 1; cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200'007;
const int MOD = 1'000'000'007;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200'007;
const int MOD = 1'000'000'007;

void solve() {
	int cnt[3] = {};
	for (int i = 0; i < 9; i++) {
		char c;
		cin >> c;
		if (c != '?') {cnt[c - 'A']++;}
	}	
	for (int i = 0; i < 3; i++) {
		if (cnt[i] < 3) {cout << (char)('A' + i) << '\n';}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

bool is_square(ll x) {
    ll l = 1, r = 1e9;
    while(l <= r) {
        ll mid = l + (r - l) / 2;
        if(mid * mid == x) return true;
        if(mid * mid > x) r = mid - 1;
        else l = mid + 1;
    }      
    return false;  
}
void solve() {
    ll n; cin >> n;
    ll s = 0;
    for(int i = 0, x; i < n; ++i) {
        cin >> x; s += x;
    }
    if(is_square(s)) cout << "YES\n";
    else cout << "NO\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200'007;
const int MOD = 1'000'000'007;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	string res = "";
	while (!s.empty()) {
		int x;
		if (s.back() == 'a' || s.back() == 'e') {x = 2;}
		else {x = 3;}
		
		while (x--) {
			res += s.back();
			s.pop_back();
		}
		res += '.';
	}
	res.pop_back();
	reverse(res.begin(), res.end());
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    map<ll, ll> m;
    ll s = 0;
    m[0] = 1;
    for(int i = 0; i < n; ++i) {
        a[i] *= ((i % 2) ? -1 : 1);
        s += a[i];
        if(m[s]) {
            cout << "YES\n";
            return;
        }
        ++m[s];
    }
    cout << "NO\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
 
int t, n;
 
vector<pair<int, int>> arr;
 
long long ans;
 
ordered_set st;
 
void solve(){
    cin >> n;
 
    arr.assign(n, {});
 
    for(auto &p : arr) cin >> p.second >> p.first;
 
    sort(arr.begin(), arr.end());
 
    ans = 0;
    st.clear();
 
    for(auto p : arr){
        ans += st.size() - st.order_of_key(p.second);
 
        st.insert(p.second);
    }
 
    cout << ans << "\n";
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
 
    cin >> t;
 
    while(t--){
        solve();
    }
}

#include "bits/stdc++.h"

const int64_t inf = 1e18;

void solve() {
    int n, m; std::cin >> n >> m;
    std::vector<std::pair<int, int>> adj[n];
    for(int i = 0; i < m; ++i) {
        int u, v, w; std::cin >> u >> v >> w; --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    std::vector<int> s(n);
    for(int& i: s) std::cin >> i;

    std::vector<std::vector<int64_t>> dist(n, std::vector<int64_t>(1001, inf));
    std::vector<std::vector<bool>> vis(n, std::vector<bool>(1001, false));
    
    dist[0][s[0]] = 0;
    std::priority_queue<std::array<int64_t, 3>> q;
    q.push({0, 0, s[0]});
    while(!q.empty()) {
        int u = q.top()[1], k = q.top()[2];
        q.pop();
        if(vis[u][k] || dist[u][k] == inf) continue;
        vis[u][k] = true;
        for(auto x: adj[u]) {
            int v = x.first, w = x.second;
            int c = std::min(s[v], k);
            if(dist[v][c] > dist[u][k] + 1LL * w * k) {
                dist[v][c] = dist[u][k] + 1LL * w * k;
                q.push({-dist[v][c], v, c});
            }
        }
    }
    int64_t ans = inf;
    for(int k = 1; k <= 1000; ++k) 
        ans = std::min(ans, dist[n - 1][k]);
    std::cout << ans << "\n";
}   
 
int main() {
    std::ios_base::sync_with_stdio(0);std::cin.tie(0);
    int t = 1; std::cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    string s, c = "codeforces";
    cin >> s;
    int ans = 0;
    for(int i = 0; i < 10; i++)
    {
        if(s[i] != c[i])
        {
            ans++;
        }
    }
    cout << ans << endl;
}

int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

void solve()
{
    int n;
    cin >> n;
    int a[n];
    int cnt = 0, ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i] == 0)
        {
            cnt++;
        }
        else
        {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    cout << max(ans, cnt) << endl;
}

int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

#define ll long long

#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()

#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; cin >> n;
    map<string, int> mp;
    mp["00"] = mp["01"] = mp["10"] = mp["11"] = 1e9;
    int ans = 1e9;
    for(int i = 0; i < n; ++i) {
        int x; cin >> x; string s; cin >> s;
        mp[s] = min(mp[s], x);
    }
    if(min(mp["11"], mp["10"] + mp["01"]) > (int)1e6) {
        cout << "-1\n";
    } else {
        cout << min(mp["11"], mp["10"] + mp["01"]) << "\n";
    }
}

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

#include <bits/stdc++.h>

using namespace std;

bool ok(int n, int m) {
	if (n == m) {return true;}
	else if (n % 3 != 0) {return false;}
	else {return (ok(n / 3, m) || ok(2 * n / 3, m));}
}

void solve() {
	int n, m;
	cin >> n >> m;
	cout << (ok(n, m) ? "YES" : "NO") << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl

int n, m;
bool vis[1005][1005];
int a[1005][1005];

int dfs(int i, int j)
{
    vis[i][j] = true;
    int ans = a[i][j];
    if(i != 0 && a[i-1][j] != 0 && !vis[i-1][j])
    {
        ans+=dfs(i-1, j);
    }
    if(i != n-1 && a[i+1][j] != 0 && !vis[i+1][j])
    {
        ans+=dfs(i+1, j);
    }
    if(j != 0 && a[i][j-1] != 0 && !vis[i][j-1])
    {
        ans+=dfs(i, j-1);
    }
    if(j != m-1 && a[i][j+1] != 0 && !vis[i][j+1])
    {
        ans+=dfs(i, j+1);
    }
    return ans;
}

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            vis[i][j] = false;
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(!vis[i][j] && a[i][j] != 0)
            {
                ans = max(ans, dfs(i, j));
            }
        }
    }
    cout << ans << endl;
}

int32_t main(){
    startt
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, m;
	cin >> n >> m;
	int cnt[n + 1];
	for (int i = 1; i <= n; i++) {
		cnt[i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		cnt[u]++;
		cnt[v]++;
	}
	map<int, int> cnts;
	for (int i = 1; i <= n; i++) {
		cnts[cnt[i]]++;
	}
	vector<int> v;
	for (auto p : cnts) {
		v.push_back(p.second);
	}
	sort(v.begin(), v.end());
	if (v.size() == 3) {
		cout << v[1] << ' ' << v[2] / v[1] << '\n';
	}
	else {
		cout << v[0] - 1 << ' ' << v[1] / (v[0] - 1) << '\n';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

long long ans[2000007];
long long a[1500][1500] = {}, curr = 1;

void solve() {
	int n;
	cin >> n;
	cout << ans[n] << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 1; i < 1500; i++) {
		for (int j = i - 1; j >= 1; j--) {
			a[j][i - j] = a[j - 1][i - j] + a[j][i - j - 1] - a[j - 1][i - j - 1] + curr * curr;
			ans[curr] = a[j][i - j];
			curr++;
		}
	}
	
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

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

#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int mod = 1e9 + 7;
void solve() {
    int n, x; cin >> n >> x;
    vector<int> a(n + 1);
    vector<vector<int>> dp(n + 1, vector<int>(1 << 6, 0));
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        for(int mask = 0; mask < (1 << 6); ++mask) {
            dp[i][mask] += dp[i - 1][mask];
            if(dp[i][mask] >= mod) dp[i][mask] -= mod;
            dp[i][mask & a[i]] += dp[i - 1][mask];
            if(dp[i][mask & a[i]] >= mod) dp[i][mask & a[i]] -= mod;
        }
        dp[i][a[i]] = (dp[i][a[i]] + 1) % mod;
    }
    int ans = 0;
    for(int mask = 0; mask < (1 << 6); ++mask) {
        if(__builtin_popcount(mask) == x) {
            ans = (ans + dp[n][mask]) % mod;
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const string s = "codeforces";

void solve() {
	char c;
	cin >> c;
	for (char i : s) {
		if (i == c) {cout << "YES\n"; return;}
	}
	cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int x = 0, y = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'L') {x--;}
		if (s[i] == 'R') {x++;}
		if (s[i] == 'D') {y--;}
		if (s[i] == 'U') {y++;}
		if (x == 1 && y == 1) {cout << "YES\n"; return;}
	}	
	cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int l = 0, r = n - 1, ans = n;
	while (s[l] != s[r] && ans > 0) {l++; r--; ans -= 2;}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long

#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; string s; cin >> n >> s;
    vector<int> cnt(26, 0), p(26, 0);
    for(auto x: s) cnt[x - 'a']++;
    int ans = 0;
    for(auto x: s) {
        --cnt[x - 'a'];
        ++p[x - 'a'];
        int cur = 0;
        for(int i = 0; i < 26; ++i) {
            cur += min(1, cnt[i]) + min(1, p[i]);
        }
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

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

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int> a(n);
        long long sum = 0;
        int negs = 0;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
            if(a[i] < 0) {
                ++negs;
                a[i] = -a[i];
            }
            sum += a[i];
        }
        sort(a.begin(), a.end());
        if(negs & 1) sum -= 2 * a[0];
        cout << sum << "\n";
    }
}

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

int digit_sum(int n) {
    int ret = 0;
    while(n) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}
void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    set<int> s;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        if(a[i] > 9) s.insert(i);
    }
    while(q--) {
        int type; cin >> type;
        if(type == 1) {
            int l, r; cin >> l >> r; --l, --r;
            int lst = l;
            while(!s.empty()) {
                auto it = s.lower_bound(lst);
                if(it == s.end() || *it > r) break;
                a[*it] = digit_sum(a[*it]);
                int paiu = *it;
                s.erase(it);
                if(a[paiu] > 9) s.insert(paiu);
                lst = paiu + 1;
            }
        } else {
            int x; cin >> x; --x;
            cout << a[x] << "\n";
        }
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(0);
	int t; cin >> t;
	while(t--) {
	    solve();
	}
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long

#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n, c, ans = 0; cin >> n >> c;
    priority_queue<int> q;
    for(int i = 1, x; i <= n; ++i) {
        cin >> x;
        q.push(-x - i);
    }
    while(!q.empty()) {
        int x = -q.top(); q.pop();
        if(x > c) break;
        ++ans;
        c -= x;
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<pair<int, int>> a;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a.pb({x+min(i+1, n-i), x+i+1});
    }
    sort(all(a));
    vector<int> pref;
    pref.pb(0);
    for(int i = 0; i < n; i++)
    {
        pref.pb(pref.back()+a[i].fr);
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int new_c = c-a[i].sc;
        int l = 0, r = n;
        int mx = 0;
        while(l <= r)
        {
            int mid = l+r>>1;
            // Calculate price
            int price = pref[mid];
            int now = mid+1;
            if(mid > i)
            {
                price-=a[i].fr;
                now--;
            }
            if(price <= new_c)
            {
                mx = max(now, mx);
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        ans = max(ans, mx);
    }
    cout << ans << endl;
}

int32_t main(){
    startt
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	cout << a[1] << '\n';	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; string s; cin >> n >> s;
    sort(all(s));
    cout << s.back() - 'a' + 1 << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        vector<int> b(a);
        sort(b.begin(), b.end());
        forn(i, n) {
            if (a[i] == b[n - 1])
                cout << a[i] - b[n - 2] << " ";
            else
                cout << a[i] - b[n - 1] << " ";
        }
        cout << endl;
   }
}

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(i == 0 || x != a.back())
        {
            a.push_back(x);
        }
    }
    int num_valley = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if((i == 0 || a[i-1] > a[i]) && (i == a.size()-1 || a[i] < a[i+1]))
        {
            num_valley++;
        }
    }
    if(num_valley == 1)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

ll calc(vector<int>& a) {
    ll zeroes = 0, ans = 0;
    for(int i = sz(a) - 1; i >= 0; --i) {
        if(a[i] == 0) ++zeroes;
        else ans += zeroes;
    }
    return ans;
}
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    ll ans = calc(a);
    forn(i, n) {
        if(a[i] == 0) {
            a[i] = 1;
            ans = max(ans, calc(a));
            a[i] = 0;
            break;
        }
    }
    for(int i = n - 1; i >= 0; --i) {
        if(a[i] == 1) {
            a[i] = 0;
            ans = max(ans, calc(a));
            a[i] = 1;
            break;
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, d;
	long long c;
	cin >> n >> c >> d;
	long long a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, greater<long long>());
	int l = 0, r = d + 2;
	while (l < r) {
		int m = l + (r - l + 1) / 2;
		long long tot = 0;
		int curr = 0;
		for (int i = 0; i < d; i++) {
			if (i % m < n) {tot += a[i % m];}
		}
		if (tot >= c) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	if (l == d + 2) {cout << "Infinity\n"; return;}
	if (l == 0) {cout << "Impossible\n"; return;}
	cout << l - 1 << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 10;
vector<pair<int, int>> adj[N];
set<int> s;
bool ok = true;
int n, a, b;
void dfs1(int u, int par, int x) {
    if(u == b) return;
    s.insert(x);
    for(auto e: adj[u]) {
        int v = e.first, w = e.second;
        if(v == par) continue;
        dfs1(v, u, x ^ w);
    }
}

bool dfs2(int u, int par, int x) {
    if(u != b && s.count(x)) return true;
    for(auto e: adj[u]) {
        int v = e.first, w = e.second;
        if(v == par) continue;
        if(dfs2(v, u, w ^ x)) return true;
    } 
    return false;
}

void solve() {
    s.clear();
    cin >> n >> a >> b; --a, --b;
    forn(i, n) adj[i].clear();
    for(int i = 0; i < n - 1; ++i) {
        int u, v, w; cin >> u >> v >> w; --u, --v;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dfs1(a, -1, 0);
    if(dfs2(b, -1, 0)) cout << "YES\n";
    else cout << "NO\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a + b == c || c + a == b || b + c == a) ? "YES\n" : "NO\n");
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

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

void solve()
{
    int n;
    cin >> n;
    int x[n];
    set<int> a;
    for(int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    for(int i = 0; i < n; i++)
    {
        if(a.find(x[i]) != a.end())
        {
            cout << "NO" << endl;
            return;
        }
        a.insert(x[i]);
    }
    cout << "YES" << endl;
}

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

How do you write a validator for this problem? (Given a grid, check if it is a valid input.)

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	char g[8][8];
	vector<int> r;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> g[i][j];
			if (g[i][j] == 'R') {r.push_back(i);}
		}
	}
	for (int i : r) {
	    bool ok = true;
	    for (int j = 0; j < 8; j++) {
	        if (g[i][j] != 'R') {ok = false; break;}
	    }
	    if (ok) {cout << "R\n"; return;}
	}
	cout << "B\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

vector<int> pairs[1001];
void solve() {
    int n; cin >> n;
    vector<int> id[1001];
    for(int i = 1; i <= n; ++i) {
        int x; cin >> x;
        id[x].push_back(i);
    }
    int ans = -1;
    for(int i = 1; i <= 1000; ++i) {
        for(int j: pairs[i]) {
            if(!id[i].empty() && !id[j].empty()) {
                ans = max(ans, id[i].back() + id[j].back());
            }
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    for(int i = 1; i <= 1000; ++i) {
        for(int j = 1; j <= 1000; ++j) {
            if(__gcd(i, j) == 1) {
                pairs[i].push_back(j);
            }
        }
    }
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<long long> pref;
    pref.push_back(0);
    vector<int> prefmax;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        pref.push_back(pref.back()+x);
        if(i == 0)
        {
            prefmax.push_back(x);
        }
        else
        {
            prefmax.push_back(max(prefmax.back(), x));
        }
    }
    for(int i = 0; i < q; i++)
    {
        int k;
        cin >> k;
        int ind = upper_bound(prefmax.begin(), prefmax.end(), k)-prefmax.begin();
        cout << pref[ind] << " ";
    }
    cout << endl;
}

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

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int q; cin >> q;
    bool otherA = false, otherB = false;
    ll cntA = 0, cntB = 0;
    while(q--) {
        ll d, k; string x; cin >> d >> k >> x;
        for(auto c: x) {
            if(d == 1) {
                if(c != 'a') otherA = 1;
                else cntA += k;
            } else {
                if(c != 'a') otherB = 1;
                else cntB += k;
            } 
        }
        if(otherB) {
            cout << "YES\n";
        } else if(!otherA && cntA < cntB) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    //we care at most about first log2(a) values
    int cur_or = 0;
    vector<bool> vis(n, false);
    for(int i = 0; i < min(31, n); ++i) {
        int mx = 0, idx = -1;
        for(int j = 0; j < n; ++j) {
            if(vis[j]) continue;
            if((cur_or | a[j]) > mx) {
                mx = (cur_or | a[j]);
                idx = j;
            }
        }
        vis[idx] = true;
        cout << a[idx] << " ";
        cur_or |= a[idx];
    }
    forn(i, n) if(!vis[i]) cout << a[i] << " ";
    cout << '\n';
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

1722A - Spell Check

Check if the string has length 5 and if it has the characters $$$\texttt{T}, \texttt{i}, \texttt{m}, \texttt{u}, \texttt{r}$$$. The complexity is $$$\mathcal{O}(n)$$$.

You can also sort the string, and check if it is $$$\texttt{Timur}$$$ when sorted (which is $$$\texttt{Timru}$$$).

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    string name = "Timur";
    sort(name.begin(), name.end());

    int n;
    cin >> n;
    forn(i, n) {
        int m;
        cin >> m;
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        cout << (s == name ? "YES" : "NO") << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'R') {
			if (t[i] != 'R') {cout << "NO\n"; return;}
		}
		else {
			if (t[i] == 'R') {cout << "NO\n"; return;}
		}
	}
	cout << "YES\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	map<string, int> mp;
	string a[3][n];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			mp[a[i][j]]++;
		}
	}
	for (int i = 0; i < 3; i++) {
		int tot = 0;
		for (int j = 0; j < n; j++) {
			if (mp[a[i][j]] == 1) {tot += 3;}
			else if (mp[a[i][j]] == 2) {tot++;}
		}
		cout << tot << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	long long tot = 0;
	vector<long long> v;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'L') {
			v.push_back((n - 1 - i) - i);
			tot += i;
		}
		else {
			v.push_back(i - (n - 1 - i));
			tot += n - 1 - i;
		}
	}
	sort(v.begin(), v.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		if (v[i] > 0) {tot += v[i];}
		cout << tot << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

You can read about 2D prefix sums if you haven't heard of them before.

#include <bits/stdc++.h>

using namespace std;

long long a[1005][1005];
long long pref[1005][1005];

void solve()
{
    long long n, q;
    cin >> n >> q;
    for(int i = 0; i <= 1001; i++)
    {
        for(int j = 0; j <= 1001; j++)
        {
            a[i][j] = pref[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++)
    {
        long long h, w;
        cin >> h >> w;
        a[h][w]+=h*w;
    }
    for(int i = 1; i <= 1000; i++)
    {
        for(int j = 1; j <= 1000; j++)
        {
            pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
        }
    }
    for(int i = 0; i < q; i++)
    {
        long long hs, ws, hb, wb;
        cin >> hs >> ws >> hb >> wb;
        cout << pref[hb-1][wb-1]-pref[hb-1][ws]-pref[hs][wb-1]+pref[hs][ws] << endl;
    }
}
 
int main() {
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

const int dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1};

void solve() {
	int n, m;
	cin >> n >> m;
	char g[n][m];
	int id[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
			id[i][j] = 0;
		}
	}
	int curr = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] == '*') {
				vector<pair<int, int>> adjh, adjv;
				if (i > 0 && g[i - 1][j] == '*') {
					adjh.emplace_back(i - 1, j);
				}
				if (i < n - 1 && g[i + 1][j] == '*') {
					adjh.emplace_back(i + 1, j);
				}
				if (j > 0 && g[i][j - 1] == '*') {
					adjv.emplace_back(i, j - 1);
				}
				if (j < m - 1 && g[i][j + 1] == '*') {
					adjv.emplace_back(i, j + 1);
				}
				if (adjh.size() == 1 && adjv.size() == 1) {
					if (id[i][j] == 0) {id[i][j] = curr;}
					else {cout << "NO\n"; return;}
					if (id[adjh[0].first][adjh[0].second] == 0) {id[adjh[0].first][adjh[0].second] = curr;}
					else {cout << "NO\n"; return;}
					if (id[adjv[0].first][adjv[0].second] == 0) {id[adjv[0].first][adjv[0].second] = curr;}
					else {cout << "NO\n"; return;}
					curr++;
				}
				else if (adjh.size() > 1 || adjv.size() > 1) {
					cout << "NO\n"; return;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] == '*') {
				if (id[i][j] == 0) {cout << "NO\n"; return;}
				else {
					for (int x = 0; x < 3; x++) {
						for (int y = 0; y < 3; y++) {
							if (0 <= i + dx[x] && i + dx[x] < n) {
								if (0 <= j + dy[y] && j + dy[y] < m) {
									if (id[i + dx[x]][j + dy[y]] != id[i][j] && id[i + dx[x]][j + dy[y]] != 0) {
										cout << "NO\n"; return;
									}
								}
							}
						}
					}
				}
			}
		}
	}
	cout << "YES\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

Output the integers from $$$1$$$ to $$$n-3$$$, then $$$2^{29}$$$, $$$2^{30}$$$, and the XOR of those $$$n-1$$$ numbers. Why does it work?

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    int case1 = 0;
    int case2 = 0;
    for(int i = 0; i < n-2; i++)
    {
        case1^=i;
        case2^=(i+1);
    }
    long long addLast = ((long long)1<<31)-1;
    if(case1 != 0)
    {
        for(int i = 0; i < n-2; i++)
        {
            cout << i << " ";
        }
        case1^=addLast;
        cout << addLast << " " << case1 << endl;
    }
    else
    {
        for(int i = 1; i <= n-2; i++)
        {
            cout << i << " ";
        }
        case2^=addLast;
        cout << addLast << " " << case2 << endl;
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	string s;
	cin >> s;
	if (s[0] != 'y' && s[0] != 'Y') {cout << "NO\n";}
	else if (s[1] != 'e' && s[1] != 'E') {cout << "NO\n";}
	else if (s[2] != 's' && s[2] != 'S') {cout << "NO\n";}
	else {cout << "YES\n";}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	bool vis[26] = {};
	int res = 0;
	for (char c : s) {
		if (!vis[c - 'A']) {res += 2; vis[c - 'A'] = true;}
		else {res++;}
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        if(b == 0)
        {
            continue;
        }
        string now;
        cin >> now;
        for(int j = 0; j < b; j++)
        {
            if(now[j] == 'U'){a[i]--;}
            else if(now[j] == 'D'){a[i]++;}
            if(a[i] < 0){a[i]+=10;}
            if(a[i] > 9){a[i]-=10;}
        }
    }
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
 
int main(){
    int t;
    cin>> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s[n];
	map<string, bool> mp;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		mp[s[i]] = true;
	}
	for (int i = 0; i < n; i++) {
		bool ok = false;
		for (int j = 1; j < s[i].length(); j++) {
			string pref = s[i].substr(0, j), suff = s[i].substr(j, s[i].length() - j);
			if (mp[pref] && mp[suff]) {ok = true;}	
		}
		cout << ok;
	}
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int a[n][n];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            char c;
            cin >> c;
            a[i][j] = c-'0';
        }
    }
    int ans = 0;
    for(int i = 0; i < (n+1)/2; i++)
    {
        for(int j = 0; j < n/2; j++)
        {
            int nowi = i, nowj = j;
            int oldnowj = nowj;
            int sum = a[nowi][nowj];
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            oldnowj = nowj;
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            oldnowj = nowj;
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            ans+=min(sum, 4-sum);
        }
    }
    cout << ans << endl;
}
 
int main(){
    int t;
    cin>> t;
    while(t--)
    {
        solve();
    }
    return 0;
} 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	int a[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	long long res = 0;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		if (a[i] >= i) {continue;}
		res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
		v.push_back(i);
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    long long ans = 0;
    long long sum = 0;
    for(int i = -1; i < n; i++)
    {
        long long now = sum;
        for(int j = i+1; j < min(n, i+32); j++)
        {
            int copy = a[j];
            copy>>=j-i;
            now+=copy;
        }
        ans = max(ans, now);
        if(i+1 != n)
        {
            sum+=a[i+1]-k;
        }
    }
    cout << ans << endl;
}
 
int main(){
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

$$$k \oplus k = 0$$$.

162159711

162158539

What happens when two consecutive piles are increased?

162159774

162158852

What happens if there exist $$$i, j, k$$$ such that $$$a_i + a_j + a_k > a_{max}$$$?

162159874

Binary search.

162159950

162684743

When can you make $$$a$$$ into $$$b$$$?

To swap $$$a_i$$$ with $$$i$$$, we need a strength of at least $$$a_i - i$$$. Is it enough?

The minimum strength needed is $$$\max_{i=1}^n a_i - b_i$$$. How can we count the number of solutions?

162159984

What's an invariant of the array?

162160016

Polynomials!

162160053

t = int(input())
for test in range(t):
    a,b,c,d = map(int, input().split())
    rs = (b > a) + (c > a) + (d > a)
    print(rs)

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

void solve()
{
	int n, x;
	cin >> n;
	set<int> a;
	for(int i = 0; i < n; i++)
	{
		cin >> x;
		a.insert(x);
	}
	if((n-a.size())%2 == 0)
	{
		cout << a.size() << endl;
	}
	else
	{
		cout << a.size()-1 << endl;
	}
}

int32_t main(){
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
	char g[9][9];
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 2; i <= 7; i++) {
		for (int j = 2; j <= 7; j++) {
			if (g[i][j] == '#' && g[i - 1][j - 1] == '#' && g[i - 1][j + 1] == '#' && g[i + 1][j - 1] == '#' && g[i + 1][j + 1] == '#') {
				cout << i << ' ' << j << '\n'; return;
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

#include <bits/stdc++.h>

using namespace std;

int a[5] = {600, 60, 0, 10, 1};
int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412};

void solve() {
	string s;
	cin >> s;
	int x;
	cin >> x;
	int tot = 0;
	for (int i = 0; i < 5; i++) {
		tot += (int)(s[i] - '0') * a[i];
	}
	set<int> t;
	for (int i = 0; i < 2022; i++) {
		t.insert(tot);
		tot += x;
		tot %= 1440;
	}
	int res = 0;
	for (int i : t) {
		for (int j = 0; j < 16; j++) {
			if (good[j] == i) {res++;}
		}
	}
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()


ll query(int l, int r, vector<ll>& p) {
    return p[r] - (l ? p[l - 1] : 0);
}

void solve() {  
    int n, s; cin >> n >> s;
    vector<ll> a(n), p(n);
    forn(i, n) {
        cin >> a[i];
        p[i] = a[i];
        if(i) p[i] += p[i - 1];
    }

    int ans = INT_MAX;

    for(int i = 0; i < n; ++i) {
        int l = i, r = n - 1, pos = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(query(i, mid, p) <= s) {
                pos = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        if(pos == -1 || query(i, pos, p) != s) continue;
        ans = min(ans, n - (pos - i + 1));
    }

    cout << (ans == INT_MAX ? -1 : ans) << "\n";
} 
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}   

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	int cnt[10] = {};
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		cnt[x % 10]++;
	}
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < min(cnt[i], 3); j++) {
			v.push_back(i);
		}	
	}
	int m = v.size();
	for (int i = 0; i < m; i++) {
		for (int j = i + 1; j < m; j++) {
			for (int k = j + 1; k < m; k++) {
				if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;}
			}
		}
	}
	cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}  

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, k;
	cin >> n >> k;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ok[n];
	for (int i = 0; i < n - 1; i++) {
		ok[i] = (a[i] < 2 * a[i + 1]);
	}
	int tot = 0;
	for (int i = 0; i < k; i++) {
		tot += ok[i];
	}
	int res = 0;
	if (tot == k) {res++;}
	for (int i = k; i < n - 1; i++) {
		tot += ok[i];
		tot -= ok[i - k];
		if (tot == k) {res++;}
	}
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
struct DynamicMaxSubarraySum {
    struct node {
        ll pref, suf, val, sum;
    };  
    int N;
    ll neutral;
    vector<node> t;
    DynamicMaxSubarraySum(int _N, ll assign_value) {
        neutral = assign_value;
        N = _N;
        t.resize(4 * N);
        forn(i, 4 * N) t[i] = {0, 0, 0, 0};
        build(1, 0, N - 1); 
    }
    void build(int i, int l, int r) {
        if(l == r) {
            t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral;
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    node merge(node a, node b) {
        node c;
        c.pref = max(a.pref, a.sum + b.pref);
        c.suf = max(b.suf, b.sum + a.suf);
        c.val = max({a.val, b.val, a.suf + b.pref});
        c.sum = a.sum + b.sum;
        return c;
    }
 
    void modif(int i, int l, int r, int pos, ll val) {
        if(l > pos || r < pos) return;
        if(l == pos && r == pos) {
            t[i].pref = t[i].suf = t[i].val = t[i].sum = val;
            return;
        }
        int mid = (l + r) >> 1;
        modif(2 * i, l, mid, pos, val);
        modif(2 * i + 1, mid + 1, r, pos, val);
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    node query(int i, int l, int r, int tl, int tr) {
        if(l > tr || r < tl) return {0, 0, 0, 0};
        if(l >= tl && r <= tr) return t[i];
        int mid = (l + r) >> 1;
        return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
    }
 
    void modif(int pos, int val) {
        modif(1, 0, N - 1, pos, val);
    }
    node query(int l, int r) {
        return query(1, 0, N - 1, l, r);
    }
    node query(int pos) {
        return query(1, 0, N - 1, pos, pos);
    }
};
 
void solve() {  
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    map<int, vector<int>> vv;
    forn(i, n) {
        vv[a[i]].pb(i);
    }
    DynamicMaxSubarraySum st(n, -1);
 
    ll mx = 0, ans = -1;
    for(auto i: vv) {
        vector<int> v = i.second;
        for(auto x: v) st.modif(x, 1);
        if(mx < st.query(0, n - 1).val) {
            ans = i.first;
            mx = st.query(0, n - 1).val;
        }
        for(auto x: v) st.modif(x, -1);
    }  
    int ansl = -1, ansr = -1;
    for(int i = 0; i < n; ++i) {
        if(a[i] == ans) a[i] = 1;
        else a[i] = -1;
    }
    ll sum = 0, lastl = 0;
    mx = 0;
    for(int i = 0; i < n; ++i) {
        sum += a[i];
        if(sum > mx) {
            mx = sum;
            ansr = i;
            ansl = lastl;
        }
        if(sum <= 0) {
            lastl = i + 1;
            sum = 0;
        }
    }
 
    cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n"; 
}   
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

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

int main() {
    int t; cin >> t;
    while(t--) {
        int x; cin >> x;
        if(x < 1400) cout << "Division 4\n";
        else if(x < 1600) cout << "Division 3\n";
        else if(x < 1900) cout << "Division 2\n";
        else cout << "Division 1\n";
    }
}

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


int main() {
	int t; cin >> t;
	while(t--) {
	    int n; cin >> n;
    	vector<int> cnt(n + 1, 0);
    	int ans = -1;
    	for(int i = 0; i < n; i++) {
    		int x; cin >> x;
    		if(++cnt[x] >= 3) {
    			ans = x;
    		}
    	}
    	cout << ans << endl;
	}
}

#include "bits/stdc++.h"
using namespace std;
 
int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int> a(n);

        int even1 = 0, even2 = 0, odd1 = 0, odd2 = 0;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
            if(i % 2 == 0) {
                if(a[i] % 2 == 1) odd1 = 1;
                else even1 = 1; 
            } else {
                if(a[i] % 2 == 1) odd2 = 1;
                else even2 = 1;
            }
        }

        if(even1 && odd1) {
            cout << "NO\n";
        } else if(even2 && odd2) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}

for i in range(int(input())):
    n = int(input())
    l = input().split('W')
    bad = False
    for s in l:
    	b1 = 'R' in s
    	b2 = 'B' in s
    	if (b1 ^ b2):
    		bad = True
    print("NO" if bad else "YES")

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

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;

        vector<vector<int>> cnt(12, vector<int>(12, 0));
        long long ans = 0;
        
        for(int i = 0;i < n; ++i) {
            string s; cin >> s;
            for(int j = 0;j < 2; ++j) {
                for(char c = 'a'; c <= 'k'; ++c) {
                    if(c == s[j]) continue;
                    string a = s; a[j] = c;
                    ans += cnt[a[0] - 'a'][a[1] - 'a'];
                }
            }
            ++cnt[s[0] - 'a'][s[1] - 'a'];
        }
        cout << ans << "\n";
    }
}

t = int(input())
for test in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    l = 0
    r = n - 1
    suml = a[0]
    sumr = a[n-1]
    ans = 0
    while l < r:
        if suml == sumr:
            ans = max(ans, l + 1 + n - r)

        if suml <= sumr:
            l+=1
            suml+=a[l]

        elif sumr < suml:
            r-=1
            sumr+=a[r]
            
    print(ans)

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, m;
	cin >> n >> m;
	char g[n + 7][m + 7];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
		}
	}
	for (int j = 0; j < m; j++) {
		int last = n - 1;
		for (int i = n - 1; i >= 0; i--) {
			if (g[i][j] == 'o') {last = i - 1;}
			else if (g[i][j] == '*') {swap(g[i][j], g[last][j]); last--;}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << g[i][j];
		}
		cout << '\n';
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

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

int main() {
    int t; cin >> t;
    while(t--) {
        int n, k; cin >> n >> k;
        vector<int> cnt(31, 0), a(n);
        for(int i = 0;i < n; ++i) {
            cin >> a[i];
            for(int j = 30; j >= 0; --j) {
                if(a[i] & (1 << j)) ++cnt[j];
            }
        }
        int ans = 0;
        for(int i = 30; i >= 0; --i) {
            int need = n - cnt[i];
            if(need <= k) {
                k -= need;
                ans += (1 << i);
            }
        }
        cout << ans << "\n";
    }
}

127991325

Link to Video

127991329

Link to Video

127991331

Link to Video

There exists a dynamic programming solution to this problem. Let $$$x$$$ be the length (number of digits) of $$$n$$$, and $$$dp_{i,j,k}$$$ be the number of pairs of integers $$$(x,y)$$$ that add up to the digits from position $$$i$$$ to $$$x-1$$$ ($$$0$$$-indexed), with $$$j$$$ carried over from the addition one place to the right, and $$$k$$$ carried over from the addition at position $$$i$$$. Notice that $$$0 \le j,k \le 1$$$, as the maximum addition value with carry in a single digit's place is $$$19$$$, and thus the maximum carry value is $$$\lfloor \frac{19}{10} \rfloor = 1$$$.

Now, we can iterate from rightmost digit to leftmost, i.e. from digit $$$x-1$$$ to $$$0$$$. We can further iterate over all pairs of digits in the addition for the current column, as well as the carry values from both one and two columns to the right, and thus, we can find the number of states that contribute to our current state.

Our answer can be found in $$$dp_{0,0,0}$$$, however, we must subtract $$$2$$$ from this as it includes the invalid pairs $$$(0,n)$$$ and $$$(n,0)$$$.

127990386

127991334

Link to Video

127990755

Link to Video

127991337

Link to Video

The value of $$$k$$$ is irrelevant, just output the answer when zero operations are performed.

If we perform $$$0$$$ operations on the array, then the answer is just $$$\max{(a_i)} - \min{(a_i)}$$$ (maximum element of $$$a$$$ minus minimum element of $$$a$$$). Call this value $$$r$$$. Now we claim that, no matter how many operations are performed on the array, the answer will always be $$$r$$$. Let's prove it.

Let $$$s$$$ be the sum of the elements of the array. Then the operation is equivalent to turning $$$a_i$$$ into $$$s - a_i$$$ for all $$$i$$$. In particular, let $$$a_p$$$ be the maximum element and $$$a_q$$$ be the minimum element of $$$a$$$. Then after the operation, $$$a_p$$$ becomes $$$s - a_p$$$ and $$$a_q$$$ becomes $$$s - a_q$$$. It's easy to see that $$$s - a_p$$$ will be the smallest number of the resulting array, and $$$s - a_q$$$ will be the largest number of the resulting array. Therefore, after the operation, the maximum difference between two numbers is $$$s - a_q - (s - a_p) = a_p - a_q$$$, which is equal to the answer for the initial array.

Therefore the answer is independent of $$$k$$$. The solution goes as follows: find the minimum and maximum of $$$a$$$, and then find their difference. This runs in $$$\mathcal{O}(n)$$$ per test case.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
    int n, k;
    cin >> n >> k;
    int a[n + 7], mn = MOD, mx = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    cout << mx - mn << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

We can solve the one-dimensional version using a DP (or just iterating), so solve the two-dimensional version using by splitting the grid into vertical and horizontal segments that don't interact.

First, let's solve the one-dimensional problem, where the only characters are $$$\texttt{<}$$$ and $$$\texttt{>}$$$. In this case, there is a brute-force solution that swaps two arrows whenever it can, but this runs in $$$\mathcal{O}(n^2)$$$. Unfortunately, I intended to make this fail, but it looks like I didn't. I apologize for this.

To solve this problem in $$$\mathcal{O}(n)$$$, we will use dynamic programming. Let $$$a_i$$$ be the maximum number of swaps that can be performed first $$$i$$$ characters of the string. Let's also keep track of the number of right arrows we've seen so far in a variable $$$rt$$$. Initially $$$a_0 = 0$$$ and $$$rt = 0$$$. Then, iterate through the string from left to right:

• If $$$s_i = \texttt{>}$$$, then $$$a_i = a_{i-1}$$$ and $$$rt = rt + 1$$$.

• If $$$s_i = \texttt{<}$$$, then $$$a_i = a_{i-1} + rt$$$.

This DP works since each left arrow can move as many times as the number of right arrows it is pointing at.

Now we return to the two-dimensional case. For each square, let's split the grid into multiple components: if the arrow is $$$\texttt{<}$$$ or $$$\texttt{>}$$$, then we will keep moving horizontally until we hit a $$$\texttt{v}$$$ or $$$\texttt{^}$$$ arrow. Similarly, if the arrow is $$$\texttt{v}$$$ or $$$\texttt{^}$$$, then we will keep moving vertically until we hit a $$$\texttt{<}$$$ or $$$\texttt{>}$$$ arrow. This works, because horizontal arrows will never interact with vertical ones, and vertical arrows will never interact with horizontal ones.

For example, the above process results in the following components in the first test case.

Now we can just solve each component individually, and add the answers. This runs in $$$\mathcal{O}(mn)$$$.

An implementation note: we don't actually need a DP array to solve each component; instead, you can just keep track of two variables $$$ans$$$ and $$$rt$$$.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

bool lr(char c) {
    return (c == '<' || c == '>'); 
}

void solve() {
    int n, m;
    cin >> n >> m;
    char c[n + 7][m + 7];
    bool vis[n + 7][m + 7];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
            vis[i][j] = false;
        }
    }
    long long res = 0, curr, cnt;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            curr = 0;
            cnt = 0;
            if (!vis[i][j]) {
                int x = i, y = j;
                if (lr(c[i][j])) {
                    while (x < n && y < m && lr(c[x][y])) {
                        vis[x][y] = true;
                        if (c[x][y] == '<') {curr += cnt;}
                        else {cnt++;}
                        y++;
                    }
                }
                else {
                    while (x < n && y < m && !lr(c[x][y])) {
                        vis[x][y] = true;
                        if (c[x][y] == '^') {curr += cnt;}
                        else {cnt++;}
                        x++;
                    }
                }
            }
            res += curr;
        }
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

We can't swap two letters if they are already sorted.

The key insight is this: let $$$c_1$$$ and $$$c_2$$$ be two characters such that $$$c_1$$$ comes before $$$c_2$$$ in the alphabet and $$$c_1$$$ comes before $$$c_2$$$ in the input string $$$s$$$. Then it is impossible to swap $$$c_1$$$ and $$$c_2$$$. We can prove this by noticing that any operation that contains both $$$c_1$$$ and $$$c_2$$$ will never swap them, since $$$c_1 < c_2$$$ and the operation always sorts the substring picked. On the other hand, if two characters are not sorted, then we can sort them easily using the operation.

Let's look at all pairs of characters in $$$\texttt{ezpc}$$$ such that the first is greater than the second. These pairs are $$$(\texttt{e}, \texttt{c})$$$, $$$(\texttt{z}, \texttt{p})$$$, $$$(\texttt{z}, \texttt{c})$$$, $$$(\texttt{p}, \texttt{c})$$$. If any of these pairs are in the wrong order in $$$s$$$, then we will be unable to swap them. This means that the string cannot be easy. On the other hand, if all of these pairs are in the right order, then we can always make the string easy.

Therefore the solution is just to look for the positions of $$$\texttt{e}$$$, $$$\texttt{z}$$$, $$$\texttt{p}$$$, and $$$\texttt{c}$$$ in $$$s$$$, and check if any of the following are true: $$$pos_e > pos_c$$$, $$$pos_z > pos_p$$$, $$$pos_z > pos_c$$$, $$$pos_p > pos_c$$$. If any of them are true, then the answer is $$$\texttt{NO}$$$. Otherwise, the answer is $$$\texttt{YES}$$$. This runs in $$$\mathcal{O}(1)$$$ per test case, since the length of $$$s$$$ is fixed.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	string s;
	cin >> s;
	int epos, zpos, ppos, cpos;
	for (int i = 0; i < 26; i++) {
	    if (s[i] == 'e') {epos = i;}
	    if (s[i] == 'z') {zpos = i;}
	    if (s[i] == 'p') {ppos = i;}
	    if (s[i] == 'c') {cpos = i;}
	}
	if (cpos < epos || ppos < zpos || cpos < zpos || cpos < ppos) {
	    cout << "NO" << endl;
	}
	else {
	    cout << "YES" << endl;
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

The maximum distance the center can move is $$$\lfloor \frac{n}{2} \rfloor \sqrt{2}$$$. We can make a construction for this value of $$$d$$$.

First notice that if we have a construction for some $$$d$$$, then we have a construction for all $$$d' < d$$$ (since all points move at least $$$d'$$$).

Notice that maximum distance the center point (or any of the center points, if $$$n$$$ is even) can move in an $$$n \times n$$$ grid is $$$\lfloor \frac{n}{2} \rfloor \sqrt{2}$$$, which can be shown through casework on whether $$$n$$$ is even or odd. Therefore, if $$$d > \lfloor \frac{n}{2} \rfloor^2 \cdot 2$$$, then the answer is $$$\texttt{NO}$$$.

Otherwise, the answer is $$$\texttt{YES}$$$. As mentioned before, we only need to find a construction when each point moves at least $$$\lfloor \frac{n}{2} \rfloor \sqrt{2}$$$ units. If $$$n$$$ is even, we can use the construction below:

If $$$n$$$ is odd, then we can move all the points in the lower-left $$$(n-1) \times (n-1)$$$ grid as before, and move the remaining points as shown:

It's easy to see that this will indeed satisfy the conditions. This runs in $$$\mathcal{O}(n^2)$$$ per test case (for output).

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void f(int x, int y) {
	cout << x << ' ' << y << ' ';
}

void solve() {
	int n, d;
	cin >> n >> d;
	if (d > (n / 2) * (n / 2) * 2) {cout << "NO" << endl; return;}
	cout << "YES" << endl;
	for (int i = 1; i <= n / 2; i++) {
		for (int j = 1; j <= n / 2; j++) {
			f(i, j); f(i + n/2, j + n/2); cout << endl;
			f(i + n/2, j + n/2); f(i, j); cout << endl;
		}
	}
	for (int i = 1; i <= n / 2; i++) {
		for (int j = n / 2 + 1; j <= (n / 2) * 2; j++) {
			f(i, j); f(i + n/2, j - n/2); cout << endl;
			f(i + n/2, j - n/2); f(i, j); cout << endl;
		}
	}
	if (n % 2) {
		f(1, n); f(n, n); cout << endl;
		f(n, n); f(n, 1); cout << endl;
		f(n, 1); f(1, n); cout << endl;
		for (int i = 2; i <= n - 1; i++) {
			f(i, n); f(n, n + 1 - i); cout << endl;
			f(n, n + 1 - i); f(i, n); cout << endl;
		}
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

The answer is $$$\texttt{YES}$$$ if and only if $$$t$$$ contains the character $$$\texttt{o}$$$.

First, if the resulting string $$$t$$$ doesn't have the character $$$\texttt{o}$$$, then the answer is $$$\texttt{NO}$$$, since after every operation the resulting string must have a character equal to $$$\texttt{o}$$$.

Otherwise, we claim the answer is $$$\texttt{YES}$$$. Suppose that $$$t$$$ has a character $$$\texttt{o}$$$ at position $$$i$$$. Then the first operation should make $$$s_i = \texttt{o}$$$ (and change any other character). Afterwards, we can make $$$s_i = \texttt{o}$$$ and, one by one, make all the characters in $$$s$$$ match $$$t$$$. (Formally, make $$$s_i = \texttt{o}$$$ and $$$s_j = t_j$$$ for all $$$1 \leq j \leq n$$$, $$$i \neq j$$$.)

This runs in $$$\mathcal{O}(n)$$$ per test case.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	for (char c : t) {
		if (c == 'o') {cout << "YES" << endl; return;}
	}
	cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

A string with all the same character has the most palindromic substrings, so we can use many of these side by side to make a total of exactly $$$n$$$ palindromic substrings.

The idea is to use triangular numbers: the string $$$\texttt{aaa}...\texttt{aaa}$$$ with length $$$\ell$$$ has exactly $$$\binom{\ell + 1}{2}$$$ palindromic substrings. Therefore it suffices to find some triangular numbers that add up to exactly $$$n$$$.

To do this, we can greedily choose the largest triangular number less than $$$n$$$. It can be checked that the length of the string will be at most $$$300$$$ for the given constraints.

Alternatively, by Gauss's Eureka Theorem, we only need to express $$$n$$$ as the sum of three triangular numbers. We can just brute force the three triangular numbers and find the answer for each $$$n$$$.

This runs in $$$\mathcal{O}(n\sqrt{n})$$$ per test case if you lazily brute force, or $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(\sqrt{n})$$$ per test case if you use some math to find the next smallest triangular number or use precomputation.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	char curr = 'a';
	int it = 0;
	while (n > 0) {
		int now = 0;
		while (((now + 1) * (now + 2)) / 2 <= n) {now++;}
		cout << string(now, ('a' + it));
		n -= (now * (now + 1)) / 2;
		it++;
	}
	cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

Brute force small $$$n$$$ and find a pattern.

Here is a rough idea: for large $$$n$$$, the smallest number we can make by turning on segments should have a lot of $$$8$$$s at the end (since $$$8$$$ has the most segments), and the largest number we can make should have a lot of $$$1$$$s at the end (since $$$1$$$ has the fewest segments, so we can put more of them next to each other).

Therefore, the intended solution goes as follows: write a brute force for small $$$n$$$ ($$$n \leq 30$$$, say), and find the smallest and largest numbers after turning on $$$n$$$ segments. We know that these sequences should be periodic, as per the idea above, and in fact they are. The cases are as follows:

• For the largest number you can make, the pattern is $$$1$$$, $$$7$$$, $$$11$$$, $$$71$$$, $$$111$$$, $$$711$$$, $$$1111$$$, $$$7111$$$, and so on. You can see how there are lots of ones at the end of the numbers, and the prefixes start repeating eventually.
• For the smallest number you can make, the pattern is $$$1$$$, $$$7$$$, $$$4$$$, $$$2$$$, $$$6$$$, $$$8$$$, $$$10$$$, $$$18$$$, $$$22$$$, $$$20$$$, $$$28$$$, $$$68$$$, $$$88$$$, $$$108$$$, $$$188$$$, $$$200$$$, $$$208$$$, $$$288$$$, $$$688$$$, $$$888$$$, $$$1088$$$, $$$1888$$$, $$$2008$$$, $$$2088$$$, $$$2888$$$, $$$6888$$$, $$$8888$$$, $$$10888$$$, and so on. You can see how there are lots of eights at the end of the numbers, and the prefixes start repeating eventually.

This runs in $$$\mathcal{O}(n)$$$ time per test case.

I know this problem might get some criticism for being too bashy or trivialized by brute force, but I think brute forcing is an important skill to have (especially for beginners). Knowing to brute force instead of caseworking by hand is extremely useful in contests, and can also help save you time (in addition to reducing mistakes).

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

int ans[15] = {-1, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88};
int pref[7] = {888, 108, 188, 200, 208, 288, 688};

void solve() {
	int n;
	cin >> n;
	if (n < 15) {
	    cout << ans[n];
	}
	else {
	    cout << pref[n % 7];
	    for (int i = 0; i < (n - 1) / 7 - 2; i++) {
	        cout << 8;
	    }
	}
	cout << ' ';
	cout << (n % 2 ? 7 : 1);
	for (int i = 0; i < n / 2 - 1; i++) {
	    cout << 1;
	}
	cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

Solve the problem for one stack, and then use linearity of expectation for all stacks.

First, suppose there was only one stack and that $$$a_i$$$ was small. Then the answer could be easily computed by dynamic programming: $$$a_1 = 1$$$, and $$$a_i = a_{i-1} \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} + 1$$$. However, $$$a_i$$$ can be up to $$$10^9$$$, so we need a way to speed this up. In fact, we can find a closed form for $$$a_i$$$: by solving the recursion, we get that $$$a_i = 2 - \frac{1}{2^{i-1}}$$$. (We can prove this by induction.) Make sure to use binary exponentiation here, because the default exponentiation function might be too slow.

Now let's solve the problem for the whole array. Note that each stack is independent. Therefore, the condition that we shoot at the stack with the smallest expected value is useless, due to linearity of expectation. Therefore, the expected number of arrows fired in total is just the sum of the expected number of arrows fired for each element.

This runs in $$$\mathcal{O}(\sum_{i=1}^n \log{a_i})$$$ time per test case.

However, you can make this run faster by noticing that for large values of $$$a_i$$$, the answer is practically equal to $$$2$$$ (this works due to the low precision). My original solution used this idea; see below for the implementation.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

long double f(long long x) {
	if (x == 0) {return 0;}
	if (x <= 60) {return (long double)2 - (long double)1/(1ll << (x - 1));}
	return (long double)2;
}

void solve() {
	int n;
	cin >> n;
	long long a;
	long double res = 0.0;
	for (int i = 0; i < n; i++) {
	    cin >> a;
	    res += f(a);
	}
	cout << fixed << setprecision(17) << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

Solve the problem for one bit, and then go bit by bit to construct $$$x$$$.

Let's figure out what $$$x$$$ should be by going bit by bit in its binary representation. In particular, let $$$a_i$$$, $$$b_i$$$, and $$$x_i$$$ denote the $$$i$$$th bit from the right in $$$a$$$, $$$b$$$, and $$$x$$$, respectively. Then for all positive integers $$$i$$$:

• If $$$a_i = 0$$$ and $$$b_i = 0$$$, $$$x_i$$$ can be $$$0$$$ or $$$1$$$. However, since $$$x \leq 10^{18}$$$, it is better to set $$$x_i=0$$$ to avoid going over that limit.
• If $$$a_i = 0$$$ and $$$b_i = 1$$$, no such $$$x_i$$$ exists, and the answer is $$$-1$$$.
• If $$$a_i = 1$$$ and $$$b_i = 0$$$, $$$x_i = 1$$$.
• If $$$a_i = 1$$$ and $$$b_i = 1$$$, $$$x_i = 0$$$.

Therefore, by going bit by bit, we can construct such an $$$x$$$ or report whether no such $$$x$$$ exists. This runs in $$$\mathcal{O}(\log{n})$$$ per test case.

There is also a simpler solution not involving going bit by bit, which uses the same proof as above: just set $$$x = a \text{ XOR } b$$$, and test whether this $$$x$$$ is valid or not.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100007;
const int MOD = 1000000007;

void solve() {
    long long a, b;
    cin >> a >> b;
    long long x = a ^ b;
    if ((x | a) == (x ^ b)) {
    	cout << x << endl;
    }
    else {
    	cout << -1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}