TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

73.3% (11/15)

Submission's AC Ratio

61.5% (16/26)

Description

建構一個有$2N$個點的無向簡單圖,其中頂點編號為$0$到$2N - 1$的整數,且圖中編號$i$和$j$的頂點之間有邊($i\neq j$)若且惟若$4N-i-j$是質數。我們稱這個圖為質數圖$G_N$。
在這題,你必須求出$G_N$上最小字典序的最大匹配(即是圖中包含最多邊的邊集,使得任兩條在集合中的邊皆沒有公共頂點)。

所謂「最小字典序的最大匹配」,定義如下:

若一個圖$G$邊集的子集$E$,滿足對於所有$e_1,e_2\in E$且$e_1\neq e_2$,$e_1,e_2$沒有公共頂點,則稱$E$是一個$G$上的匹配。
若$G$上的匹配$E$,滿足對於所有$G$上的匹配$E'$都有$|E'|\leq |E|$,則稱$E$是一個$G$上的最大匹配。

我們將一條邊記為$(a,b)$,代表這條邊的兩端點的編號分別是$a,b$,且$a<b$。
若兩條邊$x=(a,b), y=(c,d)$滿足$a<c$或$a=c \land b<d$,則定義$x<y$。
定義一個邊集$E$的排序$S(E)=(e_1,e_2,\cdots,e_k)$代表將$E$中所有邊由小到大排序後形成的序列。(即$e_1<e_2<\cdots<e_k$且$E=\{e_1,e_2,\cdots,e_k\}$)
定義邊集$E$的字典序比另一個邊集$F$小,若且唯若$S(E)$的字典序比$S(F)$的字典序小。

例如:當$N=4$時,$\{ (0, 3), (1, 2), (4, 5), (6, 7) \}$ 的字典序比 $\{ (0, 3), (1, 2), (4, 7), (5, 6) \}$小。

Input Format

輸入只有一行,包含一個正整數$N$。
對於所有測資,$2\leq N\leq 2345678$。

子任務(測資) 額外限制 分數
1 (0~2) $N \leq 10$ 10
2 (3~5) $N \leq 1000$ 30
3 (6~9) 無限制 60

Output Format

令$X$代表最大匹配的大小(即選定邊集的大小)。
輸出$X$行,每行輸出兩個整數$(a,b)$,代表邊$(a,b)$在$G_N$上最小字典序的最大匹配。注意輸出時必須先將所有邊由小到大排序後輸出,且輸出時$a < b$(即編號小的頂點在前)。

注意到由於有字典序的限制,因此答案是唯一的。

Sample Input

31

Sample Output

0 11
1 10
2 9
3 8
4 7
5 6
12 15
13 14
16 19
17 18
20 21
22 23
24 27
25 26
28 29
30 33
31 32
34 37
35 36
38 39
40 41
42 45
43 44
46 47
48 53
49 52
50 51
54 57
55 56
58 59
60 61

Hints

注意本題輸出量極大。使用C++作答的同學,輸出換行時請使用'\n'代替std::endl,以避免執行時間超過限制。

Problem Source

Problem set by rsabcmoi
建國中學107學年度校隊選拔:複試pE

Subtasks

For Testdata: 0 ~ 2, Score: 10
For Testdata: 3 ~ 5, Score: 30
For Testdata: 6 ~ 9, Score: 60
No. Time Limit (ms) Memory Limit (KiB)
0 1000 131072
1 1000 131072
2 1000 131072
3 1000 131072
4 1000 131072
5 1000 131072
6 1000 131072
7 1000 131072
8 1000 131072
9 1000 131072