마스터마인드 II

시간 제한1초메모리 제한128 MB

요약

길이가 c인 숨은 코드와 주어진 c개 코드 사이의 A/B 점수가 주어질 때, 모든 점수를 만족하는 코드 가운데 사전순으로 가장 앞선 것을 찾는다.

난이도: 보통10점 중 7점
유형: 완전 탐색, 백트래킹, 구현, 조합론
정답자: 아직 제출이 없습니다

문제

다음 조건을 모두 만족하는 수열을 생각하자.

수열의 길이는 $c$ 이다.
각 원소는 $1$ 부터 $9$ 까지의 숫자이다.
같은 숫자가 수열 안에서 두 번 이상 나오지 않는다.

이러한 수열을 코드라고 부른다.

두 코드가 주어지면 두 개의 수로 두 코드의 호환도를 측정한다.

$A$ 는 두 코드에 모두 등장하면서 같은 위치에 있는 숫자들의 합이다.
$B$ 는 두 코드에 모두 등장하지만 서로 다른 위치에 있는 숫자들의 합이다.

고정되어 있지만 알 수 없는 하나의 코드가 있다. $c$ 개의 코드와, 각 코드가 이 알 수 없는 코드와 갖는 호환도 $(A, B)$ 가 주어진다. 주어진 모든 호환도와 일치하는 코드를 찾아라.

입력

첫째 줄에 정수 $c$ ( $1 \le c \le 9$ )가 주어진다.

다음 $c$ 개의 줄에는 주어진 코드 하나와, 그 코드가 알 수 없는 코드와 갖는 호환도가 적혀 있다. 각 줄에는 공백 하나로 구분된 $c + 2$ 개의 음이 아닌 정수가 있다. 처음 두 정수는 이 코드의 호환도 $A$ 와 $B$ 이고, 나머지 $c$ 개의 정수는 코드를 이루는 서로 다른 숫자들( $1$ 부터 $9$ 까지)이다.

출력

공백 하나로 구분한 $c$ 개의 숫자를 출력한다. 이 숫자들은 하나의 코드( $1$ 부터 $9$ 까지의 서로 다른 숫자)를 이루며, 주어진 모든 코드와의 호환도가 입력과 일치해야 한다.

적어도 하나의 코드가 존재함이 보장된다. 조건을 만족하는 코드가 여러 개라면 사전순으로 가장 앞서는 코드를 출력한다(두 코드를 왼쪽부터 한 숫자씩 비교한다).

예제1

예제 1
입력
```
3
4 0 4 9 7
0 10 6 7 4
0 5 9 4 1
```
예상 출력
```
4 1 6
```