TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

92.3% (24/26)

Submission's AC Ratio

53.8% (49/91)

Tags

Description

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

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

若一個圖G邊集的子集E,滿足對於所有e1,e2Ee1e2e1,e2沒有公共頂點,則稱E是一個G上的匹配。
G上的匹配E,滿足對於所有G上的匹配E都有|E||E|,則稱E是一個G上的最大匹配。

我們將一條邊記為(a,b),代表這條邊的兩端點的編號分別是a,b,且a<b
若兩條邊x=(a,b),y=(c,d)滿足a<ca=cb<d,則定義x<y
定義一個邊集E的排序S(E)=(e1,e2,,ek)代表將E中所有邊由小到大排序後形成的序列。(即e1<e2<<ekE={e1,e2,,ek}
定義邊集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
對於所有測資,2N2345678

Output Format

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

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

Sample Input 1

31

Sample Output 1

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

No. Testdata Range Constraints Score
1 0~2 N10 10
2 3~5 N1000 30
3 6~9 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 1
2 1000 131072 262144 1
3 1000 131072 262144 2
4 1000 131072 262144 2
5 1000 131072 262144 2
6 1000 131072 262144 3
7 1000 131072 262144 3
8 1000 131072 262144 3
9 1000 131072 262144 3