All posts by Rawrosaur

UVA 278 – Chess

Pretty easy problem. Kings, Queens and Rooks are easy; with Knights you need to realize that knigns basically attack boxes of the opposite color. Once you figure that out, you are golden.

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

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

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

    int N = sc.nextInt();
    for (int zz = 0; zz < N; zz++) {
      String type = sc.next();
      int R = sc.nextInt();
      int C = sc.nextInt();
      int min = Math.min(R, C);
      int max = Math.max(R, C);
      if (type.equals("r") || type.equals("Q")) {
        out.println(min);
      } else if (type.equals("k")) {
        int a = max / 2;
        int b = (max - a);
        int c = min / 2;
        int d = (min - c);
        out.println(Math.max(a * c + b * d, a * d + b * c));
      } else if (type.equals("K")) {
        out.println(((max + 1) / 2) * ((min + 1) / 2));
      }
    }

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

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;
    }
  }
}

UVA 10646 – What is the Card?

Pretty straightforward. Don’t even need to use this Card class that I have been using for the past few questions!

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

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

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

    int N = sc.nextInt();
    for (int zz = 1; zz <= N; zz++) {
      String[] deck = new String[52];
      for (int i = 0; i < 52; i++) {
        deck[i] = sc.next();
      }
      int Y = 0;
      int last = -1;
      int count = 0;
      for (int i = 25; i >= 0 && count < 3; i--) {
        int val = getVal(deck[i]);
        Y += val;
        i -= (10 - val);
        count++;
        last = i;
      }

      if (Y <= last) {
        out.println("Case " + zz + ": " + deck[Y - 1]);
      } else {
        out.println("Case " + zz + ": " + deck[26 + (Y - last) - 1]);
      }
    }
    sc.close();
    out.close();
  }

  private static int getVal(String card) {
    char c = card.charAt(0);
    if (c >= '2' && c <= '9') {
      return Integer.parseInt(c + "");
    }
    return 10;
  }
}

UVA 10205 – Stack ’em Up

Pretty much just an implementation problem.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

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

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    String line = null;
    StringTokenizer st = null;

    int cases = Integer.parseInt(br.readLine());
    br.readLine(); // Read blank line.

    for (int zz = 0; zz < cases; zz++) {
      if (zz != 0)
        out.println();

      int shuffles = Integer.parseInt(br.readLine());
      int[][] caesar = new int[shuffles][52];
      for (int i = 0; i < shuffles; i++) {
        int count = 0;
        while (count < 52) {
          st = new StringTokenizer(br.readLine());
          while (st.hasMoreTokens()) {
            caesar[i][count] = Integer.parseInt(st.nextToken()) - 1;
            count++;
          }
        }
      }

      Card[] newDeck = new Card[52];
      init(newDeck);
      while ((line = br.readLine()) != null) {
        if (line.trim().equals(""))
          break;
        int move = Integer.parseInt(line) - 1;
        Card[] tmp = new Card[52];
        for (int i = 0; i < 52; i++) {
          tmp[i] = newDeck[caesar[move][i]];
        }
        newDeck = tmp;
      }
      for (int i = 0; i < 52; i++) {
        out.println(newDeck[i]);
      }
    }

    out.close();
    br.close();
  }

  private static void init(Card[] newDeck) {
    String[] suitOrder = new String[] { "Clubs", "Diamonds", "Hearts", "Spades" };
    String[] order = { "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace" };
    for (int j = 0; j < 4; j++) {
      for (int i = 0; i < 13; i++) {
        newDeck[i + 13 * j] = new Card(order[i], suitOrder[j]);
      }
    }
  }

  @SuppressWarnings("unused")
  private static class Card {
    String card;
    String card2;
    String num;
    String suit;

    public Card(String num, String suit) {
      card2 = num + " of " + suit;
      this.num = num;
      this.suit = suit;
      if (this.num == "10") {
        card = "T" + suit.charAt(0);
      } else {
        card = num.charAt(0) + "" + suit.charAt(0);
      }
    }

    public String toString() {
      return this.card2;
    }
  }
}

UVA 162 – Beggar My Neighbour

This was a pain to debug but I finally got it right. There’s a little bit of trickery with outputting the result as well so watch out for that!

import java.io.PrintWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

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

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

    while (sc.hasNextLine()) {
      String line = sc.nextLine().trim();
      while (line.equals(""))
        line = sc.nextLine();
      if (line.equals("#"))
        break;

      gameOver = false;
      Player[] players = new Player[2];
      for (int i = 0; i < players.length; i++) {
        players[i] = new Player();
      }
      Card[] deck = new Card[52];
      StringTokenizer st = new StringTokenizer(line);
      for (int i = 0; i < 13; i++) {
        deck[i] = new Card(st.nextToken());
      }
      for (int i = 13; i < 52; i++) {
        deck[i] = new Card(sc.next());
      }

      for (int j = 0; j < players.length; j++) {
        for (int i = 0; i < 26; i++) {
          players[j].deck.add(deck[i * 2 + j]);
        }
        Collections.reverse(players[j].deck);
      }

      // players[0] = non-dealer
      // players[1] = dealer

      int idx = 0;
      LinkedList<Card> stack = new LinkedList<>();
      while ((players[0].deck.size() > 0 || players[1].deck.size() > 0) && !gameOver) {
        Card played = players[idx].deck.poll();
        if (played == null)
          break;
        stack.add(played);
        if (played.isFaceCard()) {
          idx = doThing(stack, players, idx);
        }
        idx = 1 - idx;
      }
      if (players[0].deck.isEmpty()) {
        out.println("1 " + String.format("%2d", players[1].deck.size()));
      } else {
        out.println("2 " + String.format("%2d", players[0].deck.size()));
      }

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

  private static boolean gameOver = false;

  private static int doThing(LinkedList<Card> stack, Player[] players, int idx) {
    boolean good = true;
    idx = 1 - idx;
    int val = getGameCardVal(stack.peekLast());
    for (int i = 0; i < val; i++) {
      Card played = players[idx].deck.poll();
      if (played == null) {
        gameOver = true;
        good = false;
        break;
      } else {
        stack.add(played);
        if (played.isFaceCard()) {
          return doThing(stack, players, idx);
        }
      }
    }
    if (good)
      while (!stack.isEmpty()) {
        players[1 - idx].deck.add(stack.poll());
      }
    return idx;
  }

  private static int getGameCardVal(Card c) {
    switch (c.card.charAt(1)) {
      case 'A':
        return 4;
      case 'K':
        return 3;
      case 'Q':
        return 2;
      case 'J':
        return 1;
    }
    return 0;
  }

  private static class Card {
    String card;

    public Card(String card) {
      int test1 = getSuitIdx(card.charAt(0));
      if (test1 == -1)
        return;
      int test2 = getNumIdx(card.charAt(1));
      if (test2 == -1)
        return;
      this.card = card;
    }

    public boolean isFaceCard() {
      int val = getCardValue();
      return (val == 1 || val == 11 || val == 12 || val == 13);
    }

    public int getCardValue() {
      return getNumIdx(card.charAt(1));
    }

    private int getSuitIdx(char suit) {
      switch (suit) {
        case 'H':
          return 0;
        case 'S':
          return 1;
        case 'D':
          return 2;
        case 'C':
          return 3;
      }
      return -1;
    }

    private int getNumIdx(char num) {
      switch (num) {
        case 'A':
          return 1;
        case 'T':
          return 10;
        case 'J':
          return 11;
        case 'Q':
          return 12;
        case 'K':
          return 13;
        default:
          try {
            int val = Integer.parseInt(num + "");
            if (val > 1 && val < 10)
              return val;
            return -1;
          } catch (Exception e) {
            return -1;
          }
      }
    }

    @Override
    public String toString() {
      return this.card;
    }

  }

  private static class Player {
    private LinkedList<Card> deck;

    public Player() {
      deck = new LinkedList<>();
    }

    @Override
    public String toString() {
      return this.deck.toString();
    }
  }

}

UVA 12478 – Hardest Problem Ever (Easy)

So this was an interesting problem. You could have technically solved it manually but that would have taken too much time. If you didn’t mind at most 7 WA’s you could have just tried all 8 solutions one at a time and gotten it correct. I did it the long way; making my program solve it for me.

I used this string normalization technique I was ‘taught’ in college. It’s a neat little trick that I seem to use every chance I get. Pretty easy solution once you know you can map all permutations of a string to just one string!

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 P12478 {

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

    String[] grid = new String[] { "OBIDAIBKR", "RKAULHISP", "SADIYANNO", "HEISAWHIA", "IRAKIBULS", "MFBINTRNO", "UTOYZIFAH", "LEBSYNUNE", "EMOTIONNAL" };

    String[] originalNames = new String[] { "RAKIBUL", "ANINDYA", "MOSHIUR", "SHIPLU", "KABIR", "SUNNY", "OBAIDA", "WASI" };

    String[] names = new String[originalNames.length];
    int[] count = new int[names.length];

    for (int i = 0; i &lt; names.length; i++) {
      names[i] = normalize(originalNames[i]);
    }

    // Check Horizontally
    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) { //Shortest name is 4 characters so we are checking for sub-strings of at least that length. We could also have capped the sub-string to at most 7 characters based on the names provided.
          String substring = normalize(grid[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    // Check Vertically
    String[] grid2 = new String[grid.length];
    for (int j = 0; j &lt; 9; j++) {
      char[] tmp = new char[9];
      for (int i = 0; i &lt; 9; i++) {
        tmp[i] = grid[i].charAt(j);
      }
      grid2[j] = new String(tmp);
    }

    for (int zz = 0; zz &lt; 9; zz++) {
      for (int i = 0; i &lt; 9; i++) {
        for (int j = i + 4; j &lt;= 9; j++) {
          String substring = normalize(grid2[zz].substring(i, j));
          for (int k = 0; k &lt; names.length; k++) {
            if (substring.equals(names[k])) {
              count[k]++;
            }
          }
        }
      }
    }

    for (int i = 0; i &lt; count.length; i++) {
      if (count[i] == 2) {
        out.println(originalNames[i]);
      }
    }

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

  // Normalizes all strings
  private static String normalize(String word) {
    char[] list = word.toCharArray();
    Arrays.sort(list);
    return new String(list);
  }
}

Edit: Further explanation. I’ve also updated the code to avoid the IndexOutOfBounds exception I was strangely using a try-catch for.

Firstly let us cover the normalize function. As you can tell by the code, it takes a word, splits it into a character array, sorts the character array and then converts it back into a string. Let us take some examples so that this is clear.

Take a word, let’s say: apple once you run it through the normalize function it will become aelpp. The same will happen for all permutations of apple (I won’t list them all) for example aplpe, ppael, leapp, etc. This allows us to quickly check if a particular permutation of a word is in the grid.

If this part is clear then we can just move on to the checking part.

We will go through the grid one row at a time (the code with the comment stating horizontal). Find all substrings within that line, normalize them and then compare them with the names array. If they are in the array then we increment a counter (named count). We do the same thing for the grid vertically.

UVA 11956 – Brainfuck

So this problem wont work on uva however I am pretty sure that my implementation is correct. Really simple problem.

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

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

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

int T = Integer.parseInt(sc.nextLine());
for (int zz = 1; zz <= T; zz++) { int idx = 0; int[] byteArray = new int[100]; char[] input = sc.nextLine().trim().toCharArray(); for (int i = 0; i < input.length; i++) {         switch (input[i]) {           case '>‘:
idx++;
break;
case ‘<': idx--; break; case '+': byteArray[idx]++; break; case '-': byteArray[idx]--; break; } idx = (idx + byteArray.length) % byteArray.length; byteArray[idx] = (byteArray[idx] + 256) % 256; } out.print("Case " + zz + ":"); for (int i = 0; i < byteArray.length; i++) { String print = String.format("%02x", byteArray[i]).toUpperCase(); out.print(" " + print); } out.println(); } out.close(); sc.close(); } } [/java]

UVA 11687 – Digits

This question is terribly worded I think. Basically it wants you to find the length of the input string and let this length become the new string. Keep following this process until the length of the string and string are the same.

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

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

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

    while (sc.hasNext()) {
      String input = sc.next();
      if (input.equals("END"))
        break;
      out.println(solve(input));
    }

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

  private static int solve(String input) {
    int count = 1;
    int len = input.length();
    if ((len + "").equals(input))
      return count;
    else
      return count + solve(len + "");
  }
}

UVA 11683 – Laser Sculpture

One pass is indeed enough!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

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

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;
    String line;

    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line.trim());
      int A = Integer.parseInt(st.nextToken());
      if (A == 0)
        break;

      int B = Integer.parseInt(st.nextToken());
      int[] sculpt = new int[B];
      st = new StringTokenizer(br.readLine().trim());
      int ans = 0;
      int last = -1;
      for (int i = 0; i < B; i++) {
        sculpt[i] = Integer.parseInt(st.nextToken());
        if (last == -1) {
          last = sculpt[i];
          if (sculpt[i] != A)
            ans += (A - sculpt[i]);
        }
        if (sculpt[i] >= last) {
          last = sculpt[i];
        } else {
          ans += (last - sculpt[i]);
          last = sculpt[i];
        }
      }
      out.println(ans);
    }

    out.close();
    br.close();
  }
}

UVA 11661 – Burger Time?

Just keep track of the last burger joint you saw and the last restaurant you saw. You can solve this greedily. If you ever find a ‘Z’ then the answer is immediately always 0.

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

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

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

    while (sc.hasNextLine()) {
      int L = Integer.parseInt(sc.nextLine());
      if (L == 0)
        break;
      char[] road = sc.nextLine().toCharArray();
      int lastDrugStore = -1;
      int lastRestaurant = -1;
      int min = Integer.MAX_VALUE;
      for (int i = 0; i < road.length; i++) {
        if (road[i] == 'R') {
          lastRestaurant = i;
        } else if (road[i] == 'D') {
          lastDrugStore = i;
        } else if (road[i] == 'Z') {
          min = 0;
          break;
        }
        if (lastDrugStore != -1 && lastRestaurant != -1) {
          min = Math.min(Math.abs(lastDrugStore - lastRestaurant), min);
        }
      }
      out.println(min);
    }

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

}