마피아
시간 제한2초메모리 제한128 MB
죄책감 점수와 반응 행렬이 주어질 때, 마피아 은진이 밤마다 한 명을 제거하며 최대한 오래 살아남을 수 있는 밤의 최대 횟수를 구한다.
문제
은진이는 마피아 게임에서 자신이 마지막으로 남은 마피아라는 사실을 알게 되었다. 나머지 참가자는 모두 시민이며, 참가자 번호는 0번부터 N-1번까지이다.
게임은 생존자 수에 따라 밤과 낮을 번갈아 진행한다. 생존자가 짝수 명이면 밤이고, 홀수 명이면 낮이다. 마피아가 사라지면 시민이 이기고, 시민이 모두 사라지면 마피아가 이긴다. 이 조건이 만족되는 즉시 게임은 끝난다.
각 참가자에게는 유죄 지수가 있다. 낮에는 생존자 중 유죄 지수가 가장 높은 참가자가 죽는다. 그런 참가자가 여러 명이면 번호가 가장 작은 참가자가 죽는다. 낮에는 유죄 지수가 변하지 않는다.
밤에는 은진이가 죽일 참가자 한 명을 고른다. 참가자 i가 밤에 죽으면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.
은진이가 매번 최적으로 선택하여 게임을 최대한 오래 끌 때, 지나갈 수 있는 밤의 최대 횟수를 구하라.
입력
첫째 줄에 참가자 수 N이 주어진다.
둘째 줄에 각 참가자의 유죄 지수 N개가 주어진다.
다음 N개 줄에는 반응 배열 R이 주어진다. 각 줄에는 정수 N개가 있으며, i번째 줄의 j번째 수가 R[i][j]이다.
마지막 줄에 은진이의 참가자 번호가 주어진다.
N은 16 이하의 자연수이다. 유죄 지수는 300 이상 800 이하의 자연수이다. R에 있는 모든 수는 절댓값이 1 이상 26 이하인 정수이다.
출력
은진이가 최적으로 플레이할 때 지나갈 수 있는 밤의 최대 횟수를 출력한다.