King's Phone

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 916 Accepted Submission(s): 261

Problem Description

In a military parade, the King sees lots of new things, including an Andriod Phone. He becomes interested in the pattern lock screen.

The pattern interface is a $3 \times 3$ square lattice, the three points in the first line are labeled as $1, 2, 3$, the three points in the second line are labeled as $4, 5, 6$, and the three points in the last line are labeled as $7, 8, 9$。The password itself is a sequence, representing the points in chronological sequence, but you should follow the following rules:

- The password contains at least four points.

- Once a point has been passed through. It can't be passed through again.

- The middle point on the path can't be skipped, unless it has been passed through($3427$ is valid, but $3724$ is invalid).

His password has a length for a positive integer $k (1\le k\le 9)$, the password sequence is $s_1,s_2...s_k(0\le s_{i} < INT\_MAX)$ , he wants to know whether the password is valid. Then the King throws the problem to you.

Input

The first line contains a number $T(0 < T \le 100000)$, the number of the testcases.

For each test case, there are only one line. the first first number $k$，represent the length of the password, then $k$ numbers, separated by a space, representing the password sequence $s_1,s_2...s_k$.

Output

Output exactly $T$ lines. For each test case, print `valid` if the password is valid, otherwise print `invalid`

Sample Input

4 1 3 6 2

4 6 2 1 3

4 8 1 6 7

Sample Output

invalid
valid
valid

hint:
For test case #1：The path $1\rightarrow 3$ skipped the middle point $2$, so it's invalid.

For test case #2：The path $1\rightarrow 3$ doesn't skipped the middle point $2$, because the point 2 has been through, so it's valid.

For test case #2：The path $8\rightarrow 1 \rightarrow 6 \rightarrow 7$ doesn't have any the middle point $2$, so it's valid.

Source

BestCoder Round #75

挂终测了继续掉分一回解 orzzzz 最近太忙

题意：给你一段序列问是否为合法的解锁序列（模拟手机手势解锁）

满足条件 1.至少4个数字数量为[4,9] 2.不能重复 3.不能跳跃 4.数字的范围为[1,9]

还有记得每次的初始化

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 #include<queue>

 #include<stack>

 #include<set>

 using namespace std;

 int t;

 int a[];

 int mp[][];

 map<int,int> mpp;

 int jishu=;

 void init()

 {

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

     mp[][]=;

 }

 int main()

 {

     scanf("%d",&t);

     init();

     for(int i=;i<=t;i++)

     {

          scanf("%d",&jishu);

          memset(a,,sizeof(a));

          int maxn=;

          int flag=;

          for(int j=;j<=jishu;j++)

             {

                 scanf("%d",&a[j]);

                 if(a[j]>maxn)

                     maxn=a[j];

                 if(a[j]<=)

                     flag=;

             }

         mpp.clear();

         if(jishu<||jishu>||maxn>||flag==)

             printf("invalid\n");

         else

         {   int re=;

             mpp[a[]]=;

             for(int j=;j<jishu;j++)

             {

                 if(mpp[a[j+]]==)

                {

                  if(mp[a[j]][a[j+]]==)

                     re++;

                 else

                 {

                     if(mpp[(a[j]+a[j+])/])

                         re++;

                 }

                }

                 mpp[a[j+]]=;

             }

             if(re==jishu-)

                 printf("valid\n");

             else

                 printf("invalid\n");

         }

     }

     return ;

 }

巴特西

HDU 5641

King's Phone

最新文章

热门文章