fork(1) download
  1. import java.util.*;
  2.  
  3. class Ideone {
  4. public static void main(String[] args) {
  5. final Scanner scanner = new Scanner(System.in);
  6. int start = scanner.nextInt();
  7. int end = scanner.nextInt();
  8.  
  9. final LinkedList<Range> left = leftBounds(start, end);
  10. final Range lastLeft = left.removeLast();
  11.  
  12. final LinkedList<Range> right = rightBounds(lastLeft.getStart(), end);
  13. final Range firstRight = right.removeFirst();
  14.  
  15. LinkedList<Range> merged = new LinkedList<>();
  16. merged.addAll(left);
  17. if (!lastLeft.overlaps(firstRight)) {
  18. merged.add(lastLeft);
  19. merged.add(firstRight);
  20. } else {
  21. merged.add(Range.join(lastLeft, firstRight));
  22. }
  23. merged.addAll(right);
  24.  
  25. merged.stream()
  26. .map(Range::toRegex)
  27. .forEach(System.out::println);
  28. }
  29.  
  30. private static LinkedList<Range> leftBounds(int start, int end) {
  31. final LinkedList<Range> result = new LinkedList<>();
  32. while (start < end) {
  33. final Range range = Range.fromStart(start);
  34. result.add(range);
  35. start = range.getEnd()+1;
  36. }
  37. return result;
  38. }
  39.  
  40. private static LinkedList<Range> rightBounds(int start, int end) {
  41. final LinkedList<Range> result = new LinkedList<>();
  42. while (start < end) {
  43. final Range range = Range.fromEnd(end);
  44. result.add(range);
  45. end = range.getStart()-1;
  46. }
  47. Collections.reverse(result);
  48. return result;
  49. }
  50.  
  51. }
  52.  
  53. class Range {
  54. private final int start;
  55. private final int end;
  56.  
  57. public static Range fromEnd(int end) {
  58. final char[] chars = String.valueOf(end).toCharArray();
  59. for (int i=chars.length-1; i>=0;i--) {
  60. if (chars[i] == '9') {
  61. chars[i] = '0';
  62. } else {
  63. chars[i] = '0';
  64. break;
  65. }
  66. }
  67.  
  68. return new Range(Integer.parseInt(String.valueOf(chars)), end);
  69. }
  70.  
  71. public static Range fromStart(int start) {
  72. final char[] chars = String.valueOf(start).toCharArray();
  73. for (int i=chars.length-1; i>=0;i--) {
  74. if (chars[i]=='0') {
  75. chars[i] = '9';
  76. } else {
  77. chars[i] = '9';
  78. break;
  79. }
  80. }
  81.  
  82. return new Range(start, Integer.parseInt(String.valueOf(chars)));
  83. }
  84.  
  85. public static Range join(Range a, Range b) {
  86. return new Range(a.start, b.end);
  87. }
  88.  
  89. private Range(int start, int end) {
  90. this.start = start;
  91. this.end = end;
  92. }
  93.  
  94. public int getStart() {
  95. return start;
  96. }
  97.  
  98. public int getEnd() {
  99. return end;
  100. }
  101.  
  102. public boolean overlaps(Range r) {
  103. return end > r.start && r.end > start;
  104. }
  105.  
  106. @Override
  107. public String toString() {
  108. return String.format("Range{start=%d, end=%d}", start, end);
  109. }
  110.  
  111. public String toRegex() {
  112. String startStr = String.valueOf(getStart());
  113. String endStr = String.valueOf(getEnd());
  114.  
  115. final StringBuilder result = new StringBuilder();
  116.  
  117. for (int pos = 0; pos < startStr.length(); pos++) {
  118. if (startStr.charAt(pos) == endStr.charAt(pos)) {
  119. result.append(startStr.charAt(pos));
  120. } else {
  121. result.append('[')
  122. .append(startStr.charAt(pos))
  123. .append('-')
  124. .append(endStr.charAt(pos))
  125. .append(']');
  126. }
  127. }
  128. return result.toString();
  129. }
  130. }
  131.  
Success #stdin #stdout 0.23s 2841600KB
stdin
45 583
stdout
4[5-9]
[5-9][0-9]
[1-4][0-9][0-9]
5[0-7][0-9]
58[0-3]