1316 . 晶片設計 Chips

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

$nA-NIl$
用心練題，不要跟我一樣600題還那麼爛

User's AC Ratio

91.2% (52/57)

Submission's AC Ratio

37.9% (66/174)

Tags

IOIwarmup 2008-IOIwarmup-3rd

Description

現在有許多個晶片排成一列，其中兩兩希望連成一對(但一對晶片不一定相鄰)，如下圖所示。
然而一個小小(其實不小)的問題是，由於空間關係，晶片間的連線最多只能列上方一條，列下方一條
也就是同一個鉛直位置最多只有兩條連線經過。
試問給定一列晶片的配對條件，在符合上述連線方式的情況下，最多可以連接幾對晶片？

Input Format

第一行為一個整數n，代表總共有幾對晶片。
接下來有2n個整數，之間用空白或換行分隔，代表由左至右晶片的相連關係，要相連的兩個晶片號碼會相同。
這些整數恰好是1~n。

晶片對數n<=4000

Output Format

一個整數p，代表最多可以連接幾對晶片。

Sample Input 1

6
1 2 3 1 4 5 5 3 2 6 4 6

Sample Output 1

4

Hints

可以連1, 4, 5, 6等四個晶片

Problem Source

原TIOJ1316 / TIOJ IOI Warmup III, 2008. Problemsetter: tmt514, kelvin

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
5 900 65536 262144 6
6 900 65536 262144 7
7 900 65536 262144 8
8 900 65536 262144 9
9 900 65536 262144 10
10 900 65536 262144 11
11 900 65536 262144 12
12 900 65536 262144 13
13 900 65536 262144 14
14 900 65536 262144 15
15 900 65536 262144 16
16 900 65536 262144 17
17 900 65536 262144 18
Submit
Back to Top