실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 512 MB |
COVID-19의 유행 동안 격리된 구역에서 과학자들은 지루함을 덜기 위한 새로운 방법을 생각해냈습니다. 그것은 고급 물리학을 공부하기! 실제로, 그들은 새로운 소립자를 발견해냈고, 그것을 "무 입자"라 명명했습니다.
과학자들은 현재 ()개의 무 입자로 실험을 진행 중입니다. 입자 는 와 라는 두 정수로 표현되는 "스핀"을 가지며, 이 두 정수는 범위 내에 있습니다. 가끔 두 개의 무 입자는 상호작용합니다. 이 상호작용은 스핀이 인 입자와 인 입자 사이에서만 발생할 수 있으며, 이때 그리고 조건을 만족해야 합니다. 이러한 조건 하에서, 이 두 입자 중 정확히 하나가 사라질 수 있습니다(다른 입자에는 아무 일도 일어나지 않습니다).
주어진 시간에 최대 한 번의 상호작용만 일어날 수 있습니다.
과학자들은 임의의 상호작용 순서 후에 남을 수 있는 무 입자의 최소 개수를 알고 싶어합니다.
첫 번째 줄에는 무 입자의 초기 개수인 단일 정수 이 들어 있습니다.
다음 행 각각에는 한 입자의 스핀을 나타내는 두 정수가 공백으로 구분되어 있습니다.
각 입자는 구별되는 스핀을 가지고 있습니다.
임의의 상호작용 순서 후에 남을 수 있는 무 입자의 최소 개수를 나타내는 단일 정수를 출력하세요.
4 1 0 0 1 -1 0 0 -1
1
3 0 0 1 1 -1 3
2
상호작용이 이루어질 수 있는 한가지 순서:
오직 입자 2만 남습니다.
샘플 입력:
3
0 0
1 1
-1 3
샘플 출력:
2
입자 3는 다른 두 입자들과는 상호작용할 수 없으므로 그것은 반드시 남아 있어야 합니다. 입자 1과 2 중 적어도 하나는 남아 있어야합니다.
점수:
출처: USACO 2020 US Open Contest, Silver Problem 3. The Moo Particle