BC #49 1001 Untitled

Untitled

 

 Accepts: 504

 

 Submissions: 1542

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 65536/65536 K (Java/Others)

Problem Description

There is an integer aa and nn integers b_1, ldots, b_nb​1​​,…,b​n​​. After selecting some numbers from b_1, ldots, b_nb​1​​,…,b​n​​ in any order, say c_1, ldots, c_rc​1​​,…,c​r​​, we want to make sure that a mod c_1 mod c_2 mod ldots mod c_r = 0a mod c​1​​ mod c​2​​ mod… mod c​r​​=0 (i.e., aa will become the remainder divided by c_ic​i​​ each time, and at the end, we want aa to become 00). Please determine the minimum value of rr. If the goal cannot be achieved, print -1−1 instead.

Input

The first line contains one integer T leq 5T≤5, which represents the number of testcases.

For each testcase, there are two lines:

1. The first line contains two integers nn and aa (1 leq n leq 20, 1 leq a leq 10^61≤n≤20,1≤a≤10​6​​).

2. The second line contains nn integers b_1, ldots, b_nb​1​​,…,b​n​​ (forall 1leq i leq n, 1 leq b_i leq 10^6∀1≤i≤n,1≤b​i​​≤10​6​​).

Output

Print TT answers in TT lines.

Sample Input

2
2 9
2 7
2 9
6 7

Sample Output

2
-1

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s[20005];
int x[20005],y[20005],n,m;

int judge(int a,int b)
{
    int flg=1;
    while(a<b)
    {
        if(s[a]!=s[b])
        {
            flg=0;
            break;
        }
        a++,b--;
    }
    return flg;
}

int main()
{
    int T;
    int i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        int l=strlen(s);
        int oo=1;
        for(i=1;i<l;i++)
        {
            if(s[i]!=s[i-1])
            {
                oo=0;
                break;
            }
        }
        if(oo==1)
            printf("Yes
");
        else
        {
        n=0,m=0;
        x[0]=0,y[0]=l-1;
        for(i=1;i<=l-3;i++)
        {
            if(judge(0,i)==1)
            {
                n++;
                x[n]=i;
            }
        }
        for(i=l-2;i>=2;i--)
        {
            if(judge(i,l-1)==1)
            {
                m++;
                y[m]=i;
            }
        }
        int ans=0;
        for(i=0;i<=n;i++)
        {
            if(ans==1)
                break;
            for(j=0;j<=m;j++)
            {
                if(y[j]-x[i]<=1)
                    break;
                if(judge(x[i]+1,y[j]-1)==1)
                {
                    ans=1;
                    break;
                }
            }
        }

        if(ans==1)
            printf("Yes
");
        else
            printf("No
");
        }
    }
    return 0;
}