UVA 12247 – Jollo

I lazily figured out weather a given nubmer was good enough or not by trying all combinations. I’m sure there’s a better (greedy) way to do this that involves less work. Greedy doesn’t always work, but though so be careful! I messed up twice by trying a greedy strategy and gave up when I got tired of finding something that has no counterexamples.

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P12247 {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    while (sc.hasNext()) {
      int[] princess = new int[] { sc.nextInt(), sc.nextInt(), sc.nextInt() };
      if (princess[0] == 0)
        break;
      int[] prince = new int[] { -1, sc.nextInt(), sc.nextInt() };
      out.println(check(princess, prince));
    }

    out.close();
    sc.close();
  }

  // Cheating
  private static int[][] perm = { new int[] { 0, 1, 2 }, new int[] { 0, 2, 1 }, new int[] { 1, 0, 2 }, new int[] { 1, 2, 0 }, new int[] { 2, 0, 1 }, new int[] { 2, 1, 0 } };

  private static int check(int[] princess, int[] prince) {
    int[] tmpPrincess = Arrays.copyOf(princess, princess.length);
    int[] tmpPrince = null;
    int min = 1;
    boolean found = false;
    for (int i = min; !found && i <= 52; i++) {
      tmpPrince = Arrays.copyOf(prince, prince.length);
      tmpPrince[0] = i;
      if (i != tmpPrincess[0] && i != tmpPrincess[1] && i != tmpPrincess[2] && i != tmpPrince[1] && i != tmpPrince[2]) {
        min = i;
        // Try to lose
        int count = 0;
        for (int j = 0; count == 0 && j < perm.length; j++) {
          int subCount = 0;
          for (int k = 0; k < 3; k++) {
            if (tmpPrince[perm[j][k]] > tmpPrincess[k]) {
              subCount++;
            }
          }
          if (subCount < 2)
            count++;
        }
        if (count == 0)
          found = true;
      }
    }
    if (!found) {
      return -1;
    } else {
      return min;
    }
  }
}

One thought on “UVA 12247 – Jollo”

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.