I'm going to try to provide an intuitive explanation of the logic I
used for Problem C, in the hope it may help some fellow programmers.
First the code, in old-fashioned C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc,char *argv[])
{
char *wstr="welcome to code jam";
FILE * pFile, *pOut;
char buffer [600];
int mults[19];
int numCases;
pFile = fopen ("c-large.in" , "r");
pOut= fopen("c-large.out","w");
if (pFile == NULL) perror ("Error opening file");
else
{
fscanf(pFile, "%d\n", &numCases);
for (int num=0;num<numCases;num++)
{
fgets(buffer, 600, pFile);
for (int i=0;i<19;i++) mults[i]=0;
fprintf(pOut,"Case #%d: ",num+1);
int len=strlen(buffer);
for (int i=0;i<len;i++){
for (int j=0;j<19;j++){
if (j==0) {
if (buffer[i]==wstr[j]) mults[j]++;
}else if (mults[j-1]>0){
if (buffer[i]==wstr[j])
mults[j]=(mults[j]+mults[j-1])%10000;
}
}
}
if (mults[18]<1000) fprintf(pOut,"0");
if (mults[18]<100) fprintf(pOut,"0");
if (mults[18]<10) fprintf(pOut,"0");
fprintf(pOut,"%d\n",mults[18]);
}
fclose (pFile);
}
return 0;
}
Explanation:
Let's call the string we are testing the "test string", and "welcome
to code jam" the "target string".
For each test case, the outer loop of this algorithm iterates over the
test string, which is stored in buffer[]. The inner loop iterates
over the target string, which is stored in wstr[].
As we go over the test string, we keep track of a number mults[j] for
each character in the target string.
This is defined as:
mults[j] = the number of ways to build the target string up to the jth
character, using the characters in the test string we have evaluated
so far
* to correlate to the code, "jth character" counts from 0
Intuitively, we can describe mults[j] as the number of ways to "get
to" the jth character in "welcome to code jam" that we have found so
far.
When j==0, each time we encounter a character match ("buffer[i]==wstr
[j]"), we increment mults[0] by 1, since we have 1 more potential
first character for our target string.
When j>0, each time we encounter a match, we increment mults[j] by
mults[j-1].
This is because there are mults[j-1] ways so far to form the target
string up (j-1)th character. Each of these ways, when combined with
the character in we are currently evaluating, gives us a new way to
form the target string up to the jth character.
We also mod(%) the calculations by 10000, since only the values less
than 10000 at each step affect the last 4 digits of our final result.
When we are done iterating over the entire test string, mults[18]
will, by definition, be the number of ways to build the entire target
string, using the characters in the entire test string.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
