이 호텔 방들은 배열 2행 열 배열 로 나타낼 수 있다. 여기서 각 방은 로 나타낸다. 이고 또는 이고 이면, 두 방 와 은 인접하다고 한다.
이 호텔에 묵을 계획인 예약자들이 예약 시스템을 통해서 방을 배정받으려고 한다.
예약자들의 총 수는 이고, 예약자들의 전체 집합 에 대해서, 는 집합 으로 나뉜다. 다시 말해서, .
또한 임의의 두 집합 에 대해서, 이고, 모든 집합 는 적어도 5명의 예약자를 포함한다. 다시 말해서, .
예약 시스템은 방 하나에 한 사람씩 배정한다. 다시 말해서, 임의의 배정 는 예약자들의 집합에서 방들의 집합으로 일대일 대응이다.
또, 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정 받아야 한다. 한 덩어리의 방들이란 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다.
각 예약자 는 스트레스 지수 를 가진다.
예약 시스템의 배정 에서, 인접한 두 방에 각각 배정된 예약자 와 가 서로 다른 집합에 속하면, 충돌 가 발생한다고 하고, 의 페널티는 로 주어진다.
그러면 배정 의 페널티 는 에서 발생하는 모든 충돌들의 페널티 합으로 정의한다.
예약 시스템은 페널티 를 최소화하는 배정 를 찾아야 한다.
예를 들어, 호텔에 12개의 방이 있고, 12명의 예약자는 각각 6명씩 2개의 집합 과 로 나뉜다. 예약자들의 스트레스 지수는 모두 1이다.
방들을 2행 6열 배열 로 나타낼 때, 의 홀수 열에 에 속한 예약자들을 짝수 열에 에 속한 예약자들을 배정한다면,
같은 행의 인접한 두 방 사이에 충돌이 발생하고, 각 충돌에 2의 페널티가 주어진다. 이 경우 모두 10개의 충돌이 생기고 총 20의 페널티가 주어진다.
(물론, 이 경우는 한 덩어리 조건도 만족하지 못한다.)
이 예에서는 2개의 충돌에서 4의 페널티가 생기는 배정이 최적이다.
그림 1
제한시간: 전체 테스트 케이스는 67개 이하이며, 전체 수행 시간은 3초 이내. (Java 6초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.<br />
C에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다. ※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
제출 제한 : 최대 20회
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,
이후 차례로 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 두 정수 과 이 주어진다 .
여기서, 은 예약자들의 집합의 개수이고, 호텔에 개 방이 있음을 나타낸다.
다음 개 줄의 번째 줄에는 집합 에 속한 예약자들의 수를 나타내는 정수 와 각각 의 예약자들의 스트레스 지수를 나타내는 개의 정수 가 주어진다 .
점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 190점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 ( 37점) : 이 그룹의 테스트 케이스에서는 모든 가 짝수이다.
ㆍ 그룹 2 ( 51점) : 이 그룹의 테스트 케이스에서는 모든 가 홀수이다
ㆍ 그룹 3 ( 102점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
모든 테스트 케이스를 풀지 않고 일부분의 그룹에 속하는 테스트 케이스만을 푸는 경우에도 입력 받은 모든 케이스에 대해 (답이 틀릴지라도) 출력 양식에는 맞는 출력을 생성해야 점수가 반영되는 것이 보장된다.
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며, 그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.
예약시스템의 가능한 모든 배정 중 페널티가 가장 작은 배정을 찾아서 그 최소 페널티를 출력한다.