← 返回题目列表

Codeforces · 2032/A

A. 电路

中文机器翻译题面 查看原题

Alice 刚刚制作了一个带有 $$$n$$$ 灯和 $$$2n$$$ 开关的电路。每个组件(灯或开关)都有两种状态:开或关。灯和开关的排列方式如下:

- 每个灯都连接到两个开关。
- 每个开关都连接到一盏灯。不知道每个开关连接到哪个灯。
- 当所有开关关闭时,所有灯也关闭。
- 如果切换开关(从开到关,或反之亦然),与其连接的灯的状态也会切换。

Alice把只显示$$$2n$$$开关状态的电路带给她的妹妹Iris,并给她出一个谜语:可以打开的灯的最小和最大数量是多少?

艾丽丝太了解妹妹的滑稽动作了,她只用了一秒钟就给了爱丽丝正确的答案。你能做同样的事吗?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 电路中的灯数量。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$0 \le a_i \le 1$$$) - 电路中开关的状态。 $$$a_i = 0$$$ 表示第 $$$i$$$ 个开关关闭,$$$a_i = 1$$$ 表示第 $$$i$$$ 个开关打开。

输出

对于每个测试用例,输出两个整数——分别是可以打开的最小和最大灯数。

示例

输入 #1

5
1
0 0
1
0 1
1
1 1
3
0 0 1 0 1 0
3
0 1 1 1 0 0

输出 #1

0 0
1 1
0 0
0 2
1 3

注意

在第一个测试用例中,电路中只有一个灯,并且没有开关打开,因此灯肯定是关闭的。

在第二个测试用例中,电路中只有一盏灯,但与其连接的一个开关是打开的,因此灯是亮的。

在第三个测试用例中,电路中只有一个灯,并且两个开关都打开,因此灯因切换两次而关闭。

在第四个测试用例中,为了不亮灯,开关可以这样排列:

- 开关 $$$1$$$ 和开关 $$$4$$$ 连接到灯 $$$1$$$。由于两个开关都关闭,$$$1$$$ 灯也关闭。
- 开关 $$$2$$$ 和开关 $$$6$$$ 连接到灯 $$$2$$$。由于两个开关都关闭,$$$2$$$ 灯也关闭。
- 开关 $$$3$$$ 和开关 $$$5$$$ 连接到灯 $$$3$$$。两个开关都打开,因此灯 $$$3$$$ 从最初的关闭状态切换两次,因此也保持关闭状态。

要让 $$$2$$$ 灯亮起,开关可以这样排列:

- 开关 $$$1$$$ 和开关 $$$2$$$ 连接到灯 $$$1$$$。由于两个开关都关闭,$$$1$$$ 灯也关闭。
- 开关 $$$3$$$ 和开关 $$$4$$$ 连接到灯 $$$2$$$。由于开关 $$$3$$$ 打开且开关 $$$4$$$ 关闭,因此灯 $$$2$$$ 从其初始关闭状态切换一次,因此它打开。
- 开关 $$$5$$$ 和开关 $$$6$$$ 连接到灯 $$$3$$$。由于开关 $$$5$$$ 打开且开关 $$$6$$$ 关闭,因此灯 $$$3$$$ 从其初始关闭状态切换一次,因此它打开。