Guest User

Untitled

a guest
May 25th, 2015
591
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.94 KB | None | 0 0
  1. package net.egork;
  2.  
  3. import net.egork.io.IOUtils;
  4. import net.egork.misc.ArrayUtils;
  5. import net.egork.utils.io.InputReader;
  6. import net.egork.utils.io.OutputWriter;
  7.  
  8. public class TaskA {
  9.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  10.         int count = in.readInt();
  11.         int[] length = new int[count];
  12.         int[] qty = new int[count];
  13.         IOUtils.readIntArrays(in, length, qty);
  14.         if (count > 1 && check(length, qty, count - 2, count - 1)) {
  15.             out.printLine("YES");
  16.             return;
  17.         }
  18.         for (int i = 0; i < count; i++) {
  19.             if (check(length, qty, count - 1, i)) {
  20.                 out.printLine("YES");
  21.                 return;
  22.             }
  23.         }
  24.         out.printLine("NO");
  25.     }
  26.  
  27.     private boolean check(int[] length, int[] qty, int top, int vertical) {
  28.         qty = qty.clone();
  29.         qty[top] -= 2;
  30.         if (qty[top] < 0) {
  31.             return false;
  32.         }
  33.         qty[vertical] -= 2;
  34.         if (qty[vertical] < 0) {
  35.             return false;
  36.         }
  37.         long needQty = 0;
  38.         long needLength = 0;
  39.         for (int i = 0; i < length.length; i++) {
  40.             if (i == vertical) {
  41.                 continue;
  42.             }
  43.             if (qty[i] != 0 && length[vertical] == 1) {
  44.                 return false;
  45.             }
  46.             if (qty[i] == 0) {
  47.                 continue;
  48.             }
  49.             long needThis = (qty[i] + length[vertical] - 2) / (length[vertical] - 1);
  50.             needQty += needThis;
  51.             needLength += needThis * length[i];
  52.         }
  53.         if (needLength == length[top]) {
  54.             needQty--;
  55.         }
  56.         long excess = qty[vertical] - needQty;
  57.         if (excess < 0) {
  58.             return false;
  59.         }
  60.         needLength += excess == 0 ? 0 : excess + 1;
  61.         if (needLength > length[top]) {
  62.             return false;
  63.         }
  64.         return true;
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment