← 返回题目列表

Codeforces · 1439/E

E. 作弊并获胜

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

让我们考虑一个 $$$(10^9+1) \times (10^9+1)$$$ 字段。行用从 $$$0$$$ 到 $$$10^9$$$ 的整数进行编号,列用从 $$$0$$$ 到 $$$10^9$$$ 的整数进行编号。我们将位于 $$$x$$$ 行和 $$$y$$$ 列的单元格定义为 $$$(x, y)$$$。

我们称一个单元格为$$$(x, y)$$$ 好,如果$$$x \& y = 0$$$,其中$$$\&$$$ 是按位与运算。

让我们构建一个图,其中顶点将是场中的所有好单元,并且我们将在所有相邻的好单元对之间创建一条边。可以证明该图是一个无环的树连通图。让我们把这棵树挂在顶点 $$$(0, 0)$$$ 上,这样我们就会有一个根为 $$$(0, 0)$$$ 的有根树。

两名玩家将玩游戏。最初,一些好的细胞是黑色的,另一些是白色的。每个玩家轮流选择一个黑色的好单元格及其祖先的子集(可能是空的)并反转它们的颜色(从白色到黑色,反之亦然)。不能移动的玩家(因为所有好的单元格都是白色的)就输了。可以证明博弈总是有限的。

最初,所有单元格都是白色的。您将获得 $$$m$$$ 单元格对。对于每一对,将它们之间的简单路径中的所有单元格着色为黑色。请注意,我们不会反转它们的颜色,而是将它们涂成黑色。

Sohrab 和 Mashtali 将玩这个游戏。索拉博(Sohrab)是第一位玩家,马什塔利(Mashtali)是第二位。

Mashtali 想要获胜并决定作弊。他可以在游戏开始之前多次进行以下操作:选择一个单元格并反转它与树根之间的路径上的所有顶点的颜色。

看着他们的 Mammad 想知道:“为了制定获胜策略,Mashtali 应该执行的最少操作次数是多少?”。

找到树的初始绘画问题的答案。可以证明,至少一种可能的作弊方式总是存在的。

输入

第一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 10^5$$$)。

接下来的 $$$m$$$ 行包含四个整数 $$$x_{1}$$$, $$$y_{1}$$$, $$$x_{2}$$$, $$$y_{2}$$$ ($$$0 \leq x_i, y_i \leq 10^9$$$, $$$x_i \& y_i = 0$$$)。您应该将顶点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的路径上的所有单元格着色为黑色。

输出

打印一个整数——第二个玩家可以进行的最少作弊操作数。

示例

输入 #1

1
7 0 0 7

输出 #1

1

输入 #2

3
1 2 3 4
3 4 1 2
2 1 3 4

输出 #2

3

输入 #3

2
0 1 0 8
1 0 8 0

输出 #3

0

注意

在第一个测试中,您可以对树的根进行一次作弊操作。之后,第二个玩家可以获胜,因为他可以使用对称策略。

在第二个测试中,您可以对单元格$$$(0, 2), (0, 0), (3, 4)$$$进行作弊操作。

在第三次测试中,第二名玩家已经有了获胜策略,不需要进行任何作弊操作。