시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 75 | 20 | 13 | 22.414% |
휴대폰의 잠금 방법 중 가장 흔한 것이 잠금 패턴이다. 잠금을 해제하기 위해서는 주어진 점들을 적절한 방법으로 이어 정해진 모양을 만들어야 한다.
청호의 휴대폰은 4개의 행에 각각 3개의 점이 있는 형태의 잠금 패턴을 사용한다. 아래의 그림은 잠금 패턴의 예시로, 잠금 패턴은 아래와 같이 2차원 평면으로 모델링되며 각각의 점은 X좌표와 Y좌표를 갖는 정수 격자점으로 표현된다. 가장 왼쪽 위의 점이 (1,4)이며, 가장 오른쪽 아래의 점이 (3,1)이 된다.
위의 패턴을 좌표로 읽으면 (3,4) (2,4) (1,2) (2,1) (2,2) (3,2) (3,1) (1,3) 이 된다.
이제 '유효한 패턴' 을 다음과 같이 정의하자.
어느 날 청호는 자기 휴대폰의 잠금 패턴을 잊어버렸다. 하지만 청호는 패턴의 길이 L과 패턴이 절대 지나지 않았던 점들의 집합 S를 기억한다. S에 포함되지 않는 점들은 지날 수도 있고 지나지 않을 수도 있다.
청호는 알고 있는 정보를 바탕으로 모든 경우의 수를 하나하나 시도해보려 한다. 하지만 그 전에, 몇 번이나 시도해야할 지 미리 계산해보고 시도하고 싶다. S와 L이 주어질 때, 서로 다른 유효한 패턴의 개수는 총 몇 개일까?
첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )
각 테스트 케이스의 첫 줄엔 L과 N이 주어진다. L은 패턴의 길이이며, N은 청호가 기억하는 절대 지나지 않았던 점들의 수이다. ( 1 ≤ L ≤ 1000 ) , ( 0 ≤ N ≤ 12 )
이어 N줄에 걸쳐 두 정수 X와 Y가 주어진다. ( 1 ≤ X ≤ 3 ), ( 1 ≤ Y ≤ 4 )
이는 패턴이 점 (X,Y)를 절대 지나지 않음을 의미한다.
N개의 점은 모두 다르다.
각 테스트 케이스마다, 가능한 유효한 패턴의 총 개수를 출력한다.
만일 가능한 패턴이 한 개도 없다면 패턴의 개수 대신 BAD MEMORY를 출력한다.
3 1 0 2 10 1 1 1 2 1 3 2 1 2 2 2 3 2 4 3 2 3 3 3 4 1 3 1 4 2 4 3 4
34 BAD MEMORY 24
ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2012 Arab Collegiate Programming Contest F번