http://code.google.com/codejam/contest/dashboard?c=90101#s=p2
Problem
So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.
If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".
To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".
The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.
Input
The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.
Output
For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.
Limits
1 ≤ N ≤ 100Small dataset
Each line will be no longer than 30 characters.Large dataset
Each line will be no longer than 500 characters.Sample
Input | Output |
3 | Case #1: 0001 |
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class WelcomeJam {
private static final String str ="welcome to code jam";
static String[] letter = new String[str.length()];
public static void main(String[] args) throws IOException {
for (int i=0; i<str.length();i++){
letter[i]= str.substring(i,i+1);
}
BufferedReader r = new BufferedReader(new InputStreamReader(
WelcomeJam.class.getResourceAsStream("/in")));
String input = r.readLine();
int n = Integer.valueOf(input);
String[] inps = new String[n];
for (int i=0;i<n;i++){
inps[i]= r.readLine();
}
r.close();
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File("out"))));
for (int i=0;i<n;i++){
//System.out.println("String - "+i);
String curr = inps[i];
Map<String,TreeSet<Integer>> map = new HashMap<String,TreeSet<Integer>>();
for (String s: letter){
if (!map.containsKey(s)){
map.put(s , new TreeSet<Integer>());
}
}
for (int j=0;j<curr.length();j++){
String s = curr.substring(j,j+1);
if (map.containsKey(s)){
map.get(s).add(j);
}
}
long result =0;
Set<Integer> set = map.get(letter[0]);
for (Integer p:set){
//System.out.println("Level 0 - "+p);
result += calculate(0,p,map);
result = result%10000;
}
result = result%10000;
String out =null;
if (result>=1000){
out = String.valueOf(result);
} else if (result>=100){
out = "0"+result;
} else if (result>=10){
out = "00"+result;
} else if (result>=1){
out = "000"+result;
} else {
out ="0000";
}
w.write("Case #"+(i+1)+": "+out+"\n");
w.flush();
}
w.close();
}
private static long calculate(int level,Integer position, Map<String,TreeSet<Integer>> map){
long result=0;
if (level == letter.length-1){
//System.out.println("Encountered");
result += 1;//(map.get(letter[level]).tailSet(position).size());
} else {
Set<Integer> set = map.get(letter[level+1]).tailSet(position);
for (Integer p:set){
//System.out.println("Level "+(level+1)+" - "+p);
result = result+calculate(level+1,p,map);
}
}
return result%10000;
}
}
