Advertisement
Guest User

Untitled

a guest
May 26th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.80 KB | None | 0 0
  1. package qualification;
  2.  
  3. import java.util.*;
  4. import java.util.stream.Collectors;
  5.  
  6. public class B {
  7.     public static void main(String[] args) {
  8.         Scanner in = new Scanner(System.in);
  9.         int k = in.nextInt();
  10.         HashMap<String, Integer> map = new HashMap<>();
  11.         List<String> strings = new ArrayList<>();
  12.         int total = (int) (Math.pow(2, k) - 1);
  13.         in.nextLine();
  14.         for (int i = 0; i < total; i++) {
  15.             strings.add(Arrays.stream(in.nextLine().split(" ")).sorted(String::compareTo).reduce((a, b) -> a + " " + b).get());
  16.         }
  17.  
  18.         if (strings.size() != new HashSet<>(strings).size()) {
  19.             System.out.println("NO SOLUTION");
  20.             return;
  21.         }
  22.  
  23.         for (int i = 0; i < total; i++) {
  24.             String[] s = strings.get(i).split(" ");
  25.             map.put(s[0], map.getOrDefault(s[0], 0) + 1);
  26.             map.put(s[1], map.getOrDefault(s[1], 0) + 1);
  27.         }
  28.         if (map.keySet().size() != total + 1) {
  29.             System.out.println("NO SOLUTION");
  30.             return;
  31.         }
  32.         boolean res = true;
  33.         int count = (total + 1) / 2;
  34.         for (int i = 0; i < k; i++) {
  35.             int finalI = i;
  36.             if (i != k - 1) {
  37.                 res = res && map.values().stream().filter(q -> q == finalI + 1).count() == count;
  38.             } else {
  39.                 res = res && map.values().stream().filter(q -> q == finalI + 1).count() == count * 2;
  40.             }
  41.             count /= 2;
  42.         }
  43.         if (res) {
  44.             List<String> finalists = map.keySet().stream().filter(q -> map.get(q) == k - 1).collect(Collectors.toList());
  45.             System.out.println(finalists.get(0) + " " + finalists.get(1));
  46.         } else {
  47.             System.out.println("NO SOLUTION");
  48.         }
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement