CF2261A.Hey, It's Me, Souvlakity

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Souvlakity and Kalamakity are playing yet another game.

All the integers from 11 to nn have been distributed between the players. The distribution can be represented as a binary string ss of size nn, where si=1s_i = 1 if integer ii has been given to Souvlakity, and si=0s_i = 0 if it has been given to Kalamakity. It is guaranteed that Souvlakity owns at least one integer initially (there exists a 11 in ss).

The game will go on for 1010010^{100} turns. The two players play in alternating turns, with Souvlakity playing first.

When it is a player's turn, they must choose exactly one of their integers and give it to the other player. It can be shown that this is always possible under this game's constraints.

After all 1010010^{100} turns are finished, Souvlakity calculates his score as the range of the integers he owns (that is, his score is max⁡(S)−min⁡(S)\max(S) - \min(S), where SS is the set of integers he owns). It can be shown that Souvlakity will own at least one integer at the end of the game.

Souvlakity wants to maximize his score, and Kalamakity wants to minimize Souvlakity's score. What is Souvlakity's final score if both players act optimally?

苏夫拉基蒂和卡拉马基蒂正在玩另一场游戏。

从 11 到 nn 的所有整数已被分配给两位玩家。该分配可用一个长度为 nn 的二进制字符串 ss 表示,其中若整数 ii 分配给了苏夫拉基蒂,则 si=1s_i = 1;若分配给了卡拉马基蒂,则 si=0s_i = 0。题目保证苏夫拉基蒂初始时至少拥有一枚整数(即 ss 中至少存在一个 11)。

游戏共进行 1010010^{100} 轮。两位玩家轮流行动,苏夫拉基蒂先手。

轮到某位玩家行动时,他必须恰好选择自己所拥有的一枚整数,并将其交给另一位玩家。可以证明,在本游戏的约束条件下,此操作总能进行。

在全部 1010010^{100} 轮结束后,苏夫拉基蒂计算自己的得分为其当前所拥有整数的极差(即得分为 max⁡(S)−min⁡(S)\max(S) - \min(S),其中 SS 是苏夫拉基蒂最终拥有的整数集合)。可以证明,游戏结束时苏夫拉基蒂至少拥有一枚整数。

苏夫拉基蒂希望最大化自己的得分,而卡拉马基蒂则希望最小化苏夫拉基蒂的得分。若双方均采取最优策略,苏夫拉基蒂的最终得分是多少?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001 \le t \le 100). The description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤1002 \le n \le 100).

The second line of each test case contains a binary string ss of length nn. It is guaranteed that there exists at least one 1\mathtt{1} in ss.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1001 \le t \le 100)。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 nn(2≤n≤1002 \le n \le 100)。

每个测试用例的第二行包含一个长度为 nn 的二进制字符串 ss。保证 ss 中至少存在一个 1\mathtt{1}。

输出格式

For each test case, on a separate line, output a single integer: Souvlakity's final score after the game ends, if both players act optimally.

对于每个测试用例,在单独一行中输出一个整数:如果双方玩家均采取最优策略,则Souvlakity在游戏结束时的最终得分。

输入输出样例

  • 输入#1

    6
    2
    01
    3
    111
    4
    1100
    5
    11111
    6
    101010
    7
    1101001

    输出#1

    0
    2
    1
    4
    4
    6

说明/提示

In the first test case, Souvlakity initially owns only the integer 22. During each pair of consecutive turns (Souvlakity's turn and then Kalamakity's turn), Souvlakity gives away one integer and receives one integer, so after each of Kalamakity's turns he owns exactly as many integers as he owned initially. Since the number of turns is even, the last turn is Kalamakity's, so Souvlakity owns exactly one integer at the end of the game, and his score is 00.

In the second test case, Souvlakity initially owns all three integers. By the same argument, he owns three integers at the end of the game, that is, all of them, so his score is 3−1=23 - 1 = 2.

在第一个测试用例中,Souvlakity 最初仅拥有整数 22。在每一对连续的回合(Souvlakity 的回合,随后是 Kalamakity 的回合)中,Souvlakity 给出一个整数并收到一个整数,因此在每次 Kalamakity 的回合结束后,他所拥有的整数个数始终与初始时相同。由于总回合数为偶数,最后一轮是 Kalamakity 的回合,因此游戏结束时 Souvlakity 恰好拥有一个整数,其得分为 00。

在第二个测试用例中,Souvlakity 最初拥有全部三个整数。依据同样的推理,游戏结束时他仍拥有三个整数,即全部三个整数,因此他的得分为 3−1=23 - 1 = 2。

输入解题思路,AI测评打分。不知道怎么写?

首页