RiseOJ – 호환 쌍

설명

깊은 시골에서, 농부 존의 소들은 그저 평범한 농장 동물이 아니다. 그들은 비밀 소 정보 네트워크의 일원이다. 각 소는 엘리트 소 암호학자들이 신중하게 부여한 ID 번호를 가지고 있다. 하지만 농부 존의 다소 엉성한 태그 시스템 때문에, 일부 소들은 같은 ID를 갖게 되었다.

농부 존은 서로 다른 ID 번호가 $$N$$ ( $1\le N\le 2\cdot 10^5$ )개 있으며, 각 서로 다른 ID $$d_i$$ ( $0\le d_i\le 10^9$ )마다 그 ID를 공유하는 소가 $$n_i$$ ( $1\le n_i\le 10^9$ )마리 있다는 것을 확인했다.

소들은 오직 둘씩 짝을 지어서만 통신할 수 있으며, 그들의 비밀 암호화 방식에는 하나의 엄격한 규칙이 있다. 두 소는 서로 다른 소이고 두 소의 ID 번호의 합이 $$A$$ 또는 $$B$$ ( $0\le A\le B\le 2\cdot 10^9$ )와 같을 때에만 정보를 교환할 수 있다. 한 소는 한 번에 하나의 대화에만 참여할 수 있다 (즉, 어떤 소도 둘 이상의 쌍에 속할 수 없다).

농부 존은 최상의 정보 흐름을 보장하기 위해 서로소인 통신 쌍의 수를 최대화하고 싶다. 동시에 이루어질 수 있는 대화의 최대 개수를 구할 수 있겠는가?

Problem credits: Benjamin Qi

제약

SCORING

입력 3-4: $$A=B$$
입력 5-7: $N\le 1000$
입력 8-12: 추가 제약 없음

Problem credits: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ , $$A$$ , $$B$$ 가 주어진다.

다음 $$N$$ 개의 줄에 각각 $$n_i$$ 와 $$d_i$$ 가 주어진다. 어떤 두 $$d_i$$ 도 같지 않다.

출력 형식

동시에 형성될 수 있는 서로소인 통신 쌍의 최대 개수를 출력한다.

이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있음에 유의하라.

예제 1

입력

출력

설명

A cow with an ID of $$0$$ can communicate with another cow with an ID of $$4$$
because the sum of their IDs is $$4$$ . Since there are a total of $$100$$ cows of
ID $$0$$ and $$200$$ cows of ID $$4$$ , there can be up to $$100$$ communicating pairs
with this combination of IDs.

A cow with an ID of $$4$$ can also communicate with another cow with an ID of $$1$$
(sum to $$5$$ ). There are $$10$$ cows of ID $$1$$ and $$100$$ remaining unpaired cows of
ID $$4$$ , allowing for another $$10$$ pairs.

Finally, a cow with an ID of $$2$$ can communicate with another cow of the same
ID. Since there are a total of $$17$$ cows of ID $$2$$ , there can be up to $$8$$ more
pairs.

In total, there are $$100+10+8=118$$ communicating pairs. It can be shown that
this is the maximum possible number of pairs.

예제 2

입력

출력

설명

Pairing IDs $$0$$ and $$4$$ makes $$20$$ pairs, while pairing IDs $$1$$ and $$3$$ makes
$$10$$ pairs. It can be shown that this is the optimal pairing, resulting in a
total of $$30$$ pairs.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > US Open > Silver

올림피아드 > USACO > 2024-2025 > US Open > Silver

태그

JudgeUSACO

호환 쌍

평가 및 의견

풀이 제출