UVA 696 – How Many Knights

This is extremely similar to UVA 278 – Chess but the tricky case is when min = 2. If you write it out on paper you will figure out the optimal placing for the knights.

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

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

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

    while (sc.hasNext()) {
      int R = sc.nextInt();
      int C = sc.nextInt();
      if (R == 0 && C == 0) {
        break;
      }
      int max = Math.max(R, C);
      int min = Math.min(R, C);
      if (min == 1) {
        out.print(max);
      } else if (min == 2) {
        if (max < 3) {
          out.print(min * max);
        } else if (max == 3) {
          out.print(4);
        } else {
          int tmp = max / 4;
          int rem = max % 4;
          out.print(tmp * min * 2 + Math.min(rem, 2) * 2);
        }
      } else {
        int a = max / 2;
        int b = (max - a);
        int c = min / 2;
        int d = (min - c);
        out.print(Math.max(a * c + b * d, a * d + b * c));
      }
      out.println(" knights may be placed on a " + R + " row " + C + " column board.");
    }

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

Leave a Reply

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