Informatica Online Judge

  표 자르기 [1982 / 07BE]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[AtCoder]

Background

$2 \times \textrm{N}$의 모양의 표가 있다. 표의 각 원소는 절댓값이 1 이상 300 이하인 정수이다.

표에 있는 모든 음수를 원하는 양수로 바꿔 쓰고자 한다. 이 때 다음의 조건을 만족해야 한다.

* 서로 같은 음수끼리는 서로 같은 양수로 바꿔 써야 한다.
* 서로 다른 음수끼리는 서로 다른 양수로 바꿔 써야 한다.

규칙을 만족하도록 모든 음수를 양수로 바꿔 쓴 후, 서로 다른 숫자 사이의 모서리를 모두 가위질해낸다. 그러면 표는 몇 개인가의 조각으로 나뉘게 될 것이다.

조각의 수를 최소화하도록 수를 바꿔 썼을 때의 그 최솟값을 구하시오.

Input

첫째 줄에는 $\textrm{N}$이 주어진다. $(1 \le \textrm{N} \le 100,000)$
둘째 줄과 셋째 줄에는 각각 표의 첫 번째와 두 번째 행의 숫자들이 공백을 사이에 두고 주어진다.
표의 $i$행 $j$열의 원소를 $\textrm{X}_{ij}$라고 하면, $1 \le |\textrm{X}_{ij}| \le 300$.

Output

첫째 줄에 조각의 수를 최소화했을 때의 조각의 수를 출력하시오.

IO Example

입력
6
-1 -1 -1 -1 3 3
3 3 3 3 -4 3

출력
2

설명
예를 들어, -1을 3으로, -4를 10000으로 바꾼 후 표를 가위질하면 총 두 개의 조각으로 나뉜다.
이보다 더 적은 조각이 나오도록 하는 방법은 없으므로, 답은 2이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]