Let's define a periodic infinite sequence S (0-indexed) with period K using the formula Si=(i%K)+1.

Chef has found a sequence of positive integers A with length N buried underground. He suspects that it is a contiguous subsequence of some periodic sequence. Unfortunately, some elements of A are unreadable. Can you tell Chef the longest possible period K of an infinite periodic sequence which contains A (after suitably filling in the unreadable elements) as a contiguous subsequence?

Example Input

3

3

-1 -1 -1

5

1 -1 -1 4 1

4

4 6 7 -1

Example Output

inf

4

impossible

Chef has found a sequence of positive integers A with length N buried underground. He suspects that it is a contiguous subsequence of some periodic sequence. Unfortunately, some elements of A are unreadable. Can you tell Chef the longest possible period K of an infinite periodic sequence which contains A (after suitably filling in the unreadable elements) as a contiguous subsequence?

Example Input

3

3

-1 -1 -1

5

1 -1 -1 4 1

4

4 6 7 -1

Example Output

inf

4

impossible

Here's the link to the challenge

https://www.codechef.com/SNCK1A19/problems/PERIODIC/

https://www.codechef.com/SNCK1A19/problems/PERIODIC/

i can tell the logic for periodic problem if anyone can give me logic for 100 points chefadd problem

For the first problem, Chef can't read any of the numbers. They could be any numbers for a sequence of any length, so the answer is inf(infinite).

For the second one, notice the transition from 4 to 1. This can only happen at the end of a sequence, and in this case, it tells you that K mus be 4 if the sequence is valid. The other unknowns will work when k==4 so the answer is 4.

The third one can't be a valid sequence because "4 6" can never appear in a valid sequence. If S_{i} is X then S_{i+1} must be X+1 or 1.

For the second one, notice the transition from 4 to 1. This can only happen at the end of a sequence, and in this case, it tells you that K mus be 4 if the sequence is valid. The other unknowns will work when k==4 so the answer is 4.

The third one can't be a valid sequence because "4 6" can never appear in a valid sequence. If S

Topic archived. No new replies allowed.