Advertisement
florence20

Untitled

Apr 16th, 2018
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileNotFoundException;
  4. import java.io.FileReader;
  5. import java.io.IOException;
  6. import java.io.PrintWriter;
  7. import java.util.ArrayList;
  8. import java.util.Arrays;
  9. import java.util.Collections;
  10. import java.util.Comparator;
  11. import java.util.LinkedList;
  12.  
  13. public class Numaratoare {
  14.  
  15. public static final String INPUT_FILE = "numaratoare.in";
  16. public static final String OUTPUT_FILE = "numaratoare.out";
  17. Integer[] numbers;
  18. int s, n, i;
  19. /*
  20. * lista de liste va retine toate combinatiile de numere
  21. * care obtin suma dorita
  22. */
  23. LinkedList<LinkedList<Integer>> res = new LinkedList<>();
  24.  
  25. public void readInput() {
  26. try {
  27. BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
  28. s = Integer.parseInt(reader.readLine());
  29. n = Integer.parseInt(reader.readLine());
  30. i = Integer.parseInt(reader.readLine());
  31. reader.close();
  32. } catch (IOException e) {
  33. throw new RuntimeException(e);
  34. }
  35. numbers = new Integer[s];
  36. for (int j = 0; j < s; j++) {
  37. numbers[j] = j + 1;
  38. }
  39. }
  40.  
  41. /*
  42. * primeste suma si o lista auxiliara in care se consruieste
  43. * sirul dorit; indicele pastajeaza vectorul pentru a sti
  44. * de pe ce pozitie incolo mai putem extrage
  45. */
  46. public void findNumbers(int sum, LinkedList<Integer> r, int i) {
  47. if (sum < 0) {
  48. return;
  49. }
  50. if (sum == 0 && n == r.size()) {
  51. LinkedList<Integer> aux = (LinkedList<Integer>) r.clone();
  52. Collections.reverse(aux);
  53. res.add(aux);
  54. return;
  55. }
  56. while (i < numbers.length && sum - numbers[i] >= 0) {
  57. r.add(numbers[i]);
  58. findNumbers(sum - numbers[i], r, i);
  59. i++;
  60. r.removeLast();
  61. }
  62. }
  63.  
  64. public void combinationSum(int sum) {
  65. LinkedList<Integer> r = new LinkedList<>();
  66. findNumbers(sum, r, 0);
  67. }
  68.  
  69. public void writeOutput() throws FileNotFoundException {
  70. System.out.println(s + " " + n + " " + i);
  71. System.out.println(res.size());
  72.  
  73. PrintWriter pw = new PrintWriter(new File(OUTPUT_FILE));
  74. if (i >= res.size()) {
  75. pw.printf("-");
  76. pw.close();
  77. } else {
  78. for (LinkedList<Integer> x : res) {
  79. System.out.println(x);
  80. }
  81. LinkedList<Integer> r = res.get(i);
  82. pw.printf("%d=%d", s, r.get(0));
  83. r.remove(0);
  84. r.forEach((element) -> {
  85. pw.printf("+%d", element);
  86. });
  87. pw.close();
  88. }
  89.  
  90. }
  91.  
  92. public void solve() throws FileNotFoundException {
  93. readInput();
  94. combinationSum(s);
  95. writeOutput();
  96. }
  97.  
  98. public static void main(String[] args) throws FileNotFoundException {
  99. new Numaratoare().solve();
  100. }
  101.  
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement