Connection Status:
Competition Arena > EasySequence

EasySequence

Member SRM 455 · 2009-12-03 · by Seyaua

Member SRM 455 · 2009-12-03 · by Seyaua · Search
Class Name: EasySequence
Return Type: int
Method Name: find
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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)
{9,9,9,9,9,9,9}
{1,3,1,1,9,1,9,5,9,5,9,7,5,9}
Returns: 147
4)
{9,9,9,9,9,9,9}
{5,9,9,9,9,9,9,9,3,7,5,1,3,7,5,1,9,1,7,3,3,9,3,5,1,1,5,7,1,3,3,1,1,1,7,7,3,3,3,5,9,7,7,7,1,9,5,
5,1,5}
Returns: 9371

Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EasySequence with a public method int find(vector<int> A, vector<int> B) · 133 test cases · 2 s / 256 MB per case

Submitting as anonymous