코딩도장 - VonNeumannAirport

VonNeumannAirport

ACM 항공사는 모항으로 폰 노이만 공항을 가진 지역 항공사이다.

많은 승객들에게, 폰 노이만 공항은 그들 여행의 출발점이 아니고,

그들의 마지막 도착지도 아니어서, 많은 갈아타는 승객들이 공항을 통하여 지나간다.  

 

폰 노이만 항공사는 복도 배치를 가지고 있다.

도착 출입문들이 복도의 북쪽에 같은 일정한 간격으로 위치해 있다.

출발 출입문들은 마찬가지로 일정한 간격으로 복도의 남쪽에 있다.

두 개의 인접한 출입문들의 거리는 복도의 폭과 같다.

각 도착 출입문은 정확하게 하나의 도시에 할당되어 있고, 그리고 출발 출입문들도 동일하게 점유한다.

 

승객들은 그들의 기원 도시에 할당된 도착 출입문에 도착해서, 터미널로 나가거나,

그들의 대상 도시에 할당된 출입문에서 갈아타는 항공편로 간다. 이 문제에서는, 오직 갈아타는 항공편을 가진 승객들만을 고려되어진다.  

 

갈아타는 승객들은 복도에 많은 교통량을 생성한다.

도시들 간의 여행하는 사람들의 평균은 사전에 알려져 있다.

이 정보를 사용해서, 가능한한 교통량을 줄일 수 있다.

만약 Cx 도시에서 Cy 도시로의 승객들이 매우 자주 발생한다면,

그들 도시들을 가까이나 상호간에 반대편에 직접 할당된 출입문을 위치시켜서 도울 것이다.  

 

가게들과 정원들의 존재 때문에 복도를 대각선으로 가로지르는 것은 가능하지 않아서,

도착하는 G1 출입문과 출발하는 G3 출입문(도표를 봐라)의 거리는 1 + 2 = 3 이다.  

 

당신은 몇 개의 다른 설정들에 대해서 총 교통량 부하를 평가해야만 한다.

기원 출입문과 대상 출입문들 간의 교통량 부하는 기원에서 대상으로 승객들의 숫자와

도착하는 출입문과 출발하는 출입문 간의 거리의 곱으로 정의되어 진다.

 

그 총 교통량 부하는 모든 기원-대상 쌍들의 합이다.  

 

입력

입력 파일은 여러 개의 테스트 경우들을 포한한다. 입력파일에서 마지막 테스트 경우는 숫자 0을 포한하는 한 개의 라인이 따라온다.  

각 테스트 경우는 2개의 부분들을 가진다. 첫 번째는 교통량 데이타, 그 뒤는 설정 영역.  

 

교통량 데이타는 도시들의 숫자를 나타내는 정수 N(1 < N < 25)으로 시작한다.

따라오는 N 라인들은 각각 한 개 도시에대한 교통량 데이타를 나타낸다.

교통량 데이타를 가진 각 라인은 기원 도시를 식별하는 1에서 N의 범위를 가진 정수로 시작한다.

이것은 모든 대상 도시에 대해서 한쌍씩, 정수 k 쌍들이 따라온다.

각 쌍은 대상 도시와 기원 도시에서 이 대상 도시로 여행하는 승객들의 수(최대 500)를 식별한다.  

 

설정 영역은 하나나 그 이상(최대 20)의 설정들로 구성되고 숫자 0을 포한하는 한 라인으로 끝난다.  

설정은 3개의 라인들로 구성한다. 첫 번째 라인은 설정을 식별하는 양수를 포함한다.

다음 라인은 도착 출입문들이 할당된 도시들의 순열이다.

첫 번째 숫자는 첫 번째 문에 할당된 도시를 나타내고, 등등. 다음 라인은 같은 방법으로 출발 출입문들이 할당된 도시들을 나타낸다.  

 

출력

각 테스트의 경우에, 출력은 설정 숫자들과 총 교통량 부하를 오름차순으로 나타내는 표를 포함한다.

만약 두 개의 설정들이 동일한 교통량 부하를 가진다면,

가장 작은 설정 숫자가 첫 번째로 오게된다. 다음 출력 형식은 아래 샘플이 보여준다.  

 

Sample Input

3  

1 2 2 10 3 15  

2 1 3 10  

3 2 1 12 2 20  

1  

1 2 3  

2 3 1  

2  

2 3 1  

3 2 1  

0  

2  

1 1 2 100  

2 1 1 200  

1  

1 2  

1 2  

2  

1 2  

2 1  

0  

0  

 

Output for the Sample Input

Configuration   Load

2       119

1       122

Configuration   Load

2       300

1       600

출처 : http://xper.org/wiki/seminar/VonNeumannAirport