4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: static const LL MODVAL = 1000000007;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class DNADeletion {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	int differentProteins(vector <string> DNASequence, vector <string> codonTable)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		string dna;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<DNASequence.size(); ++i) dna += DNASequence[i];
4fd800b3a8 2011-02-23        kinaba: 		int N = dna.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<string> cL, cR;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<codonTable.size(); ++i) {
4fd800b3a8 2011-02-23        kinaba: 			stringstream sin(codonTable[i]);
4fd800b3a8 2011-02-23        kinaba: 			string s, t; sin>>s>>t;
4fd800b3a8 2011-02-23        kinaba: 			cL.push_back(s);
4fd800b3a8 2011-02-23        kinaba: 			cR.push_back(t);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		int M = cL.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector<LL> dp(N+1); dp[0] = 1;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			// there's dp[i] ways to generate some aminoseq from dna[0...i]
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			vector<int> p(M);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 			set<string> done;
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i; j<dna.size(); ++j)
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				for(int k=0; k<M; ++k)
4fd800b3a8 2011-02-23        kinaba: 					if( p[k]<3 && dna[j]==cL[k][p[k]] ) {
4fd800b3a8 2011-02-23        kinaba: 						p[k]++;
4fd800b3a8 2011-02-23        kinaba: 						if( p[k]==3 && !done.count(cR[k]) ) {
4fd800b3a8 2011-02-23        kinaba: 							done.insert(cR[k]);
4fd800b3a8 2011-02-23        kinaba: 							dp[j+1] = (dp[j+1] + dp[i]) % MODVAL;
4fd800b3a8 2011-02-23        kinaba: 						}
4fd800b3a8 2011-02-23        kinaba: 					}
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL n = (accumulate(dp.begin(), dp.end(), 0LL) - 1) % MODVAL;
4fd800b3a8 2011-02-23        kinaba: 		return int(n);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	string DNASequence_[] = {"ACTG"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
4fd800b3a8 2011-02-23        kinaba: 	string codonTable_[] = {"ACT gua", "ACG cys", "ATG leu", "CTG thr"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
4fd800b3a8 2011-02-23        kinaba: 	int RetVal = 4;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	string DNASequence_[] = {"AAACCC"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
4fd800b3a8 2011-02-23        kinaba: 	string codonTable_[] = {"AAA thr", "CCC cys"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
4fd800b3a8 2011-02-23        kinaba: 	int RetVal = 3;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	string DNASequence_[] = {"AAATCCC"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
4fd800b3a8 2011-02-23        kinaba: 	string codonTable_[] = {"AAA gua","TCC dop","AAT dop","CCC gua"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
4fd800b3a8 2011-02-23        kinaba: 	int RetVal = 5;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	string DNASequence_[] = {"ATGCGCATTAACCTCCTACCATGGAAGGGACGTAACCCGGCAATTTGATC",
4fd800b3a8 2011-02-23        kinaba:  "CTGATGACGGCATAAGCTACCCCTAGAGGTAAAAATGCATACTGCGTGCT",
4fd800b3a8 2011-02-23        kinaba:  "ATGCAG"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
4fd800b3a8 2011-02-23        kinaba: 	string codonTable_[] = {"AAC RpjZt","AAT ZeiC","GCA ChZwh","TCC RpjZt","GAA I",
4fd800b3a8 2011-02-23        kinaba:  "TAG ZeiC","CTG dVK","GAG ZeiC","GTG I","AAG q","ATT dVK",
4fd800b3a8 2011-02-23        kinaba:  "AGA cJEjM","GGG KONUd","GTC ZRV","GGC ZeiC","TTA KONUd",
4fd800b3a8 2011-02-23        kinaba:  "GAC q","CCA q","GCC ZRV","GCG RpjZt","CCT ZRV","ATG dVK",
4fd800b3a8 2011-02-23        kinaba:  "ATC ChZwh","CTC cJEjM","CCC q","ATA dWjz","TTG DkEG",
4fd800b3a8 2011-02-23        kinaba:  "CAG q","CAA ZRV","ACT dVK","TCG dVK","ACC I","CGC dVK"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
4fd800b3a8 2011-02-23        kinaba: 	int RetVal = 455985264;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	string DNASequence_[] = {"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
4fd800b3a8 2011-02-23        kinaba: 	string codonTable_[] = {"AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
4fd800b3a8 2011-02-23        kinaba: 	int RetVal = 3;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
4fd800b3a8 2011-02-23        kinaba: