I solved C in C++ using dynamic programming. The idea is to loop through the input string once for each character is "welcome to code jam". If the current character in S is the first "e" (i==1), and the current character of the input string is "e" (j) then the occurrences of "we" to this point is the previous number of occurrences of "we" (dp[i][j-1]) plus the number of occurrences of "we" using the current "e" (dp[i-1][j-1]). If the letter of the input string does not match then the number of occurrences of "we" is dp[i] [j-1].
I later rewrote it to a recursive memoized solution, but here it is... If you have any questions don't hesitate to ask. #include <cstdio> #include <string> #include <fstream> #include <sstream> using namespace std; #define MOD 10000 ifstream fin; ofstream fout; string inp,S = "welcome to code jam"; int dp[20][500]; string getResult(int n) { stringstream ss; ss << n; string s = ss.str(); while(s.size() < 4) s = "0" + s; return s; } int main() { int N,i,j; fin.open("c.in"); fout.open("c.out"); fin >> N; getline(fin, inp); for(int t = 1; t <= N; t++) { getline(fin,inp); fout << "Case #" << t << ": "; if(inp.size() == 0) { fout << "0000" << endl; continue; } for(i = 0; i < S.size(); i++) dp[0][i] = 0; if(inp[0] == S[0]) dp[0][0] = 1; for(i = 1; i < inp.size(); i++) if(S[0] == inp[i]) dp[0][i] = dp[0][i-1] + 1; else dp[0][i] = dp[0][i-1]; for(i = 1; i < S.size(); i++) for(j = 1; j < inp.size(); j++) if(S[i] == inp[j]) dp[i][j] = (dp[i-1][j-1] + dp[i][j-1])%MOD; else dp[i][j] = dp[i][j-1]; fout << getResult(dp[S.size()-1][inp.size()-1]) << endl; } fout.close(); fin.close(); return 0; } On Sep 3, 6:53 pm, MagicLi <musicl...@gmail.com> wrote: > I am curious how to see the solutions, especially for problem C. I use > C++. > > On Sep 3, 9:50 pm, Dhruva Sagar <dhruva.sa...@gmail.com> wrote: > > > > > Yes I did exactly the same. > > I did in ruby. And yes I found that we can download the solutions :) > > > Thanks & Regards, > > Dhruva Sagar. > > > Jonathan > > Swift<http://www.brainyquote.com/quotes/authors/j/jonathan_swift.html> > > - "May you live every day of your life." > > > On Fri, Sep 4, 2009 at 7:16 AM, Pedro Henrique Calais < > > > pedro.cal...@gmail.com> wrote: > > > Yes, they are available on the web site. > > > > My solution for problem A was just to convert the words to regexs: > > > > (ab)c(cd) --> [ab]c[cd] > > > > and then tested the regex against all the vocabulary of the language. > > > > -- Pedro > > > > On Thu, Sep 3, 2009 at 10:44 PM, Dhruva Sagar > > > <dhruva.sa...@gmail.com>wrote: > > > >> I finished only problem A for both small & large :(. > > >> Came close to finishing B, but time ran out. > > > >> Is it possible to see others' solutions ? I would love to. > > > >> Thanks & Regards, > > >> Dhruva Sagar. > > > >> Pablo > > >> Picasso<http://www.brainyquote.com/quotes/authors/p/pablo_picasso.html> > > >> - "Computers are useless. They can only give you answers." > > > >> On Fri, Sep 4, 2009 at 6:55 AM, MagicLi <musicl...@gmail.com> wrote: > > > >>> I finish problem A&B, for problem C, I finish the small input, my > > >>> program fail the large input. I think there is better algorithm to > > >>> work it out.- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to google-code@googlegroups.com To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---