Advertisement
Guest User

Untitled

a guest
Jan 16th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.59 KB | None | 0 0
  1. /*
  2. ID: dhruv411
  3. LANG: JAVA
  4. TASK: holstein
  5. */
  6. import java.util.*;
  7. import java.io.*;
  8.  
  9. public class holstein {
  10. static int vitamins;
  11. static BufferedReader br;
  12. public static void main(String[] args) throws IOException {
  13. br = new BufferedReader(new FileReader("holstein.in"));
  14. StringTokenizer st = new StringTokenizer(br.readLine());
  15. PrintWriter pw = new PrintWriter(new FileWriter("holstein.out"));
  16. ArrayList<ArrayList<Integer>> tot = new ArrayList<ArrayList<Integer>>();
  17. vitamins = Integer.parseInt(st.nextToken());
  18. Feed[] brans = new Feed[30];
  19. brans[0] = new Feed(0, st);
  20. st = new StringTokenizer(br.readLine());
  21. int g = Integer.parseInt(st.nextToken());
  22. for(int x = 1; x<=g; x++){
  23. brans[x] = new Feed(x,st);
  24. }
  25.  
  26. for(int x = 1; x<=g; x++){
  27. for(ArrayList<Integer> k : combine(g,x))
  28. tot.add(k);
  29. }
  30.  
  31. ArrayList<ArrayList<Integer>> sols = new ArrayList<ArrayList<Integer>>();
  32.  
  33. for(ArrayList<Integer> k : tot){
  34. ArrayList<Integer> tempv = new ArrayList<Integer>();
  35. for(int x : brans[0].vits){
  36. tempv.add(x);
  37. }
  38.  
  39. for(int l : k){
  40. for(int j = 0; j<brans[0].vits.size(); j++){
  41. tempv.set(j, tempv.get(j) - brans[l].vits.get(j));
  42. }
  43. }
  44. boolean isSol = true;
  45. for(int l : tempv){
  46. if(l > 0)
  47. isSol = false;
  48. }
  49. if(isSol){
  50. sols.add(k);
  51. }
  52. }
  53.  
  54. Collections.sort(sols, new Comparator<ArrayList<Integer>>() {
  55. @Override
  56. public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
  57. if(o1.size() > o2.size())
  58. return 1;
  59. if(o1.size() < o2.size())
  60. return -1;
  61. if(o1.get(0) > o2.get(0))
  62. return 1;
  63. if(o1.get(0) < o2.get(0))
  64. return -1;
  65. return 0;
  66. }
  67. });
  68.  
  69. pw.print(sols.get(0).size() + " ");
  70. int k;
  71. for(k = 0; k<sols.get(0).size()-1; k++)
  72. pw.print(sols.get(0).get(k) + " ");
  73. pw.println(sols.get(0).get(k));
  74. pw.close();
  75. }
  76.  
  77. static class Feed{
  78. List<Integer> vits;
  79. int name;
  80.  
  81. public Feed(int n, StringTokenizer st) throws IOException{
  82. name = n;
  83. vits = new ArrayList<Integer>();
  84. st = new StringTokenizer(br.readLine());
  85. for(int x = 0; x<vitamins; x++){
  86. vits.add(Integer.parseInt(st.nextToken()));
  87. }
  88. }
  89. }
  90.  
  91. public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
  92. ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  93.  
  94. if (n <= 0 || n < k)
  95. return result;
  96.  
  97. ArrayList<Integer> item = new ArrayList<Integer>();
  98. dfs(n, k, 1, item, result); // because it need to begin from 1
  99.  
  100. return result;
  101. }
  102.  
  103. private static void dfs(int n, int k, int start, ArrayList<Integer> item,
  104. ArrayList<ArrayList<Integer>> res) {
  105. if (item.size() == k) {
  106. res.add(new ArrayList<Integer>(item));
  107. return;
  108. }
  109.  
  110. for (int i = start; i <= n; i++) {
  111. item.add(i);
  112. dfs(n, k, i + 1, item, res);
  113. item.remove(item.size() - 1);
  114. }
  115. }
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement