← 返回题目列表

Codeforces · 1102/A

A. 整数序列除法

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

给定一个整数序列 $$$1, 2, \dots, n$$$。您必须将其分为两个集合 $$$A$$$ 和 $$$B$$$,使得每个元素恰好属于一个集合,并且 $$$|sum(A) - sum(B)|$$$ 是最小可能的。

值 $$$|x|$$$ 是 $$$x$$$ 的绝对值,$$$sum(S)$$$ 是集合 $$$S$$$ 的元素之和。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^9$$$)。

输出

打印一个整数 — 如果将初始序列 $$$1, 2, \dots, n$$$ 分为两组 $$$A$$$ 和 $$$B$$$,则 $$$|sum(A) - sum(B)|$$$ 的最小可能值。

示例

输入 #1

3

输出 #1

0

输入 #2

5

输出 #2

1

输入 #3

6

输出 #3

1

注意

示例的一些(不是全部)可能答案:

在第一个示例中,您可以将初始序列分为集合 $$$A = \{1, 2\}$$$ 和 $$$B = \{3\}$$$,因此答案是 $$$0$$$。

在第二个示例中,您可以将初始序列分为集合 $$$A = \{1, 3, 4\}$$$ 和 $$$B = \{2, 5\}$$$,因此答案是 $$$1$$$。

在第三个示例中,您可以将初始序列分为集合 $$$A = \{1, 4, 5\}$$$ 和 $$$B = \{2, 3, 6\}$$$,因此答案是 $$$1$$$。