Created
January 15, 2015 01:15
-
-
Save st0le/6f5827bda2c373d74837 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.File; | |
import java.io.PrintStream; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Scanner; | |
import java.util.concurrent.Callable; | |
import java.util.concurrent.ExecutorService; | |
import java.util.concurrent.Executors; | |
import java.util.concurrent.Future; | |
public class Solution implements Callable<String> { | |
private int ga, gb, gc; | |
private int[][] wt; | |
public Solution(int[] g, int[][] wt) { | |
this.wt = wt; | |
this.ga = g[0]; | |
this.gb = g[1]; | |
this.gc = g[2]; | |
} | |
public static void main(String[] args) throws Exception { | |
System.setOut(new PrintStream(new File( | |
"C:\\Users\\gaurav\\Desktop\\out.txt"))); | |
Scanner scan = new Scanner(new File( | |
"C:\\Users\\gaurav\\Desktop\\in.txt")); | |
List<Future<String>> threads = new ArrayList<Future<String>>(); | |
ExecutorService pool = Executors.newFixedThreadPool(4); | |
int T = Integer.parseInt(scan.nextLine()); | |
for (int t = 1; t <= T; t++) { | |
int[] g = new int[3]; | |
for (int j = 0; j < 3; j++) | |
g[j] = scan.nextInt(); | |
int n = scan.nextInt(); | |
int[][] wt = new int[n][3]; | |
for (int i = 0; i < n; i++) { | |
for (int j = 0; j < 3; j++) | |
wt[i][j] = scan.nextInt(); | |
} | |
threads.add(pool.submit(new Solution(g, wt))); | |
} | |
for (int t = 1; t <= T; t++) { | |
System.out.println(String.format("Case #%d: %s", t, | |
threads.get(t - 1).get())); | |
} | |
pool.shutdown(); | |
} | |
private boolean subset(int ga, int gb, int gc, int[][] wt, int n, int i) { | |
if (ga == 0 && gb == 0 && gc == 0) | |
return true; | |
if (i == n || ga < 0 || gb < 0 || gc < 0) | |
return false; | |
return subset(ga - wt[i][0], gb - wt[i][1], gc - wt[i][2], wt, n, i + 1) | |
|| subset(ga, gb, gc, wt, n, i + 1); | |
} | |
@Override | |
public String call() throws Exception { | |
return subset(ga, gb, gc, wt, wt.length, 0) ? "yes" : "no"; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment