헨리와 헤티는 최근 피아트라님트의 네트워크 회사에 취직했습니다. 첫 번째 과제는 새로운 형식의 라우터인 혁신적인 이더넷 연결 작동 인터페이스 2016(CEOI 2016)을 만드는 것인데, 구성은 아래와 같습니다.
- 1부터 N까지 번호가 붙은 N개의 입력 노드;
- N+1부터 2xN까지 번호가 붙은 N개의 출력 노드;
- 2xN+1부터 2xN+K까지 번호가 붙은 K개의 내부 노드;
- 서로 다른 노드 쌍을 연결하는 M개의 단일 방향 직접 연결;
아래의 경우 노드 X는 노드 Y에 데이터를 전송할 수 있습니다 (이는 Y가 X에서 데이터를 받을 수 있음을 의미합니다.):
- X = Y, 또는
- 노드 Z와 노드 Y 사이 직접 연결이 존재하고 노드 X에서 노드 Z로 데이터를 전송할 수 있는 노드 Z가 존재.
노드 X에서 노드 Y로 데이터를 보낼 수 있고 X ≠ Y라면, A1 = X이고 AL = Y일 때 어떤 L >= 2에 대해 X에서 Y까지 데이터 경로는 직접 연결 {(A1, A2), (A2, A3), ... (AL-1, AL)}로 정의됩니다.
라우터는 아래의 경우 원활히 작동합니다.
- 각 입력 노드가 각 출력 노드에 데이터를 전송할 수 있음;
- 각 입력 노드가 자신에게만 데이터를 받을 수 있음;
- 각 출력 노드가 자신에게만 데이터를 전송할 수 있음;
- 임의의 두 노드 X와 Y에 대해, X ≠ Y이고 X에서 Y로 데이터를 전송할 수 있으면 Y는 X로 데이터를 전송하지 못함;
- 임의의 두 노드 X와 Y에 대해, X ≠ Y이고 X에서 Y로 데이터를 전송할 수 있으면 X에서 Y로 가는 데이터 경로는 유일함. 달리 말해, 임의의 두 노드 X와 Y는 최대 1개의 직접 연결로만 연결될 수 있음.
다른 모든 전자 기기와 같이, 라우터가 작동하려면 전기가 필요합니다.INX가 X에 데이터를 전송할 수 있는 입력 노드의 수, OUTX가 X에서 데이터를 받을 수 있는 출력 노드의 수를 나타낸다고 할 때, 노드 X를 작동하기 위한 전력을 PX = INX x OUTX로 정의합시다. 라우터가 사용하는 최대 전력을 Pmax = max(P1, P2, ... P2xN+K)로 정의합시다.
프로젝트 담당자는 헨리와 헤티에게 아래와 같은 테스트 라우터를 구축할 때 충족해야 할 기술 요건을 주었습니다. 담당자는 아래의 조건을 만족하는 라우터를 원합니다:
- 정확히 N개의 입력 노드와 N개의 출력 노드가 존재;
- 최대 Mlim개의 직접 연결의 사용;
- 최대 Plim의 최대 전력을 사용;
- 최대 500 000개의 노드를 사용. (총 노드 = Ntot = 2xN + K <= 500 000)
입력
유일한 줄에 세 정수가 주어집니다: 입력 노드와 출력 노드의 수 N; 최대 직접 연결의 수 Mlim; 라우터의 최대 전력 Plim입니다.
이 문제에서 N = 223, Mlim = 1 000 000, Plim = 1 000 000입니다.
출력
하나의 공백으로 구분해 두 정수를 출력합니다: 라우터를 구축할 때 필요한 총 노드의 수를 나타내는 Ntot = 2xN+K과; 직접 연결의 총 개수 M입니다. 다음 M개의 줄에 노드 X에서 노드 Y로 가는 직접 연결을 구축했다는 의미로 정수 쌍 X와 Y를 출력합니다.
ez_code 4년 전 2
문제
헨리와 헤티는 최근 피아트라님트의 네트워크 회사에 취직했습니다. 첫 번째 과제는 새로운 형식의 라우터인 혁신적인 이더넷 연결 작동 인터페이스 2016(CEOI 2016)을 만드는 것인데, 구성은 아래와 같습니다.
- 1부터 N까지 번호가 붙은 N개의 입력 노드;
- N+1부터 2xN까지 번호가 붙은 N개의 출력 노드;
- 2xN+1부터 2xN+K까지 번호가 붙은 K개의 내부 노드;
- 서로 다른 노드 쌍을 연결하는 M개의 단일 방향 직접 연결;
아래의 경우 노드 X는 노드 Y에 데이터를 전송할 수 있습니다 (이는 Y가 X에서 데이터를 받을 수 있음을 의미합니다.):
- X = Y, 또는
- 노드 Z와 노드 Y 사이 직접 연결이 존재하고 노드 X에서 노드 Z로 데이터를 전송할 수 있는 노드 Z가 존재.
노드 X에서 노드 Y로 데이터를 보낼 수 있고 X ≠ Y라면, A1 = X이고 AL = Y일 때 어떤 L >= 2에 대해 X에서 Y까지 데이터 경로는 직접 연결 {(A1, A2), (A2, A3), ... (AL-1, AL)}로 정의됩니다.
라우터는 아래의 경우 원활히 작동합니다.
- 각 입력 노드가 각 출력 노드에 데이터를 전송할 수 있음;
- 각 입력 노드가 자신에게만 데이터를 받을 수 있음;
- 각 출력 노드가 자신에게만 데이터를 전송할 수 있음;
- 임의의 두 노드 X와 Y에 대해, X ≠ Y이고 X에서 Y로 데이터를 전송할 수 있으면 Y는 X로 데이터를 전송하지 못함;
- 임의의 두 노드 X와 Y에 대해, X ≠ Y이고 X에서 Y로 데이터를 전송할 수 있으면 X에서 Y로 가는 데이터 경로는 유일함. 달리 말해, 임의의 두 노드 X와 Y는 최대 1개의 직접 연결로만 연결될 수 있음.
다른 모든 전자 기기와 같이, 라우터가 작동하려면 전기가 필요합니다.INX가 X에 데이터를 전송할 수 있는 입력 노드의 수, OUTX가 X에서 데이터를 받을 수 있는 출력 노드의 수를 나타낸다고 할 때, 노드 X를 작동하기 위한 전력을 PX = INX x OUTX로 정의합시다. 라우터가 사용하는 최대 전력을 Pmax = max(P1, P2, ... P2xN+K)로 정의합시다.
프로젝트 담당자는 헨리와 헤티에게 아래와 같은 테스트 라우터를 구축할 때 충족해야 할 기술 요건을 주었습니다. 담당자는 아래의 조건을 만족하는 라우터를 원합니다:
- 정확히 N개의 입력 노드와 N개의 출력 노드가 존재;
- 최대 Mlim개의 직접 연결의 사용;
- 최대 Plim의 최대 전력을 사용;
- 최대 500 000개의 노드를 사용. (총 노드 = Ntot = 2xN + K <= 500 000)
입력
유일한 줄에 세 정수가 주어집니다: 입력 노드와 출력 노드의 수 N; 최대 직접 연결의 수 Mlim; 라우터의 최대 전력 Plim입니다.
이 문제에서 N = 223, Mlim = 1 000 000, Plim = 1 000 000입니다.
출력
하나의 공백으로 구분해 두 정수를 출력합니다: 라우터를 구축할 때 필요한 총 노드의 수를 나타내는 Ntot = 2xN+K과; 직접 연결의 총 개수 M입니다. 다음 M개의 줄에 노드 X에서 노드 Y로 가는 직접 연결을 구축했다는 의미로 정수 쌍 X와 Y를 출력합니다.