เฉลย Google Code jam 2009 : Welcome to google code jam (Dynamic Programming)

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;

public class WelcomToGoogleCodeJam {
	public static void main(String[] args) {
		try {
			String welcom = "welcome to code jam";
			PrintWriter pw = new PrintWriter(new File("out-large.out"));
			Scanner sc = new Scanner(new File("C-large-practice.in"));

			int T = Integer.parseInt(sc.nextLine());
			for (int i = 1; i <= T; i++) {
				String s = sc.nextLine();
				BigInteger mem[] = new BigInteger[welcom.length()];
				for(int j=0;j< welcom.length();j++)
				{
					mem[j] = new BigInteger("0");
				}
				for (int j = 0; j < s.length(); j++) {
					char x = s.charAt(j);
					if (welcom.contains("" + x)) {
						if (x == welcom.charAt(0)) {
							mem[0] = mem[0] .add(BigInteger.ONE);
						} else {
							for (int k = 1; k < welcom.length(); k++) {
								if (x == welcom.charAt(k))
									mem[k] = mem[k].add( mem[k - 1]);
							}
						}
					}
				}
				String output ;
				output = String.format("%04d", mem[ welcom.length()-1].mod(new BigInteger( "10000")));
				System.out.println("Case #"+i+": "+output);
				pw.println("Case #"+i+": "+output);
			}
			pw.close();
		} catch (IOException ee) {
			ee.printStackTrace();
		}

	}
}

Comments

รับสอนเขียนโปรแกรมคอมพิวเตอร์ โทร 0853507540 - Page Generated in 0.2811 seconds | Site Views: 152