KIMO1 - abdou set

no tags 

abdou has a set of unique positive integers . he wants to add several (possibly none) new positive integers to this set, such that when the set is sorted for every two consecutive numbers X , Y we have abs(X%m-Y%m) = 1 . your task is to calculate the smallest possible count of new numbers, with which he can achieve that. 
                                                                                Input
 
The first line contains T, the number of test cases. It is followed by 2*T each test case consist of two lines the first line contain two numbers m , N .. the second line contain N integer .
1 <=T <= 5000 .
1 <= m <= 10^5 
2 <= N <=50.
1 <= every integer in the set <= 10^6
                                                                              Output
 
 For each line of input produce one line of output. This line contains the smallest possible count of new numbers, with which he can complete the set  or -1 if no solution .
                                                                              Example
input
5
2 3 
2 10 20
10 2
10 20
10 6
11 19 5 30 40 100
1 2 
1  9999
15 3
4218 15210 1426
10 6 11 19 5 30 40 1007
output
2
1
-1
-1
3
expanation :
in first test case we can add 3 and 13 to the given set to  achieve abdou goal  .
you can see my time here 

 

Abdou has a set of unique positive integers. He wants to add several (possibly none) new positive integers to this set, such that when the set is sorted, for every two consecutive numbers X , Y abs(X%M-Y%M) = 1 . Your task is to calculate the smallest possible count of new numbers, with which he can achieve that. 

                                                                               Input

The first line contains T, the number of test cases. It is followed by 2*T lines, two lines per test case. The first line contains two positive integers M and N. The second line contains N integers.

1 <= T <= 5000 .

1 <= M <= 10^5 

2 <= N <=50.

1 <= every integer in the set <= 10^6

                                                                              Output

For test case print a single integer in a separate line: the smallest possible count of new numbers, with which he can complete the set or -1 if no solution exists.

                                                                              Example

Input:

5

2 3 

2 10 20

10 2

10 20

10 6

11 19 5 30 40 100

1 2 

1  9999

15 3

4218 15210 1426


Output:

2

1

-1

-1

3


Explanation:

In the first test case we can add 3 and 13 to the given set to achieve abdou goal.



hide comments
SWOOSH!!!: 2013-06-12 09:01:22

For the 3rd test case, shouldn't the solution be 11 12 13 14 15 16 17 18 19 8 7 6 5 4 3 2 1 30 41 40 101 100? Why is the output -1 then?
Also for 5th test case, the solution should be 4218 4217 4216 15210 1426. Please correct me if I am wrong.

(abdelkarim) please , read the problem statement correctly .

Last edit: 2013-06-12 20:25:35
Mitch Schwartz: 2013-06-10 00:50:17

A time limit of 0.029s makes AC in certain languages impossible because it is less than the interpreter startup time, e.g. on Cube a program that does nothing currently takes about 0.06s in Python 3 and 0.03s in Java. Please adjust the test data so that a more fair time limit such as 0.5s can be used.
--------------------
(abdelkarim)done, i changed the time limit i hope now this problem be solvable by other languages .

(Mitch) Thanks!

Last edit: 2013-06-07 21:58:16

Added by:abdelkarim
Date:2013-05-12
Time limit:0.5s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:owner