시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 64 MB (%)
문제
워털루에서, 당신은 오리(geese)를 보았을것이다. 오리(geese)를 당신의 계산기에서 어떻게 볼까? 6으로 시작해서, 7을 더하고 6을 곱하고 8을 곱하고 7을 더하고 8을 곱하고 7을 곱하면, 35336을 얻을 수 있다. 35336을 상하로 뒤집어보면, gEESE가 보인다. ![figure1](/download_file/fe601ac99db4940e536a0eca60650ec7e352d8e91a048c7ecf2b8c74ef53e268/1.png/?show=true) 당신은 이러한 타입의 트릭을 자동으로 만들어주는 프로그램을 만들고 싶다. 하지만, 당신의 계산기는 많은 버튼이 고장났다: 수학 연산자는 +와 *만 작동하고, 몇몇의 적은 한자리 번호만 작동한다. 당신의 목적은 이렇게 반 고장난 계산기를 이용해 목적 숫자를 만드는 것인데, 한자리 숫자와 정해진 갯수의 연산자만을 사용해서이다. Note: 계산기의 연산자는 입력하는 순간 계산되며, 연산자 순서 규칙보다 우선적용된다. (예제 2번을 보라)
입력
첫 줄에는 W, 정확히 사용해야 하는 연산자 횟수가 주어진다. W는 0과 6 사이의 정수이다. 두번째 줄에는 1<=D<=10, 누를 수 있는 한자리 숫자 버튼의 갯수가 주어진다. D개의 줄에 작동하는 숫자 버튼이 무엇인지 주어진다: 이 값은 0과 9사이의 서로다른 숫자들이다. 마지막으로 정수 1<=V<=5가 주어지는데, 이것은 목적 숫자의 갯수이다. 이어지는 V개의 줄에 0에서 5000000사이의 (포함하는) 당신의 계산기를 통해 도달하고자 하는 목적값이 주어진다.
출력
출력은 각각의 목적값과 대응되는 V개의 줄로 표현된다: 각줄이 "Y"를 포함하면 정확히 W번의 연산을 주어진 D개의 한자리 숫자 버튼만을 이용해서 목적값에 도달이 가능하다는 뜻이고, "N"은 불가능할 경우이다. 정확히 말해, 목적값 T가 도달가능하다는 뜻은, 처음에 D개의 숫자중에 하나로 시작해서 W번 숫자를 더하거나 곱해서 최종적으로 T로 끝나는 것이다. 숫자는 재사용 가능하고, 모든 숫자를 사용할 필요는 없다. 당신은 여러자릿수의 숫자를 입력할 수는 없다.
힌트
예제입력1 ``` 6 3 6 7 8 1 35336 ``` 예제출력1 ``` Y ``` 예제입력2 ``` 3 2 4 9 2 97 88 ``` 예제출력2 ``` N Y ``` 예제설명 첫줄 : 우리는 위의 규칙을 적용해 97을 만들 수 없다. 그러므로 N을 출력한다. (4*4+9*9=97이지만, 입력하는 즉시 계산이 되므로 불가능하다.) 두번째줄 : 9로 시작해서 9를 더하고 5를 더하고 5를 곱하면; 주어진 88이 만들어진다.