소들은 평소와 같이 어설프게 주사위를 굴리는 게임인 Yahtzee를 즐기고 있습니다. 소들은 S개(1 <= S <= 8)의 면이 있는 N개(1 <= N <= 20)의 주사위를 굴립니다. 그들은 ("3개의 2를 포함하는" 또는 "1개의 2와 2개의 3을 포함하는"과 같은) 특정 조건에 맞는, 주사위를 굴리는 경우의 수를 알고 싶어합니다.
소들이 경우의 수를 배울 수 있도록 도와주세요. N, S와 소들이 제시한 기준을 나타낸 여러 수식을 입력받은 후, 아래 조건에 맞는 프로그램을 작성하세요. 주사위를 굴릴 수 있는 모든 경우의 수에 대해, 입력받은 수식을 충족시키는 경우의 수를 세야 합니다. (참고로, 면이 2개인 주사위 3개를 굴리는 모든 경우의 수는 {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2}입니다.)
각 수식은 "적어도 W개 이상의 R가 나와야 한다"는 것을 표현하는 기본 양식의 조합으로 구성됩니다. 이때 기본 양식은 0 <= W <= N, 1 <= R <= S를 충족하는 다음의 수식으로 표현할 수 있습니다.
WxR
각 테스트 케이스마다 E개(1 <= E <= 20)의 수식이 입력되는데, 각 수식은 1개 이상 10개 이하의 위 기본 양식이 0~9개의 '+'로 연결된 형식으로 주어집니다. (이때 '+'는 AND를 의미합니다.) 또한, 각 E개의 수식은 서로 'inclusive OR' 조건으로 묶여 있습니다. 그러므로, 아래 표현은 "3개 이상의 5를 포함하거나, 1개 이상의 3과 2개 이상의 4를 포함할 것"을 의미합니다.
3x5
1x3+2x4
5개의 면을 가진 주사위 4개를 굴릴 때, 위 표현을 만족시키는 주사위 눈의 조합은 {5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3.}입니다.
주의: 1번째 줄에서는 2개 이상의 자연수를 입력받은 후, 2번째 줄부터는 문자열을 입력받아야 합니다. 몇몇 언어들의 경우 입출력 양식이 생각보다 까다로울 수 있습니다! 또한, 채점 데이터에는 주사위를 굴리는 모든 경우의 수가 절대 1,512,768개를 초과하지 않습니다.
--------
[입력]
1번째 줄: 3개의 정수 N, S, E가 공백으로 구분되어 주어집니다.
2번째 줄 이후, E개의 줄: 문제 지문에서 설명한 것과 같이 E개의 수식이 한 줄에 하나씩 문자열로 주어집니다.
--------
[출력]
1번째 줄: S개의 면을 가진 N개의 주사위를 굴리는 모든 경우 중에서, E개의 수식을 만족시키는 경우의 수를 하나의 정수로 출력합니다.
moner_ari 1년 전
[문제]
소들은 평소와 같이 어설프게 주사위를 굴리는 게임인 Yahtzee를 즐기고 있습니다. 소들은 S개(1 <= S <= 8)의 면이 있는 N개(1 <= N <= 20)의 주사위를 굴립니다. 그들은 ("3개의 2를 포함하는" 또는 "1개의 2와 2개의 3을 포함하는"과 같은) 특정 조건에 맞는, 주사위를 굴리는 경우의 수를 알고 싶어합니다.
소들이 경우의 수를 배울 수 있도록 도와주세요. N, S와 소들이 제시한 기준을 나타낸 여러 수식을 입력받은 후, 아래 조건에 맞는 프로그램을 작성하세요. 주사위를 굴릴 수 있는 모든 경우의 수에 대해, 입력받은 수식을 충족시키는 경우의 수를 세야 합니다. (참고로, 면이 2개인 주사위 3개를 굴리는 모든 경우의 수는 {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2}입니다.)
각 수식은 "적어도 W개 이상의 R가 나와야 한다"는 것을 표현하는 기본 양식의 조합으로 구성됩니다. 이때 기본 양식은 0 <= W <= N, 1 <= R <= S를 충족하는 다음의 수식으로 표현할 수 있습니다.
각 테스트 케이스마다 E개(1 <= E <= 20)의 수식이 입력되는데, 각 수식은 1개 이상 10개 이하의 위 기본 양식이 0~9개의 '+'로 연결된 형식으로 주어집니다. (이때 '+'는 AND를 의미합니다.) 또한, 각 E개의 수식은 서로 'inclusive OR' 조건으로 묶여 있습니다. 그러므로, 아래 표현은 "3개 이상의 5를 포함하거나, 1개 이상의 3과 2개 이상의 4를 포함할 것"을 의미합니다.
5개의 면을 가진 주사위 4개를 굴릴 때, 위 표현을 만족시키는 주사위 눈의 조합은 {5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3.}입니다.
주의: 1번째 줄에서는 2개 이상의 자연수를 입력받은 후, 2번째 줄부터는 문자열을 입력받아야 합니다. 몇몇 언어들의 경우 입출력 양식이 생각보다 까다로울 수 있습니다! 또한, 채점 데이터에는 주사위를 굴리는 모든 경우의 수가 절대 1,512,768개를 초과하지 않습니다.
--------
[입력]
--------
[출력]