Advertisement
Danielto2000

Untitled

Nov 9th, 2018
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.02 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. public class TASK_C {
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         int maxSize = (int) Math.pow(2, 5);
  9.         ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();
  10.         for (int i = 0; i < maxSize; i++) {
  11.             matrix.add(new ArrayList<Integer>());
  12.             for (int j = 0; j < 5; j++) {
  13.                 matrix.get(i).add(getBit(i, 5 - j - 1));
  14.             }
  15.         }
  16.         int k = Integer.parseInt(sc.next());
  17.         boolean[] isOk = new boolean[5];
  18.         Arrays.fill(isOk, false);
  19.         for (int i = 0; i < k; i++) {
  20.             int curNumbers = Integer.parseInt(sc.next());
  21.             String truth = sc.next();
  22.             int curBits[] = new int[(int) Math.pow(2, curNumbers)];
  23.             for (int j = 0; j < curBits.length; j++) {
  24.                 curBits[j] = Integer.parseInt(truth.substring(j, j + 1));
  25.             }
  26.             isOk[0] = isOk[0] || nonConserveZero(curBits);
  27.             isOk[1] = isOk[1] || nonConserveOne(curBits);
  28.             isOk[2] = isOk[2] || !isLinear(curBits);
  29.             isOk[3] = isOk[3] || !SD(curBits);
  30.             isOk[4] = isOk[4] || !MONO(curBits, matrix);
  31.         }
  32.         for (int i = 0; i < 5; i++) {
  33.             if (!isOk[i]) {
  34.                 System.out.println("NO");
  35.                 return;
  36.             }
  37.         }
  38.         System.out.println("YES");
  39.     }
  40.  
  41.     public static int getBit(int number, int shift) {
  42.         return (number >> shift) % 2;
  43.     }
  44.  
  45.     public static boolean nonConserveZero(int[] values) {
  46.         return values[0] == 1;
  47.     }
  48.  
  49.     public static boolean nonConserveOne(int[] values) {
  50.         return values[values.length - 1] == 0;
  51.     }
  52.  
  53.     public static boolean isLinear(int[] values) {
  54.         int[] coefficient = makePoly(values);
  55.         int k = 1;
  56.         for (int i = 1; i < coefficient.length; i++) {
  57.             if (i == k) {
  58.                 k *= 2;
  59.             } else if (coefficient[i] == 1) return false;
  60.         }
  61.         return true;
  62.     }
  63.  
  64.     public static int[] makePoly(int[] values) {
  65.         ArrayList<Integer> coefficient = new ArrayList<>();
  66.         int curSize = values.length;
  67.         int firstIndex = 0;
  68.         for (int i = 0; i < curSize; i++) {
  69.             coefficient.add(values[i]);
  70.         }
  71.         while (firstIndex < curSize - 1) {
  72.             for (int i = firstIndex; i < curSize - 1; i++) {
  73.                 int cur;
  74.                 cur = coefficient.get(i) ^ coefficient.get(i + 1);
  75.                 coefficient.add(cur);
  76.             }
  77.             firstIndex++;
  78.             int toRemove = values.length - 1;
  79.             while (toRemove >= firstIndex) {
  80.                 coefficient.remove(firstIndex);
  81.                 toRemove--;
  82.             }
  83.         }
  84.         int[] b = new int[values.length];
  85.         for (int i = 0; i < coefficient.size(); i++) {
  86.             b[i] = coefficient.get(i);
  87.         }
  88.         return b;
  89.     }
  90.  
  91.     public static boolean SD(int[] values) {
  92.         int size = values.length;
  93.         if (size == 1) return false;
  94.         for (int i = 0; i < size / 2; i++) {
  95.             if (values[i] == values[size - i - 1]) return false;
  96.         }
  97.         return true;
  98.     }
  99.  
  100.     public static boolean dominate(ArrayList<Integer> firstLine, ArrayList<Integer> secondLine) {
  101.         for (int i = 0; i < firstLine.size(); i++) {
  102.             if (firstLine.get(i) > secondLine.get(i)) {
  103.                 return false;
  104.             }
  105.         }
  106.         return true;
  107.     }
  108.  
  109.     public static boolean MONO(int[] values, ArrayList<ArrayList<Integer>> table) {
  110.         for (int i = 0; i < values.length; i++) {
  111.             if (values[i] != 0) {
  112.                 for (int j = i + 1; j < values.length; j++) {
  113.                     if (dominate(table.get(i), table.get(j)) && values[i] > values[j]) {
  114.                         return false;
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.         return true;
  120.     }
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement