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 <[email protected]> wrote:
> I am curious how to see the solutions, especially for problem C. I use
> C++.
>
> On Sep 3, 9:50 pm, Dhruva Sagar <[email protected]> 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 <
>
> > [email protected]> 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
> > > <[email protected]>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 <[email protected]> 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 [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
