CF1102A Integer Sequence Dividing

题目描述

给定一个整数序列 $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)|$ 的最小可能值。

3

0

5

1

6

1

说明/提示

以下是部分样例的可能答案：

在第一个样例中，你可以将初始序列划分为 $A = \{1, 2\}$ 和 $B = \{3\}$，此时答案为 $0$。

在第二个样例中，你可以将初始序列划分为 $A = \{1, 3, 4\}$ 和 $B = \{2, 5\}$，此时答案为 $1$。

在第三个样例中，你可以将初始序列划分为 $A = \{1, 4, 5\}$ 和 $B = \{2, 3, 6\}$，此时答案为 $1$。

由 ChatGPT 4.1 翻译