Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: dhruv411
- LANG: JAVA
- TASK: holstein
- */
- import java.util.*;
- import java.io.*;
- public class holstein {
- static int vitamins;
- static BufferedReader br;
- public static void main(String[] args) throws IOException {
- br = new BufferedReader(new FileReader("holstein.in"));
- StringTokenizer st = new StringTokenizer(br.readLine());
- PrintWriter pw = new PrintWriter(new FileWriter("holstein.out"));
- ArrayList<ArrayList<Integer>> tot = new ArrayList<ArrayList<Integer>>();
- vitamins = Integer.parseInt(st.nextToken());
- Feed[] brans = new Feed[30];
- brans[0] = new Feed(0, st);
- st = new StringTokenizer(br.readLine());
- int g = Integer.parseInt(st.nextToken());
- for(int x = 1; x<=g; x++){
- brans[x] = new Feed(x,st);
- }
- for(int x = 1; x<=g; x++){
- for(ArrayList<Integer> k : combine(g,x))
- tot.add(k);
- }
- ArrayList<ArrayList<Integer>> sols = new ArrayList<ArrayList<Integer>>();
- for(ArrayList<Integer> k : tot){
- ArrayList<Integer> tempv = new ArrayList<Integer>();
- for(int x : brans[0].vits){
- tempv.add(x);
- }
- for(int l : k){
- for(int j = 0; j<brans[0].vits.size(); j++){
- tempv.set(j, tempv.get(j) - brans[l].vits.get(j));
- }
- }
- boolean isSol = true;
- for(int l : tempv){
- if(l > 0)
- isSol = false;
- }
- if(isSol){
- sols.add(k);
- }
- }
- Collections.sort(sols, new Comparator<ArrayList<Integer>>() {
- @Override
- public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
- if(o1.size() > o2.size())
- return 1;
- if(o1.size() < o2.size())
- return -1;
- if(o1.get(0) > o2.get(0))
- return 1;
- if(o1.get(0) < o2.get(0))
- return -1;
- return 0;
- }
- });
- pw.print(sols.get(0).size() + " ");
- int k;
- for(k = 0; k<sols.get(0).size()-1; k++)
- pw.print(sols.get(0).get(k) + " ");
- pw.println(sols.get(0).get(k));
- pw.close();
- }
- static class Feed{
- List<Integer> vits;
- int name;
- public Feed(int n, StringTokenizer st) throws IOException{
- name = n;
- vits = new ArrayList<Integer>();
- st = new StringTokenizer(br.readLine());
- for(int x = 0; x<vitamins; x++){
- vits.add(Integer.parseInt(st.nextToken()));
- }
- }
- }
- public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
- ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
- if (n <= 0 || n < k)
- return result;
- ArrayList<Integer> item = new ArrayList<Integer>();
- dfs(n, k, 1, item, result); // because it need to begin from 1
- return result;
- }
- private static void dfs(int n, int k, int start, ArrayList<Integer> item,
- ArrayList<ArrayList<Integer>> res) {
- if (item.size() == k) {
- res.add(new ArrayList<Integer>(item));
- return;
- }
- for (int i = start; i <= n; i++) {
- item.add(i);
- dfs(n, k, i + 1, item, res);
- item.remove(item.size() - 1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement