Guest User

Sticks

a guest
Apr 21st, 2020
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.21 KB | None
  1. import java.util.TreeSet;
  2. import java.util.Scanner;
  3.  
  4. public class Sticks {
  5.     public static class Pair {
  6.         private int first;
  7.         private int second;
  8.  
  9.         Pair(int first, int second ) {
  10.             this.first = first;
  11.             this.second = second;
  12.         }
  13.  
  14.         private void swapPairValue() {
  15.             int temp = this.first;
  16.             this.first = this.second;
  17.             this.second = temp;
  18.         }
  19.  
  20.         @Override
  21.         public String toString() {
  22.             return String.format("|%d-%d|", this.first, this.second);
  23.         }
  24.     }
  25.  
  26.     private static void generate(TreeSet<String> set, Pair[] sticks, int index){
  27.         if (index == sticks.length){
  28.             StringBuilder toInsert = new StringBuilder();
  29.             for (int i = 0; i < sticks.length; i++) {
  30.                 toInsert.append(sticks[i].toString());
  31.                 toInsert.append(i == sticks.length-1 ? "" : " # ");
  32.             }
  33.             set.add(toInsert.toString());
  34.         }else{
  35.             for (int i = index; i < sticks.length; i++){
  36.                 swapElement(sticks, index, i);
  37.                 generate(set, sticks, index + 1);
  38.                
  39.                 sticks[index].swapPairValue();
  40.                 generate(set, sticks, index +1);
  41.                
  42.                 sticks[index].swapPairValue();
  43.                 swapElement(sticks, index, i);
  44.             }
  45.         }
  46.     }
  47.  
  48.     private static void swapElement(Pair[] sticks, int index1, int index2) {
  49.         Pair temp = sticks[index1];
  50.         sticks[index1] = sticks[index2];
  51.         sticks[index2] = temp;
  52.     }
  53.  
  54.     public static void main(String[] args) {
  55.         Scanner console = new Scanner(System.in);
  56.         TreeSet <String> set = new TreeSet <>();
  57.         int steps = Integer.parseInt(console.nextLine());
  58.         Pair[] sticks = new Pair[steps];
  59.  
  60.         for (int i = 0; i < steps; i++)
  61.             sticks[i] = new Pair(console.nextInt(), console.nextInt());
  62.  
  63.         generate(set, sticks, 0);
  64.  
  65.         System.out.println(set.size());
  66.         set
  67.                 .stream()
  68.                 .sorted(String::compareTo)
  69.                 .forEach(System.out::println);
  70.         console.close();
  71.     }
  72. }
RAW Paste Data Copied