TopCoder problem "EasySequence" used in Member SRM 455 (Division II Level Two)



Problem Statement

    Petya likes sequences. He has an infinite sequence A[] with the following properties:

  • A[0], A[1], ..., A[N-1] are given;
  • A[i]=(A[i-1]+A[i-2]+...+A[i-N])%10 for all i>=N;
Sequence B[] with length M is a substring of A[] if there is such index P that B[0]=A[P], B[1]=A[P+1], ..., B[M-1]=A[P+M-1]. Your task is to find the smallest possible such P. If there is no such index, return -1.
 

Definition

    
Class:EasySequence
Method:find
Parameters:int[], int[]
Returns:int
Method signature:int find(int[] A, int[] B)
(be sure your method is public)
    
 

Constraints

-A will contain between 1 and 7 elements, inclusive.
-B will contain between 1 and 50 elements, inclusive.
-Each element of A will be between 0 and 9, inclusive.
-Each element of B will be between 0 and 9, inclusive.
 

Examples

0)
    
{1,2,3}
{0,7,8,5}
Returns: 5
Starting with 1,2,3 we have:
1+2+3 =  6,  6 % 10 = 6
2+3+6 = 11, 11 % 10 = 1
3+6+1 = 10, 10 % 10 = 0
6+1+0 =  7,  7 % 10 = 7
1+0+7 =  8,  8 % 10 = 8
0+7+8 = 15, 15 % 10 = 5
7+8+5 = 20, 20 % 10 = 0

1,2,3,6,1,0,7,8,5,0
          0,7,8,5      answer = 5
1)
    
{1,2,8}
{7,4,2,3}
Returns: -1
2)
    
{1,2,3,4,5}
{4,5}
Returns: 3
3)
    
{1}
{1,1,1}
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10716

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14179&pm=10716

Writer:

Seyaua

Testers:

Rustyoldman , timmac , StevieT , maksay , K.A.D.R , Seyaua

Problem categories:

Search