Guest User

Sequence NM

a guest
Jan 11th, 2019
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package _06SequenceNM;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.Arrays;
  7. import java.util.Deque;
  8. import java.util.LinkedList;
  9. import java.util.stream.Collectors;
  10.  
  11. /**
  12.  * Created by IntelliJ IDEA.
  13.  * User: LAPD
  14.  * Date: 10.1.2019 г.
  15.  * Time: 15:52 ч.
  16.  */
  17. public class _06SequenceNM {
  18.     public static void main(String[] args) throws IOException {
  19.  
  20.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  21.  
  22.         int[] input = Arrays.stream(bufferedReader.readLine()
  23.                 .split("\\s+"))
  24.                 .mapToInt(Integer::parseInt)
  25.                 .toArray();
  26.  
  27.         int start = input[0];
  28.         int end = input[1];
  29.  
  30.         if (end <= start) {
  31.             return;
  32.         }
  33.  
  34.         Deque<Item> queue = new LinkedList<>();
  35.  
  36.         queue.addLast(new Item(start));
  37.  
  38.         while (queue.size() > 0) {
  39.             Item current = queue.removeFirst();
  40.  
  41.             int nextValue1 = current.value + 1;
  42.             int nextValue2 = current.value + 2;
  43.             int nextValue3 = current.value * 2;
  44.  
  45.             if (nextValue1 == end
  46.                     || nextValue2 == end
  47.                     || nextValue3 == end) {
  48.                 print(current, end);
  49.                 break;
  50.             }
  51.  
  52.             if (nextValue1 < end) {
  53.                 queue.addLast(new Item(nextValue1, current));
  54.             }
  55.             if (nextValue2 < end) {
  56.                 queue.addLast(new Item(nextValue2, current));
  57.             }
  58.             if (nextValue3 < end) {
  59.                 queue.addLast(new Item(nextValue3, current));
  60.             }
  61.         }
  62.     }
  63.  
  64.     private static void print(Item item, int end) {
  65.  
  66.         Deque<Integer> deque = new LinkedList<>();
  67.  
  68.         deque.addFirst(end);
  69.         while (item.previous != null) {
  70.             deque.addFirst(item.value);
  71.             item = item.previous;
  72.         }
  73.         deque.addFirst(item.value);
  74.  
  75.         System.out.println(Arrays.stream(deque.toArray())
  76.                 .map(String::valueOf)
  77.                 .collect(Collectors.joining(" -> ")));
  78.     }
  79.  
  80.     private static class Item {
  81.  
  82.         private int value;
  83.         private Item previous;
  84.  
  85.         public Item() {
  86.             this.previous = null;
  87.         }
  88.  
  89.         public Item(int value) {
  90.             this(value, null);
  91.         }
  92.  
  93.         public Item(int value, Item previous) {
  94.             this.value = value;
  95.             this.previous = previous;
  96.         }
  97.  
  98.         public int getValue() {
  99.             return value;
  100.         }
  101.  
  102.         public void setValue(int value) {
  103.             this.value = value;
  104.         }
  105.  
  106.         public Item getPrevious() {
  107.             return previous;
  108.         }
  109.  
  110.         public void setPrevious(Item previous) {
  111.             this.previous = previous;
  112.         }
  113.     }
  114. }
RAW Paste Data