Saveit

Xedef 택배 회사는 여러 도시 사이에서 항공 택배를 운영한다. 이 도시들 중 일부는 Xedef의 허브로, 특수 처리 시설이 세워져 있다. Xedef의 항공기는 도시 한 쌍 사이를 오가며, 필요에 따라 양방향으로 화물을 운송한다.

어느 도시에서 다른 도시로 화물을 보내려면, 화물을 일련의 구간으로 운송해야 한다. 각 구간은 한 항공기가 담당하는 도시 쌍 사이에서 화물을 운송한다. 또한 이 구간 열에는 Xedef의 허브가 적어도 하나 포함되어야 한다.

경로 설정을 돕기 위해 Xedef는 모든 도시에서 모든 허브까지의 최단 구간 열 길이를 모든 화물의 운송장에 인코딩하려 한다. (허브에서 자기 자신으로 가는 최단 구간 열의 길이는 0이다.) 당연히 이 정보를 압축된 형태로 표현해야 한다.

여러분은 두 프로시저 encode(N,H,P,A,B)와 decode(N,H)를 구현해야 한다. N은 도시의 수이고 H는 허브의 수이다. 도시에는 0부터 N-1까지 번호가 매겨져 있고, 허브는 0부터 H-1까지 번호가 매겨진 도시라고 가정한다. 또한 N ≤ 1000이고 H ≤ 36이라고 가정한다. P는 항공기로 연결된 도시 쌍의 수이다. 모든 (순서 없는) 도시 쌍은 서로 다르다. A와 B는 크기 P의 배열로, 첫 번째로 연결된 도시 쌍은 (A[0],B[0]), 두 번째 쌍은 (A[1],B[1])과 같은 식이다.

encode는 decode가 모든 도시에서 모든 허브까지의 구간 수를 알아낼 수 있는 비트 열을 계산해야 한다. encode는 encode_bit(b) 호출을 통해 비트 열을 채점 서버로 전송한다. 여기서 b는 0 또는 1이다. decode는 decode_bit 호출을 통해 채점 서버로부터 비트 열을 받는다. decode_bit의 i번째 호출은 encode_bit(b)의 i번째 호출에서의 b 값을 반환한다. decode가 decode_bit를 호출하는 횟수는 항상 encode가 이전에 encode_bit(b)를 호출한 횟수 이하여야 한다.

구간 수를 디코딩한 뒤, decode는 모든 허브 h와 모든 도시 c (모든 허브도 포함한다. 즉 c=h인 경우도 포함한다)에 대해 hops(h,c,d)를 호출해야 한다. 여기서 d는 h와 c 사이에서 화물을 보내는 데 필요한 최소 구간 수이다. 즉, hops(h,c,d) 호출이 N*H번 있어야 한다. 호출 순서는 상관없다. 모든 허브와 모든 도시 사이에서 화물을 보낼 수 있음이 보장된다.

참고: encode와 decode는 명시된 인터페이스로만 통신해야 한다. 공유 변수, 파일 접근, 네트워크 접근은 금지된다. C 또는 C++에서는 지속 변수를 static으로 선언해 encode나 decode를 위한 정보를 유지하면서 공유를 막을 수 있다. Pascal에서는 해 파일의 implementation 부분에 지속 변수를 선언할 수 있다.