算法练习专栏——Codeforces——Codeforces Round 925 (Div. 3)

A. Recovering a Small String

Nikita had a word consisting of exactly $3$ lowercase Latin letters. The letters in the Latin alphabet are numbered from $1$ to $26$, where the letter “a” has the index $1$, and the letter “z” has the index $26$.

He encoded this word as the sum of the positions of all the characters in the alphabet. For example, the word “cat” he would encode as the integer $3 + 1 + 20 = 24$, because the letter “c” has the index $3$ in the alphabet, the letter “a” has the index $1$, and the letter “t” has the index $20$.

However, this encoding turned out to be ambiguous! For example, when encoding the word “ava”, the integer $1 + 22 + 1 = 24$ is also obtained.

Determine the lexicographically smallest word of $3$ letters that could have been encoded.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

$a$ is a prefix of $b$, but $a \ne b$;
in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

Input

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

This is followed by the descriptions of the test cases.

The first and only line of each test case contains an integer $n$ ($3 \le n \le 78$) — the encoded word.

Output

For each test case, output the lexicographically smallest three-letter word that could have been encoded on a separate line.

Example

input

output

aav
rzz
aaa
czz
auz

翻译

Nikita 有一个单词由恰好 $$$3$$$ 个小写拉丁字母组成。拉丁字母表中的字母编号从 $$$1$$$ 到 $$$26$$$ ，其中字母“a”的索引为 $$$1$$$ ，字母“z”的索引为 $$$26$$$ 。

他将这个单词编码为字母表中所有字符的位置总和。例如，他将单词“cat”编码为整数 $$$3 + 1 + 20 = 24$$$ ，因为字母“c”在字母表中的索引为 $$$3$$$ ，字母“a”的索引为 $$$1$$$ ，字母“t”的索引为 $$$20$$$ 。

但是，这种编码结果却不明确！例如，在对单词“ava”进行编码时，也会得到整数 $$$1 + 22 + 1 = 24$$$ 。

确定可以编码的字典顺序最小的 $$$3$$$ 个字母的单词。

当且仅当下列条件之一成立时，字符串 $$$a$$$ 的字典顺序小于字符串 $$$b$$$ ：

$$$a$$$ 是 $$$b$$$ 的前缀，但 $$$a \ne b$$$ ；
在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置上，字符串 $$$a$$$ 中有一个字母在字母表中出现的时间比 $$$b$$$ 中对应的字母更早。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 100$ ) — 测试中的测试用例数。

接下来是测试用例的描述。

每个测试用例的第一行也是唯一一行包含一个整数 $n$ ( $3 \le n \le 78$ ) — 编码的单词。

输出

对于每个测试用例，输出按字典顺序排列的最小三个字母的单词，该单词可以单独编码。

Example

input

output

aav
rzz
aaa
czz
auz

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 2e5 + 10;
int a[N];

void solve(){
	int n;
	cin >> n;
	if (n >= 3 && n <= 28) {
		cout << "aa" << char('a' + (n - 3)) << '\n';
	} else if (n > 28 && n <= 53) {
		cout << "a" << char('a' + n - 28) << "z" << '\n';
	} else {
		cout << char('a' + n - 53)<< "z" << "z" << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

B. Make Equal

Problem - B - Codeforces

There are $n$ containers of water lined up, numbered from left to right from $1$ to $n$. Each container can hold any amount of water; initially, the $i$-th container contains $a_i$ units of water. The sum of $a_i$ is divisible by $n$.

You can apply the following operation any (possibly zero) number of times: pour any amount of water from the $i$-th container to the $j$-th container, where $i$ must be less than $j$ (i.e. $i \lt j$). Any index can be chosen as $i$ or $j$ any number of times.

Determine whether it is possible to make the amount of water in all containers the same using this operation.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of containers with water.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the amounts of water in the containers. It is guaranteed that the sum of $a_i$ in each test case does not exceed $2 \cdot 10^9$. Also, the sum of $a_i$ is divisible by $n$.

It is guaranteed that the sum of $n$ over all test cases in the input does not exceed $2 \cdot 10^5$.

Output

Output $t$ lines, each of which is the answer to the corresponding test case. As the answer, output “YES” if it is possible to make the amount of water in all containers the same using the described operation. Otherwise, output “NO”.

You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be accepted as a positive answer.

Example

input

6
1
43
2
1 3
5
4 5 2 1 3
3
1 2 3
7
4 5 5 0 6 4 4
7
6 5 5 1 3 4 4

output

YES
NO
YES
NO
NO
YES

Note

In the third test case of the example ($a=[4, 5, 2, 1, 3]$), you can proceed as follows:

pour $1$ unit of water from the first vessel to the fourth, then $a=[3, 5, 2, 2, 3]$;
pour $1$ unit of water from the second vessel to the third, then $a=[3, 4, 3, 2, 3]$;
pour $1$ unit of water from the second vessel to the fourth, then $a=[3, 3, 3, 3, 3]$.

翻译

有 $n$ 个水容器排成一排，从左到右编号为 $1$ 至 $n$ 。每个容器可容纳任意数量的水；最初，第 $i$ 个容器包含 $a_i$ 个单位的水。 $a_i$ 的总和可以被 $n$ 整除。

您可以任意次（可能是零次）应用以下操作：将任意数量的水从第 $i$ 个容器倒入第 $j$ 个容器，其中 $i$ 必须小于 $j$ （即 $i \lt j$ ）。任何索引都可以被任意次选择为 $i$ 或 $j$ 。

确定是否可以使用此操作使所有容器中的水量相同。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — 装有水的容器的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^9$ ) — 容器中的水量。保证每个测试用例中的 $a_i$ 的总和不超过 $2 \cdot 10^9$ 。此外， $a_i$ 的总和可以被 $n$ 整除。

保证输入中所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出

输出 $t$ 行，每行都是相应测试用例的答案。如果可以使用所述操作使所有容器中的水量相同，则输出“YES”作为答案。否则，输出“NO”。

您可以以任何大小写（小写或大写）输出每个字母。例如，字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

Example

input

6
1
43
2
1 3
5
4 5 2 1 3
3
1 2 3
7
4 5 5 0 6 4 4
7
6 5 5 1 3 4 4

output

YES
NO
YES
NO
NO
YES

注意

在示例的第三个测试用例 ( $a=[4, 5, 2, 1, 3]$ ) 中，您可以按如下方式进行：

将 $1$ 单位的水从第一个容器倒入第四个容器，然后倒入 $a=[3, 5, 2, 2, 3]$ ；
将 $1$ 单位的水从第二个容器倒入第三个容器，然后倒入 $a=[3, 4, 3, 2, 3]$ ；
将 $1$ 单位的水从第二个容器倒入第四个容器，然后倒入 $a=[3, 3, 3, 3, 3]$ 。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];

void solve(){
	int n;
	LL sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		sum += a[i];
	}
	LL av = 1.0 * sum / n;
	for (int i = 1;i <= n; i++) {
		if (a[i] < av) {
			cout << "NO\n";
			return;
		} else {
			a[i + 1] += a[i] - av;
		}
	}
	
	cout << "YES\n";
	
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

C. Make Equal Again

Problem - C - Codeforces

You have an array $a$ of $n$ integers.

You can no more than once apply the following operation: select three integers $i$, $j$, $x$ ($1 \le i \le j \le n$) and assign all elements of the array with indexes from $i$ to $j$ the value $x$. The price of this operation depends on the selected indices and is equal to $(j - i + 1)$ burles.

For example, the array is equal to $[1, 2, 3, 4, 5, 1]$. If we choose $i = 2, j = 4, x = 8$, then after applying this operation, the array will be equal to $[1, 8, 8, 8, 5, 1]$.

What is the least amount of burles you need to spend to make all the elements of the array equal?

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. The descriptions of the test cases follow.

The first line of the description of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10 ^ 5$) — the size of the array.

The second line of the description of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — array elements.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output one integer — the minimum number of burles that will have to be spent to make all the elements of the array equal. It can be shown that this can always be done.

Example

input

8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3

output

翻译

您有一个包含 $$$n$$$ 个整数的数组 $$$a$$$ 。

您只能一次应用以下操作：选择三个整数 $$$i$$$ 、 $$$j$$$ 、 $$$x$$$ ( $$$1 \le i \le j \le n$$$ )，并将索引从 $$$i$$$ 到 $$$j$$$ 的数组的所有元素赋值 $$$x$$$ 。此操作的价格取决于所选的索引，等于 $$$(j - i + 1)$$$ 个 burles。

例如，数组等于 $$$[1, 2, 3, 4, 5, 1]$$$ 。如果我们选择 $$$i = 2, j = 4, x = 8$$$ ，那么应用此操作后，数组将等于 $$$[1, 8, 8, 8, 5, 1]$$$ 。

需要花费最少的 burle 数量是多少才能使数组的所有元素都相等？

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 输入测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10 ^ 5$ ) — 数组的大小。

每个测试用例描述的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le n$ ) — 数组元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数 — 使数组的所有元素相等所需花费的最小 burle 数。可以证明这总是可以做到的。

Example

input

8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3

output

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 2e5 + 10;
int a[N];

void solve(){
	int n;
	cin >> n;
	int l = 1, r = n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int k1 = a[l], k2 = a[r];
	while (l <= n) {
		if (a[l] == k1) l++;
		else {
			l--;
			break;	
		}
	} 
	while (r >= 1) {
		if (a[r] == k2) r--;
		else {
			r++;
			break;	
		}
	}
	
	// cout << l << " " << r << '\n';
	if (l == n + 1) {
		cout << "0\n";
	} else if (k1 != k2){
		cout << n - max(l, n - r + 1) << '\n';
	} else {
		cout << n - (l + n - r + 1) << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

D. Divisible Pairs

Problem - D - Codeforces

Polycarp has two favorite integers $x$ and $y$ (they can be equal), and he has found an array $a$ of length $n$.

Polycarp considers a pair of indices $\langle i, j \rangle$ ($1 \le i \lt j \le n$) beautiful if:

$a_i + a_j$ is divisible by $x$;
$a_i - a_j$ is divisible by $y$.

For example, if $x=5$, $y=2$, $n=6$, $a=$[$1, 2, 7, 4, 9, 6$], then the only beautiful pairs are:

$\langle 1, 5 \rangle$: $a_1 + a_5 = 1 + 9 = 10$ ($10$ is divisible by $5$) and $a_1 - a_5 = 1 - 9 = -8$ ($-8$ is divisible by $2$);
$\langle 4, 6 \rangle$: $a_4 + a_6 = 4 + 6 = 10$ ($10$ is divisible by $5$) and $a_4 - a_6 = 4 - 6 = -2$ ($-2$ is divisible by $2$).

Find the number of beautiful pairs in the array $a$.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains three integers $n$, $x$, and $y$ ($2 \le n \le 2 \cdot 10^5$, $1 \le x, y \le 10^9$) — the size of the array and Polycarp’s favorite integers.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the number of beautiful pairs in the array $a$.

Example

input

7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14

output

翻译

Polycarp 有两个最喜欢的整数 $x$ 和 $y$ （它们可以相等），并且他找到了一个长度为 $n$ 的数组 $a$ 。

Polycarp 认为一对索引 $\langle i, j \rangle$ ( $1 \le i \lt j \le n$ ) 是优美的，如果：

$a_i + a_j$ 可以被 $x$ 整除；
$a_i - a_j$ 可以被 $y$ 整除。

例如，如果 $x=5$ 、 $y=2$ 、 $n=6$ 、 $a=$ [ $1, 2, 7, 4, 9, 6$ ]，那么唯一完美的配对是：

$\langle 1, 5 \rangle$ ： $a_1 + a_5 = 1 + 9 = 10$ ( $10$ 可被 $5$ 整除) 和 $a_1 - a_5 = 1 - 9 = -8$ ( $-8$ 可被 $2$ 整除)；
$\langle 4, 6 \rangle$ ： $a_4 + a_6 = 4 + 6 = 10$ （ $10$ 能被 $5$ 整除）和 $a_4 - a_6 = 4 - 6 = -2$ （ $-2$ 能被 $2$ 整除）。

找出数组 $a$ 中漂亮对的数量。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含三个整数 $n$ 、 $x$ 和 $y$ ( $2 \le n \le 2 \cdot 10^5$ 、 $1 \le x, y \le 10^9$ ) — 数组的大小和 Polycarp 最喜欢的整数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — 数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数——数组 $a$ 中漂亮对的数量。

Example

input

7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14

output

思路

同余的性质，相加能被x整除，那么先同余x再相加同样能被x整除，相减被y整除，那么先同余y再相减同样能被y整除（其实相当于就是两者余数相同）

所以对一个数，它同余x和同余y的余数其实已经确定了，其实就是找和它配成同余x的余数相加能被x整除以及同余y的余数相同的数前面有多少个。因为xy同样可以很大，开桶会爆空间，所以使用map或者set。（到目前为止其实大家还是可以很简单的想到的）

考虑使用map<pair<int,int>,int> ，前面的pair键描述分别同余x和y的余数信息，后面的int值记录数量即可。这个地方这种构造map的方式还有后续具体如何寻找键值对数量是这道题目的难点。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;
typedef long long LL;
// const int N = 2e5 + 10;
// int a[N];
map<pair<int, int>, int> mp;
LL ans = 0;

void solve(){
	int n, x, y;
	cin >> n >> x >> y;
	
	ans = 0;
	mp.clear();
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		// 此处再 % 一次是为了防止出现负数情况
		ans += mp[make_pair((x - k % x) % x, k % y)];
		
		mp[make_pair(k % x, k % y)] ++;		
	}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

E. Anna and the Valentine’s Day Gift

Problem - E - Codeforces

Sasha gave Anna a list $a$ of $n$ integers for Valentine’s Day. Anna doesn’t need this list, so she suggests destroying it by playing a game.

Players take turns. Sasha is a gentleman, so he gives Anna the right to make the first move.

On her turn, Anna must choose an element $a_i$ from the list and reverse the sequence of its digits. For example, if Anna chose the element with a value of $42$, it would become $24$; if Anna chose the element with a value of $1580$, it would become $851$. Note that leading zeros are removed. After such a turn, the number of elements in the list does not change.
On his turn, Sasha must extract two elements $a_i$ and $a_j$ ($i \ne j$) from the list, concatenate them in any order and insert the result back into the list. For example, if Sasha chose the elements equal to $2007$ and $19$, he would remove these two elements from the list and add the integer $200719$ or $192007$. After such a turn, the number of elements in the list decreases by $1$.

Players can’t skip turns. The game ends when Sasha can’t make a move, i.e. after Anna’s move there is exactly one number left in the list. If this integer is not less than $10^m$ (i.e., $\ge 10^m$), Sasha wins. Otherwise, Anna wins.

It can be shown that the game will always end. Determine who will win if both players play optimally.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follows the description of the test cases.

The first line of each test case contains integers $n$, $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^6$) — the number of integers in the list and the parameter determining when Sasha wins.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the list that Sasha gave to Anna.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output:

“Sasha”, if Sasha wins with optimal play;
“Anna”, if Anna wins with optimal play.

Example

input

9
2 2
14 2
3 5
9 56 1
4 10
1 2007 800 1580
4 5
5000 123 30 4
10 10
6 4 6 2 3 1 10 9 10 7
1 1
6
1 1
10
8 9
1 2 9 10 10 2 10 2
4 5
10 10 10 10

output

Sasha
Anna
Anna
Sasha
Sasha
Anna
Anna
Anna
Sasha

Note

Consider the first test case.

Anna can reverse the integer $2$, then Sasha can concatenate the integers $2$ and $14$, obtaining the integer $214$, which is greater than $10^2 = 100$. If Anna had reversed the integer $14$, Sasha would have concatenated the integers $41$ and $2$, obtaining the integer $412$, which is greater than $10^2 = 100$. Anna has no other possible moves, so she loses.

翻译

萨沙送给安娜一份包含 $n$ 个整数的列表 $a$ ，作为情人节礼物。安娜不需要这份列表，所以她建议通过玩游戏来毁掉它。

玩家轮流行动。萨沙是一位绅士，所以他让安娜先行动。

轮到安娜时，安娜必须从列表中选择一个元素 $a_i$ ，并反转其数字的顺序。例如，如果安娜选择了值为 $42$ 的元素，它将变成 $24$ ；如果安娜选择了值为 $1580$ 的元素，它将变成 $851$ 。请注意，前导零会被删除。经过这样的轮换后，列表中元素的数量不会改变。
轮到他时，Sasha 必须从列表中提取两个元素 $a_i$ 和 $a_j$ ( $i \ne j$ )，以任意顺序连接它们，然后将结果重新插入列表。例如，如果 Sasha 选择等于 $2007$ 和 $19$ 的元素，他将从列表中删除这两个元素并添加整数 $200719$ 或 $192007$ 。经过这样的轮次，列表中的元素数量将减少 $1$ 。

玩家不能跳过轮次。当 Sasha 无法移动时，游戏结束，即 Anna 移动后列表中只剩下一个数字。如果这个整数不小于 $10^m$ （即 $\ge 10^m$ ），Sasha 获胜。否则，Anna 获胜。

可以证明游戏总会结束。如果两位玩家都发挥最佳水平，确定谁会获胜。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。

接下来是测试用例的描述。

每个测试用例的第一行包含整数 $n$ , $m$ ( $1 \le n \le 2 \cdot 10^5$ , $0 \le m \le 2 \cdot 10^6$ ) — 列表中整数的数量和确定 Sasha 获胜的参数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ) — Sasha 给 Anna 的列表。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试案例，输出：

“Sasha”，如果 Sasha 以最佳玩法获胜；
“Anna”，如果 Anna 以最佳玩法获胜。

Example

input

9
2 2
14 2
3 5
9 56 1
4 10
1 2007 800 1580
4 5
5000 123 30 4
10 10
6 4 6 2 3 1 10 9 10 7
1 1
6
1 1
10
8 9
1 2 9 10 10 2 10 2
4 5
10 10 10 10

output

Sasha
Anna
Anna
Sasha
Sasha
Anna
Anna
Anna
Sasha

注意

考虑第一个测试案例。

Anna 可以反转整数 $2$ ，然后 Sasha 可以连接整数 $2$ 和 $14$ ，得到整数 $214$ ，大于 $10^2 = 100$ 。如果 Anna 反转整数 $14$ ，Sasha 会连接整数 $41$ 和 $2$ ，得到整数 $412$ ，大于 $10^2 = 100$ 。Anna 没有其他可能的行动，所以她输了。

思路

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 2e5 + 10;

int _ , n, m, a[N];

pair<int,int> g(int x){
	int cnt1 = 0,cnt2;
	while(x % 10 == 0){
		cnt1 ++;
		x /= 10;
	}
	cnt2 = cnt1;
	while(x){
		cnt2 ++;
		x /= 10;
	}
	return make_pair(cnt1,cnt2);
}

int main(){
	cin >> _;
	while(_--){
		cin >> n >> m;
		int ans = 0;
		for(int i = 1;i <= n; i++){
            int t;
			cin >> t;
			pair<int, int> tmp(g(t));
			a[i] = tmp.first;
			ans += tmp.second;
		}
		sort(a + 1,a + n + 1, greater<int>());
		for(int i = 1;i <= n;i += 2)
			ans -= a[i];
		
		puts((ans > m) ? "Sasha":"Anna");
	}
	return 0;
}

算法练习专栏——Codeforces——Codeforces Round 923 (Div. 3) 上一篇

监考系统PLUS——需求分析下一篇