Rezultati

Up. imeNalogaJezikRezultatČas oddaje
vlakectomaz-2017 Pasavci C++ 100/100OK 11. maj '17 @ 20:08

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,215 MiB 0,004 s OK
#2 5/5 3,180 MiB 0,004 s OK
#3 5/5 3,219 MiB 0,004 s OK
#4 5/5 3,195 MiB 0,004 s OK
#5 5/5 3,219 MiB 0,004 s OK
#6 5/5 3,219 MiB 0,004 s OK
#7 5/5 3,219 MiB 0,004 s OK
#8 5/5 3,219 MiB 0,004 s OK
#9 6/6 3,195 MiB 0,004 s OK
#10 6/6 5,125 MiB 0,174 s OK
#11 6/6 3,207 MiB 0,004 s OK
#12 6/6 3,215 MiB 0,004 s OK
#13 6/6 3,191 MiB 0,004 s OK
#14 6/6 3,191 MiB 0,004 s OK
#15 6/6 3,191 MiB 0,004 s OK
#16 6/6 3,191 MiB 0,004 s OK
#17 6/6 3,215 MiB 0,004 s OK
#18 6/6 5,117 MiB 0,186 s OK

Ocenjevani program (pasavci.cpp):
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

struct pasavec {
	string left;
	string right;
	long long pojavitev;
};

int m;
int lenP;
string p;
pasavec s[1003];

long long count(string str){
	int i=0;
	long long c=0;
	while(true){
		int pos = str.find(p,i);
		if(pos==string::npos)
			break;
		c++;
		i=pos+1;
	}

	return c;
}

string getLeft(string s1){
	return s1.substr(0,min(lenP, (int)s1.size()));
}

string getRight(string s1){
	return s1.substr(max(0,(int)s1.size()-lenP),min(lenP, (int)s1.size()));
}



int main(){
	string s1;
	string s2;
	
	cin >> p >> s1 >> s2;

	lenP = p.size()-1;
	s[1].pojavitev = count(s1);
	s[1].left = getLeft(s1);
	s[1].right = getRight(s1);
	s[2].pojavitev = count(s2);
	s[2].left = getLeft(s2);
	s[2].right = getRight(s2);

	cin >> m;
	
	for(int i=3;i<m+3;i++){
		int a,b;
		cin >> a >> b;
		
		pasavec *prvi = &s[a];
		pasavec *drugi = &s[b];
		s[i].pojavitev = prvi->pojavitev + drugi->pojavitev;
		string sredina = prvi->right + drugi->left;
		s[i].pojavitev += count(sredina);
		s[i].pojavitev %= 1000000007;

		if(prvi->left.size()<lenP){
			s[i].left = getLeft(sredina);
		} else {
			s[i].left = prvi->left;
		}
		if(drugi->right.size()<lenP){
			s[i].right = getRight(sredina);
		} else {
			s[i].right = drugi->right;
		}
	}

	cout<<s[m+2].pojavitev<<endl;
	
	return 0;
}