A. Binary Imbalance

Description

You are given a string $s$, consisting only of characters ‘0’ and/or ‘1’.

In one operation, you choose a position $i$ from $1$ to $|s|-1$, where $|s|$ is the current length of string $s$. Then you insert a character between the $i$-th and the $(i+1)$-st characters of $s$. If $s_i=s_{i+1}$, you insert ‘1’. If $s_i\ne s_{i+1}$, you insert ‘0’.

Is it possible to make the number of zeroes in the string strictly greater than the number of ones, using any number of operations (possibly, none)?

Input

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of testcases.

The first line of each testcase contains an integer $n$ ($1\le n\le 100$).

The second line contains a string $s$ of length exactly $n$, consisting only of characters ‘0’ and/or ‘1’.

Output

For each testcase, print “YES” if it’s possible to make the number of zeroes in $s$ strictly greater than the number of ones, using any number of operations (possibly, none). Otherwise, print “NO”.

Example

input
3
2
00
2
11
2
10
output
YES
NO
YES

Note

In the first testcase, the number of zeroes is already greater than the number of ones.

In the second testcase, it’s impossible to insert any zeroes in the string.

In the third testcase, you can choose $i=1$ to insert a zero between the $1$-st and the $2$-nd characters. Since $s_1\ne s_2$, you insert a ‘0’. The resulting string is “100”. It has two zeroes and only a single one, so the answer is “YES”.

Solution

具体见文后视频。

---

Code

#include <iostream>
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
 
void solve()
{
	int N;
	string S;
 
	cin >> N >> S;
 
	S = ' ' + S;
	int Count = 0;
	for (int i = 1; i <= N; i ++)
	{
		Count += (S[i] == '0');
		if (i < N && S[i] != S[i + 1])
		{
			cout << "YES" << endl;
			return;
		}
	}
 
	if (Count > (N - Count)) cout << "YES" << endl;
	else cout << "NO" << endl;
}
 
signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
 
	int Data;
 
	cin >> Data;
 
	while (Data --)
		solve();
 
	return 0;
}

B. Getting Points

Description

Monocarp is a student at Berland State University. Due to recent changes in the Berland education system, Monocarp has to study only one subject — programming.

The academic term consists of $n$ days, and in order not to get expelled, Monocarp has to earn at least $P$ points during those $n$ days. There are two ways to earn points — completing practical tasks and attending lessons. For each practical task Monocarp fulfills, he earns $t$ points, and for each lesson he attends, he earns $l$ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day $1$ (and can be completed on any day from $1$ to $n$), the second task is unlocked on day $8$ (and can be completed on any day from $8$ to $n$), the third task is unlocked on day $15$, and so on.

Every day from $1$ to $n$, there is a lesson which can be attended by Monocarp. And every day, Monocarp chooses whether to study or to rest the whole day. When Monocarp decides to study, he attends a lesson and can complete no more than $2$ tasks, which are already unlocked and not completed yet. If Monocarp rests the whole day, he skips a lesson and ignores tasks.

Monocarp wants to have as many days off as possible, i. e. he wants to maximize the number of days he rests. Help him calculate the maximum number of days he can rest!

Input

The first line contains a single integer $tc$ ($1\le tc\le 10^4$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains four integers $n$, $P$, $l$ and $t$ ($1\le n,l,t\le 10^9$; $1\le P\le 10^{18}$) — the number of days, the minimum total points Monocarp has to earn, the points for attending one lesson and points for completing one task.

It’s guaranteed for each test case that it’s possible not to be expelled if Monocarp will attend all lessons and will complete all tasks.

Output

For each test, print one integer — the maximum number of days Monocarp can rest without being expelled from University.

Example

input
5
1 5 5 2
14 3000000000 1000000000 500000000
100 20 1 10
8 120 10 20
42 280 13 37
output
0
12
99
0
37

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <cmath>
#define int long long
 
using namespace std;
 
typedef pair<int, int> PII;
 
void solve()
{
	int N, P, L, T;
 
	cin >> N >> P >> L >> T;
 
	int Day = (N - 1) / 7 + 1;
	int Score = (Day / 2) * (L + 2 * T);
	if (Score >= P) cout << N - (int)ceil(P * 1.0 / (L + 2 * T)) << endl;
	else
	{
		if (Day & 1) Score += L + T;
		if (Score >= P) cout << N - (Day / 2 + 1) << endl;
		else
		{
			P -= Score;
			cout << N - (P + L - 1) / L - (Day / 2 + (Day & 1)) << endl;
		}
	}
}
 
signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
 
	int Data;
 
	cin >> Data;
 
	while (Data --)
		solve();
 
	return 0;
}

C. Insert and Equalize

Description

You are given an integer array $a_1,a_2,\dots ,a_n$, all its elements are distinct.

First, you are asked to insert one more integer $a_{n+1}$ into this array. $a_{n+1}$ should not be equal to any of $a_1,a_2,\dots ,a_n$.

Then, you will have to make all elements of the array equal. At the start, you choose a positive integer $x$ ($x>0$). In one operation, you add $x$ to exactly one element of the array. Note that $x$ is the same for all operations.

What’s the smallest number of operations it can take you to make all elements equal, after you choose $a_{n+1}$ and $x$?

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9$). All $a_i$ are distinct.

The sum of $n$ over all testcases doesn’t exceed $2\cdot 10^5$.

Output

For each testcase, print a single integer — the smallest number of operations it can take you to make all elements equal, after you choose integers $a_{n+1}$ and $x$.

Example

input
3
3
1 2 3
5
1 -19 17 -3 -15
1
10
output
6
27
1

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10;

int N;
int A[SIZE], Minus[SIZE];

void solve()
{
	cin >> N;

	int Max = -1e18;
	for (int i = 1; i <= N; i ++)
		cin >> A[i], Max = max(A[i], Max);

	int X = 0;
	for (int i = 1; i <= N; i ++)
		X = __gcd(X, Max - A[i]);

	if (X == 0)
	{
		cout << 1 << endl;
		return;
	}

	sort(A + 1, A + 1 + N);

	A[N + 1] = A[1] - X;
	for (int i = N - 1; i >= 1; i --)
		if (A[i + 1] - A[i] > X)
		{
			A[N + 1] = A[i + 1] - X;
			break;
		}

	int Result = 0;
	for (int i = 1; i <= N + 1; i ++)
		Result += (Max - A[i]) / X;

	cout << Result << endl;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}

D. Robot Queries

Description

There is an infinite $2$-dimensional grid. Initially, a robot stands in the point $(0,0)$. The robot can execute four commands:

• U — move from point $(x,y)$ to $(x,y+1)$;
• D — move from point $(x,y)$ to $(x,y-1)$;
• L — move from point $(x,y)$ to $(x-1,y)$;
• R — move from point $(x,y)$ to $(x+1,y)$.

You are given a sequence of commands $s$ of length $n$. Your task is to answer $q$ independent queries: given four integers $x$, $y$, $l$ and $r$; determine whether the robot visits the point $(x,y)$, while executing a sequence $s$, but the substring from $l$ to $r$ is reversed (i. e. the robot performs commands in order $s_1{s}_2{s}_3\dots s_{l-1}{s}_r{s}_{r-1}{s}_{r-2}\dots s_l{s}_{r+1}{s}_{r+2}\dots s_n$).

Input

The first line contains two integers $n$ and $q$ ($1\le n,q\le 2\cdot 10^5$) — the length of the command sequence and the number of queries, respectively.

The second line contains a string $s$ of length $n$, consisting of characters U, D, L and/or R.

Then $q$ lines follow, the $i$-th of them contains four integers $x_i$, $y_i$, $l_i$ and $r_i$ ($-n\le x_i,y_i\le n$; $1\le l\le r\le n$) describing the $i$-th query.

Output

For each query, print YES if the robot visits the point $(x,y)$, while executing a sequence $s$, but the substring from $l$ to $r$ is reversed; otherwise print NO.

Example

input
8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8
output
YES
YES
NO

input

4 2

RLDU

0 0 2 2

-1 -1 2 3

output

YES

NO

input
10 6
DLUDLRULLD
-1 0 1 10
-1 -2 2 5
-4 -2 6 10
-1 0 3 9
0 1 4 7
-3 -1 5 8
output
YES
YES
YES
NO
YES
YES

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;

typedef pair<int, int> PII;

int N, Q;
string S;
std::map<char, int> dx, dy;
std::map<PII, int> Exist1, Exist2;
std::vector<PII> Point1, Point2;
std::map<PII, vector<int>> Id1, Id2;

bool Check(int X, int Y, int L, int R)
{
	auto P1 = Point1[L - 1];
	auto P2 = Point2[N - R];
	
	X += P2.first - P1.first;
	Y += P2.second - P1.second;

	int P = lower_bound(Id2[{X, Y}].begin(), Id2[{X, Y}].end(), N - R) - Id2[{X, Y}].begin();
	if (Exist2.count({X, Y}) && Id2[{X, Y}][P] >= N - R + 1 && Id2[{X, Y}][P] <= N - L + 1) return 1;
	return 0;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	dy['U'] = 1, dy['D'] = -1, dy['L'] = 0, dy['R'] = 0;
	dx['U'] = 0, dx['D'] = 0, dx['L'] = -1, dx['R'] = 1;

	cin >> N >> Q >> S;

	string T = S;
	S = ' ' + S;
	reverse(T.begin(), T.end());
	T = ' ' + T;
	int X1 = 0, Y1 = 0, X2 = 0, Y2 = 0;
	Exist1[{X1, Y1}] = Exist2[{X2, Y2}] = 1;
	Id1[{X1, Y1}].push_back(0), Id2[{X2, Y2}].push_back(0);
	Point1.push_back({X1, Y1}), Point2.push_back({X2, Y2});
	for (int i = 1; i <= N; i ++)
	{
		X1 += dx[S[i]], Y1 += dy[S[i]];
		X2 += dx[T[i]], Y2 += dy[T[i]];
		Id1[{X1, Y1}].push_back(i);
		Id2[{X2, Y2}].push_back(i);
		Exist1[{X1, Y1}] = Exist2[{X2, Y2}] = 1;
		Point1.push_back({X1, Y1});
		Point2.push_back({X2, Y2});
	}

	// cout << "Check:";
	// for (auto c : Id2[{-2, -1}])
	// 	cout << c << ' ';
	// cout << endl;

	while (Q --)
	{
		int X, Y, L, R;

		cin >> X >> Y >> L >> R;

		if (Exist1.count({X, Y}) && *Id1[{X, Y}].begin() < L) cout << "YES" << endl;
		else if (Exist1.count({X, Y}) && Id1[{X, Y}].back() > R) cout << "YES" << endl;
		else if (Check(X, Y, L, R)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}

E. Collapsing Strings

Description

You are given $n$ strings $s_1,s_2,\dots ,s_n$, consisting of lowercase Latin letters. Let $|x|$ be the length of string $x$.

Let a collapse $C(a,b)$ of two strings $a$ and $b$ be the following operation:

• if $a$ is empty, $C(a,b)=b$;
• if $b$ is empty, $C(a,b)=a$;
• if the last letter of $a$ is equal to the first letter of $b$, then $C(a,b)=C(a_{1,|a|-1},b_{2,|b|})$, where $s_{l,r}$ is the substring of $s$ from the $l$-th letter to the $r$-th one;
• otherwise, $C(a,b)=a+b$, i. e. the concatenation of two strings.

Calculate $\sum _{i=1}^n\sum _{j=1}^n|C(s_i,s_j)|$.

Input

The first line contains a single integer $n$ ($1\le n\le 10^6$).

Each of the next $n$ lines contains a string $s_i$ ($1\le |s_i|\le 10^6$), consisting of lowercase Latin letters.

The total length of the strings doesn’t exceed $10^6$.

Output

Print a single integer — $\sum _{i=1}^n\sum _{j=1}^n|C(s_i,s_j)|$.

Example

input

3

aba

ab

ba

output

20

input

5

abab

babx

xab

xba

bab

output

126

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 1e6 + 10;

int N;
string S[SIZE];
int Trie[SIZE][26], Count[SIZE], idx = 0;
int Point[SIZE], k;

void Insert(string S)
{
	int p = 0;
	for (int i = 0; i < S.size(); i ++)
	{
		int c = S[i] - 'a';
		if (!Trie[p][c]) Trie[p][c] = ++ idx;
		p = Trie[p][c];
		Count[p] ++;
	}
}

int Query(string S)
{
	int p = 0, Depth = 0, Cnt = 0;
	k = 0;
	for (int i = 0; i < S.size(); i ++)
	{
		int c = S[i] - 'a';
		if (!Trie[p][c]) break;
		p = Trie[p][c];
		Point[ ++ k] = p;
	}

	int Result = 0, Max = 0;
	for (int i = k; i >= 1; i --)
	{
		Result += (min((int)S.size(), i) * 2) * (Count[Point[i]] - Max);
		Max = Count[Point[i]];
	}

	return Result;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;

	int Len = 0;
	for (int i = 1; i <= N; i ++)
	{
		cin >> S[i];
		string Tmp = S[i];
		reverse(Tmp.begin(), Tmp.end());
		Insert(Tmp);
		Len += (int)S[i].size();
	}

	int Result = 0;
	for (int i = 1; i <= N; i ++)
	{
		int Minus = Query(S[i]);
		Result += Len + (int)S[i].size() * N - Minus;
	}

	cout << Result << endl;

	return 0;
}

视频题解

---

最后祝大家早日