Integer Sequence Dividing

將 $[1, n]$ 所有數分兩堆，使得兩堆之間的差最小

題解

有一個觀察是: 四個四個一組來看的話，舉個例來說 $1, 2, 3, 4$ 可以分成 $1, 4$ 和 $2, 3$ 兩組，使得差值為$0$。

所以對於 $[1, n]$ 區間，如果對於 $mod\ 4$ 來討論

1. 餘數0 $\rightarrow$ 可以完美分堆，所以差為$0$
2. 餘數1 $\rightarrow$ 把$1$拿出來，其餘人可以四個四個一組，所以差為$1$
3. 餘數2 $\rightarrow$ 中間兩數字不參與分堆，其餘人可以四個四個一組，所以差為中間兩數字之差，也是$1$
4. 餘數3 $\rightarrow$ 舉例子看，以$1, 2, 3, 4, 5, 6, 7$來說, $1$先不參與分組，$[2, 7]$的中間兩數字也不參與分組($4, 5$)，其餘人可以四個四個一組，所以目前差為$0$。剩餘的三個數字($1, 4, 5$)，因為中間兩數字差為$\mid 5-4 \mid = 1$，可以把剛剛留下的$1$分給小的那堆(亦即$1+4$)，所以可以將差值從$1$再降為$0$。

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
	int n;
	scanf("%d", &n);

	n %= 4;
	if (n == 1 || n == 2)
		printf("1\n");
	else
		printf("0\n");

	return 0;
}