31453번 - 카드 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 42 | 28 | 13 | 68.421% |
문제
두 어린이 Albert와 Bob은 종종 카드게임을 한다. 양수가 적힌 카드 $N$장과 음수가 적힌 카드 $N$장을 이용한 게임을 하는데, 각 카드에는 절댓값이 1이상 $N$ 이하의 정수가 적혀있고, 같은 정수가 두 장 이상의 카드에 적힌 경우는 없다. 즉 $-N$ 부터 $-1$, 그리고 $1$부터 $N$까지의 정수가 각각 한 번씩 등장한다.
우선, 두 어린이는 카드를 잘 섞은 후 각자 $N$장씩 가져간다 -- 카드가 총 $2N$ 장 이므로, 각 어린이는 자신의 카드 $N$ 장을 확인하면 상대방이 가진 카드 $N$장이 무엇인지 알 수 있다. 이후 총 $N$ 턴 동안 게임을 진행하는데, 각 턴에 각자 한 장씩의 카드를 동시에 내서 아래 규칙에 따라 점수를 매긴다.
- 두 카드에 적힌 수의 부호가 같다면 (즉, 둘 다 음수이거나 둘 다 양수라면), 절댓값이 큰 카드를 낸 사람이 1점을 얻는다.
- 두 카드에 적힌 수의 부호가 다르다면, 동생인 Albert가 1점을 얻는다.
마지막 $N$번째 턴을 마친 후에 각자 점수의 총합을 구했더니 Albert의 점수는 $M$ 점이었다. Albert는 본인이 어떤 순서로 자신의 $N$장의 카드를 냈는지 정확히 기억하지만, Bob이 어떤 순서로 카드를 냈는지는 기억하지 못한다. Albert는 문득 궁금해졌다: 자신은 카드를 낸 순서를 바꾸지 않을 때, Bob이 어떤 순서로 그의 카드를 플레이할 때 Albert가 그대로 $M$점을 얻을 수 있을까?
편의상 $i$번째 턴에 Albert가 낸 카드에 적힌 수를 $X[i]$라 하고 Bob이 낸 카드에 적힌 수를 $Y[i]$라 하자.
예를 들어 $N = 3$, $M = 1$ 이고 $X = [1, -1, 2]$ 라고 하면, Bob이 가진 카드는 $[-3, -2, 3]$ 임을 알 수 있다 - 이렇게 세 장의 카드를 임의의 순서로 플레이 하는 경우는 $3! = 6$ 가지 있고, 아래와 같이 Albert의 최종 점수가 1이 되는 경우는 4가지 존재한다.
- $Y = [-3, -2, 3]$: Albert는 1번째 턴에 1점을 얻고 나머지 턴에 점수를 얻지 못해 총점이 1점이 된다.
- $Y = [-3, 3, -2]$: Albert는 모든 턴에 점수를 얻어 총점이 3점이 된다.
- $Y = [-2, -3, 3]$: Albert는 1번째 턴에 1점을 얻고 나머지 턴에 점수를 얻지 못해 총점이 1점이 된다.
- $Y = [-2, 3, -3]$: Albert는 모든 턴에 점수를 얻어 총점이 3점이 된다.
- $Y = [3, -3, -2]$: Albert는 3번째 턴에 1점을 얻고 나머지 턴에 점수를 얻지 못해 총점이 1점이 된다.
- $Y = [3, -2, -3]$: Albert는 3번째 턴에 1점을 얻고 나머지 턴에 점수를 얻지 못해 총점이 1점이 된다.
입력으로 $N$, $M$, $X$가 주어졌을 때, Albert가 정확히 $M$점을 얻게 되도록 하는 Bob의 카드 내는 순서의 총 수를 구해보자. 위 예제의 경우 정답은 4가 된다.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$, $M$이 공백으로 구분되어 주어진다. 둘째 줄에는 Albert가 플레이 한 카드에 적힌 $N$개의 정수 (즉, 배열 $X$)가 공백으로 구분되어 주어진다.
출력
각 줄에 각 테스트 케이스의 정답을 출력한다.
제한
- $1 \le T \le 10$
- $1 \le N \le 15$
- $0 \le M \le N$
- $1 \le i \le N$ 인 각 $i$에 대하여: $1 \le | X[i] | \le N$ (여기서 $|x|$ 는 $x$ 의 절댓값이다)
- $i \ne j$ 이면서 $X[i] = X[j]$ 인 경우는 없다 (즉, 배열 $X$에 중복된 원소는 없다)
예제 입력 1
7 3 3 1 2 3 3 1 1 -1 2 3 3 1 2 -3 3 0 -1 -2 3 11 11 1 2 3 4 5 6 7 8 9 10 -11 11 10 1 2 3 4 5 6 7 8 9 -10 -11 11 9 1 2 3 4 5 6 7 8 -9 -10 -11
예제 출력 1
6 4 2 0 3628800 13063680 20321280
예제 1: Bob이 가진 카드는 $[-1, -2, -3]$ 임을 알 수 있다. 어떤 순서로 플레이 하더라도 두 카드에 적힌 수의 부호가 다르므로 Albert가 매번 점수를 얻어 총 3점을 얻게된다.
예제 2: 본문에서 다루었다
예제 3: 추가 설명 없음
예제 4: Bob이 가진 카드는 $[1, 2, -3]$ 임을 알 수 있다. Bob이 어떤 순서로 카드를 내더라도 Albert가 최소 1점을 얻게 되므로 정답은 0이 된다.
예제 5-7: 추가 설명 없음
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호