| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1151
Shortest Subsequence
Time Limit: 1000ms
Memory Limit: 65536kb Description
Logicalmars has a friend who is very superstitious. He thinks randomly written sequence is not that "random", which he explains that you write them according to your sub-consciousness. He kept writing random numbers day and day and he thinks random numbers should have a limitation, let us say m, which means all numbers other than 1~m are noise that shouldn't be considered. Now, with a lot of random numbers in hand (n in total), he wants to recognize some subsequence, which should consist of numbers from 1 to m at least once each and could contain some noise. He wants the shortest one, so he turns to you for your help. Input
The input consists of several test cases. In each test case, first line contains m, n, as described above. Then comes a line with n integers. These numbers are indexed from 1 to n. A pair of m=0 and n=0 indicates the end the input. 1<=m<=5000, 0<=n<=10^6, using 32-bit integer is enough for numbers. Output
For each test case, output the minimum length of the subsequence containing every number from 1 to m, and the index of the rightmost number of the subsequence. If multiple solutions exist, output the leftmost solution.Output -1 if the subsequence doesn't exist. Sample Input
4 10 1 0 0 2 2 3 4 2 1 0 4 10 0 0 0 0 1 2 3 0 0 0 0 0 Sample Output
4 9 -1 Source
lm@USTC
|