TopCoder SRM 455 div2

500

deque<int> insert( deque<int> v, int n, int size ){
  int a=0;
  for(int i=v.size()-1 ; i>= max(0, (int)v.size()-size) ; i--){
    a += v[i];
  }

  a %= 10;

  v.push_back(a);

  if( v.size()> n ){
    v.pop_front();
  }
  return v;

}

class EasySequence {
public:
  int find(vector <int> A, vector <int> B) {
    
    if(A.size() > B.size()){
      for(int i=0 ; i<=A.size()-B.size() ; i++){
	vector<int> v;

	for(int j=i ; j<i+B.size() ; j++){
	  v.push_back(A[j]);
	}
	
	if(v==B) return i;
	
      }
    }
    
    if(A == B)return 0;
    
    int An = A.size();
    int Bn = B.size();
    
    deque<int> AA, BB;
   
    for(int i=0 ; i<A.size() ; i++)
      AA.push_back(A[i]);
    	  

    for(int i=0 ; i<B.size() ; i++)
      BB.push_back(B[i]);
    
    
    while( AA.size() < BB.size())
      AA = insert(AA, Bn, An);
    
    
    if( AA == BB) return 0;
    
    clock_t start, end;
    start = clock();
    int cnt = AA.size()-BB.size();
    while(1){
      
      AA = insert( AA,Bn,An );
      cnt++;
      if( AA.size() == BB.size()){
	if( AA==BB ) return cnt;
      }
      else{
	deque<int> AAA;
	for(int i=AA.size()-BB.size() ; i<AA.size() ; i++){
	  AAA.push_back( AA[i] );
	}      
	if( AAA==BB) return cnt;
      }

      // 1.9秒超えたら終わり
      end = clock();
      if( (end-start)/CLOCKS_PER_SEC > 1.9) return -1;
    }

  }
};