25877번 - Team Shirts/Jerseys 다국어

The Legendary Mathematician Travis and his friends are in a recreational (rec) league for competitive programming. Travis has n friends and his friends want to show a sense of unity for this competitive programming league, so they splurged on team shirts/jerseys each of which has an integer between 1 and 99 (inclusive) on the back. Each of Travis’s friends have already selected their own (not necessarily distinct) jersey number so we have a list of n integers. Travis now needs to choose his jersey number to complete a list of n+1 integers. Travis will also choose an integer between 1 and 99 (inclusive) and he does not have to pick a number different from what his friends have picked (i.e., he can choose to duplicate a jersey number).

Even though Travis can choose any jersey number, he wants to show why he is considered to be a legendary mathematician. Travis has a favorite positive integer and he wants to select his jersey number such that he would be able to pick a set of numbers from the list of n+1 integers, concatenate this set of numbers together, and reach his favorite integer without extra leading or trailing digits (since Travis wants his favorite integer and not some other integer, he is trying to do so without any extra trailing or leading digits).

Travis has the fortunate option to choose his jersey number last. Now he just needs to determine if he can select some number that guarantees he can form his favorite integer. For example, suppose Travis’s friends have selected the jersey numbers 3, 10, 9, and 86. Then, by selecting the number 75, Travis could form his favorite positive integer 8,675,310. Note that Travis didn’t need to use the jersey number 9.

Note that if Travis chooses to use a jersey number, he must use the number completely, i.e., he cannot use just some of the digits in the number. For example, if he decides to use 75 in the above example, he must use “75”; he cannot just use “7” or use just “5”. Note also that if he wants to use a particular jersey number multiple times, he must have multiple friends with that jersey number. For example, if he wants to use 75 multiple times, he must have multiple friends with the number 75 (he can, of course, pick 75 for himself as well to increase the number of occurrences of 75 in the list of n+1 numbers).

We now have to break the secret that Travis is very temperamental! He tends to gain and lose friends very easily (so much for that whole unity thing); he also changes his favorite integer more often than the lights change at a busy intersection. For these reasons, Travis needs your help to write a program to solve this problem for a general set of friends and favorite numbers.

Given a set of positive integers representing friends’ jersey numbers, and a favorite integer, determine if Travis can choose a jersey number (for himself) that can allow for the creation of his favorite integer via concatenation of zero or more friends’ numbers and potentially his number. Additionally, since this is a rec league, the list of friends may contain duplicate jersey numbers, and Travis can choose an already chosen number for his shirt.

The first line of input contains exactly one positive integer, t (t < 1,000,000,000), representing Travis’s favorite integer. The second line of input contains exactly one positive integer, n (n ≤ 25), representing how many friends Travis has today. The next input line contains n space separated integers which denote the jersey number chosen by each of Travis’s friends. The jersey numbers will be between 1 and 99 (inclusive) and will have no leading zeroes, e.g., the input would have jersey number 7 but not 07.

If Travis is capable of reaching his favorite integer with (or without) his set of friends, print 1 (one); otherwise output 0 (zero).