23986번 - Big Buttons 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 20 초 (추가 시간 없음) | 1024 MB | 10 | 9 | 8 | 88.889% |
문제
You are a contestant on a popular new game show and are playing for the grand prize!
There are two big buttons, a red one and a black one. You will make a sequence of exactly N button presses.
There are lots of different sequences of presses you could make, but there are P forbidden prefixes, each of length no greater than N. If you make a sequence of presses which begins with any of the forbidden sequences, you will not win the grand prize. It is fine for your sequence to contain one or more forbidden prefixes as long as they do not appear at the start of your sequence.
A winning sequence must consist of exactly N button presses and must not begin with one of the forbidden prefixes. How many different winning sequences are there?
입력
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing two integers N and P, as described above. Then, there are P more lines, each of which contains a string of between 1 and N characters, inclusive, describing one of the forbidden sequences of presses. An R represents pressing the red button, whereas a B represents pressing the black button.
출력
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of winning sequences, as desribed above.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ P ≤ min(2N, 100).
- Each forbidden prefix is between 1 and N characters long, inclusive.
- No two forbidden prefixes will be the same.
Test Set 1 (9점)
- 1 ≤ N ≤ 10.
Test Set 2 (13점)
- 1 ≤ N ≤ 50.
예제 입력 1
3 3 2 BBB RB 5 1 R 4 3 R B RBRB
예제 출력 1
Case #1: 5 Case #2: 16 Case #3: 0
In the first case, you must make a sequence of 3 presses. There are 8 possible sequences of three presses, but some of them will cause you to lose the game. They are listed below:
RBB. This is forbidden since it starts with the first forbidden sequence (RB).RBR. This is forbidden since it starts with the first forbidden sequence (RB).BBB. This is forbidden since it starts with the second forbidden sequence (BBB).
Thus, there are only 5 winning sequences.
In the second case, you must make a sequence of 5 presses. There is only one forbidden sequence, which is R. This means that the first press must be B, and the next 4 presses can be either button. This gives a total of 16 different button presses.
In the third case, you must make a sequence of 4 presses. There are three forbidden sequences, but since every possible sequence begins with either R (the first forbidden sequence) or B (the second forbidden sequence), there are no winning sequences. So the answer is 0.
예제 입력 2
1 50 5 BRBRBBBRBRRRBBB BRBRBRRRBRRRBRB BBBRBBBRBRRRBBB BRBRBRRRBRRRB BRBRBBBRBBBRB
예제 출력 2
Case #1: 1125556309458944
출처
Contest > Google > Kick Start > Google Kick Start 2018 > Round H A번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호