1. Mother's Milk
This is my solution to the USACO training problem "milk3":
1 import java.io.*; 2 import java.util.*; 3 4 public class milk3 { 5 public static BufferedReader input; 6 public static PrintWriter output; 7 public static boolean [] list; 8 public static int [] size; 9 10 private static void pour(int i,int j,int [] prev,boolean [][] vis) { 11 int [] state = {prev[0],prev[1],size[2]-prev[0]-prev[1]}; 12 int delt = (state[i]<size[j]-state[j])? 13 state[i]:size[j]-state[j]; 14 state[i] -= delt; 15 state[j] += delt; 16 if (!vis[state[0]][state[1]]) { 17 vis[state[0]][state[1]] = true; 18 dfs(state,vis); 19 vis[state[0]][state[1]] = false; 20 } else if (state[0]==0) { 21 list[state[2]] = true; 22 } 23 24 } 25 private static void dfs(int [] state,boolean [][] visit) { 26 pour(0,1,state,visit); 27 pour(0,2,state,visit); 28 pour(1,0,state,visit); 29 pour(1,2,state,visit); 30 pour(2,0,state,visit); 31 pour(2,1,state,visit); 32 } 33 public static void main(String[] args) throws IOException { 34 input = new BufferedReader(new FileReader("milk3.in")); 35 StringTokenizer str = new StringTokenizer(input.readLine()); 36 size = new int[3]; 37 size[0] = Integer.parseInt(str.nextToken()); 38 size[1] = Integer.parseInt(str.nextToken()); 39 size[2] = Integer.parseInt(str.nextToken()); 40 input.close(); 41 list = new boolean [size[2]+1]; 42 boolean [][] visit = new boolean[size[2]+1][size[2]+1]; 43 dfs(new int[2],visit); 44 output = new PrintWriter(new FileWriter("milk3.out")); 45 for (int i=0;i<size[2];i++) { 46 if (list[i]) { 47 output.print(i+" "); 48 } 49 } 50 output.println(size[2]); 51 output.close(); 52 } 53 }
2. Wormholes
This is my solution to the USACO training problem "wormhole":
1 import java.util.*; 2 import java.io.*; 3 4 public class wormhole { 5 public static class Point { 6 public int x,y; 7 } 8 9 public static Scanner in; 10 public static PrintWriter out; 11 public static int num; 12 public static Point[] hole; 13 public static int[] next; 14 15 private static int test(int[] pair) { 16 // Test whether Bessie will get stuck in a cycle 17 boolean[] vis = new boolean[num]; 18 for (int i=0;i<num;i++) { 19 if (!vis[i]) { 20 int j = i; 21 while (j>=0) { 22 vis[j] = true; 23 j = next[pair[j]]; 24 if (i==j) { 25 return 1; 26 } 27 } 28 } 29 } 30 return 0; 31 } 32 private static int dfs(int[] pair,int depth) { 33 // Enumeration of Wormhole-Pair Matching 34 if (depth==num) { 35 return test(pair); 36 } else if (pair[depth]>=0) { 37 return dfs(pair,depth+1); 38 } else { 39 int val = 0; 40 for (int i=depth+1;i<num;i++) { 41 if (pair[i]>=0) { 42 continue; 43 } 44 pair[depth] = i; 45 pair[i] = depth; 46 val += dfs(pair,depth+1); 47 pair[i] = -1; 48 } 49 pair[depth] = -1; 50 return val; 51 } 52 } 53 private static void setNext() { 54 next = new int[num]; 55 for (int i=0;i<num;i++) { 56 next[i] = -1; 57 } 58 for (int i=0;i<num;i++) { 59 for (int j=0;j<num;j++) { 60 // next[i]==j means Bessie will falls into hole[j] 61 // after she departs from hole[i] 62 if (hole[i].y!=hole[j].y || hole[j].x<=hole[i].x) { 63 continue; 64 } else if (next[i]<0 || hole[next[i]].x>hole[j].x) { 65 next[i] = j; 66 } 67 } 68 } 69 } 70 private static void solve() { 71 int val = 0; 72 int[] pair = new int[num]; 73 for (int i=0;i<num;i++) { 74 pair[i] = -1; 75 } 76 val += dfs(pair,0); 77 out.println(val); 78 } 79 public static void init() { 80 num = in.nextInt(); 81 hole = new Point[num]; 82 for (int i=0;i<num;i++) { 83 hole[i] = new Point(); 84 hole[i].x = in.nextInt(); 85 hole[i].y = in.nextInt(); 86 } 87 setNext(); 88 } 89 public static void main(String[] args) throws IOException { 90 in = new Scanner(new FileReader("wormhole.in")); 91 init(); 92 in.close(); 93 out = new PrintWriter(new FileWriter("wormhole.out")); 94 solve(); 95 out.close(); 96 } 97 }
3. Zero Sum
This is my solution to the USACO training problem "zerosum":
1 import java.util.*; 2 import java.io.*; 3 4 public class zerosum { 5 public static Scanner in; 6 public static PrintWriter out; 7 8 private static boolean test(char[] op,int n) { 9 int val = 0, tmp = 1; 10 boolean minus = false; 11 for (int i=1;i<n;i++) { 12 if (op[i]==' ') { 13 tmp = tmp*10+(i+1); 14 } else if (op[i]=='+') { 15 if (!minus) { 16 val+=tmp; 17 } else { 18 val-=tmp; 19 } 20 tmp = i+1; 21 minus = false; 22 } else { 23 if (!minus) { 24 val+=tmp; 25 } else { 26 val-=tmp; 27 } 28 tmp = i+1; 29 minus = true; 30 } 31 } 32 if (!minus) { 33 return val==-tmp; 34 } else { 35 return val==tmp; 36 } 37 } 38 private static void print(char[] op,int n) { 39 out.print(1); 40 for (int i=1;i<n;i++) { 41 out.print(op[i]+""+(i+1)); 42 } 43 out.println(); 44 } 45 private static void dfs(char[] op,int k,int n) { 46 if (k==n) { 47 if (test(op,n)) { 48 print(op,n); 49 } 50 return; 51 } 52 op[k] = ' '; 53 dfs(op,k+1,n); 54 op[k] = '+'; 55 dfs(op,k+1,n); 56 op[k] = '-'; 57 dfs(op,k+1,n); 58 } 59 public static void main(String[] args) throws IOException { 60 in = new Scanner(new FileReader("zerosum.in")); 61 int n = in.nextInt(); 62 in.close(); 63 out = new PrintWriter(new FileWriter("zerosum.out")); 64 dfs(new char[n],1,n); 65 out.close(); 66 } 67 }