2012 Canadian Computing Competition, Stage 2

Day 1, Problem 1: Choose Your Own Arithmetic

In Waterloo, you probably have seen some geese. How can you see geese with your calculator? Start with 6, add 7, multiply by 6, multiply by 8, add 7, multiply by 8, and multiply by 7, giving 35336. Then if you flip your calculator upside down, it says gEESE:

You want to write a program to help automatically build tricks of this type. However, your calculator has a lot of broken buttons: the only mathematical operators that work are + and ×, and only a few of the digits work. Your goal is to figure out whether your half-broken calculator can achieve a given target value, using single-digit inputs and a fixed number of operations.

Note: the calculator performs the operations as soon as they are entered, rather than following any rules for order of operations (see Sample Input 2).

Input Format

The first line of input is W, the exact number of operations you must use. W will be an integer between 0 and 6. The second line of input is 1 ≤ D ≤ 10, the number of working digit keys. On each of the D following lines, a working digit is given; these values are distinct integers from 0 to 9. Finally, an integer 1 ≤ V ≤ 5 is given, the number of target values; on each of the following Vlines there is an integer between 0 and 5000000 (inclusive) giving a target value which you'd like to achieve on your calculator.

Output Format

The output consists of V lines corresponding to the target values; each line contains "Y" if that target value can be achieved, and "N" if it cannot be achieved, using exactly W operations with the D given digits.

Precisely, a target value T can be achieved if, starting with one of the D digits, and then by adding or multiplying exactly W times by one of the digits, you end up with T. Digits can be re-used, and you do not need to use all of the digits. You cannot enter multi-digit numbers.

Sample Input 1

6
3
6
7
8
1
35336

Sample Output 1

Y

Sample Input 2

3
2
4
9
2
97
88

Sample Output 2

N
Y

Explanation

First line: we cannot achieve 97 using the rules of this calculator, so the output is N (even despite that 4 × 4 + 9 × 9 = 97, when the typical order of operations rules are taken into account). Second line: start with 9, add 9, add 4, and multiply by 4; this gives 88.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 64M
Added: Jun 20, 2012

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)