Category Archives: Java

UVA 10919 – Prerequisites?

Super easy. HashSet would have provided better performance than an ArrayList though.

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

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

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

    while (sc.hasNextInt()) {
      int K = sc.nextInt();
      if (K == 0)
        break;
      int M = sc.nextInt();

      ArrayList<String> courses = new ArrayList<>();
      for (int i = 0; i < K; i++) {
        courses.add(sc.next());
      }

      boolean good = true;
      for (int i = 0; i < M; i++) {
        int num = sc.nextInt();
        int min = sc.nextInt();
        int count = 0;
        for (int j = 0; j < num; j++) {
          String course = sc.next();
          if (courses.contains(course))
            count++;
        }
        if (count < min)
          good = false;
      }

      if (good) {
        out.println("yes");
      } else {
        out.println("no");
      }
    }

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

}

UVA 10424 – Love Calculator

Pretty easy. Just make appropriate functions and call them recursively.

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

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

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

    DecimalFormat df = new DecimalFormat();
    df.setMinimumFractionDigits(2);
    df.setMaximumFractionDigits(2);

    while (sc.hasNextLine()) {
      String first = sc.nextLine().toLowerCase();
      String second = sc.nextLine().toLowerCase();
      double numFirst = toNum(convert(first));
      double numSecond = toNum(convert(second));
      double ans;
      if (numFirst < numSecond) {
        ans = numFirst * 100 / numSecond;
      } else {
        ans = numSecond * 100 / numFirst;
      }
      out.println(df.format(ans) + " %");
    }

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

  private static String convert(String first) {
    int x = 0;
    for (int i = 0; i < first.length(); i++) {
      char c = first.charAt(i);
      if (c >= 'a' && c <= 'z')
        x += (c - 'a') + 1;
    }
    return x + "";
  }

  private static double toNum(String first) {
    if (first.length() != 1) {
      int x = 0;
      for (int i = 0; i < first.length(); i++) {
        x += Integer.parseInt(first.charAt(i) + "");
      }
      return toNum(x + "");
    } else {
      return Double.parseDouble(first);
    }
  }

}

UVA 10324 – Zeros and Ones

I finally solved this problem. Everytime I see the word queries or MOD 1000000007 I instantly panic because I know I haven’t quite yet gotten to making a Segment Tree or solving DP problems yet. I did end up making a Segment Tree that does successfully solve this problem however since our input is so huge it will most definitely TLE. Here is my solution, I can just keep summing the values and put them in an ArrayList and then just compare the sums at the query endpoints. I did however miss out the edge case of [1,0,0,0,0] as the sum would be same at both ends however the actual numbers are different. I just added that case in and AC!

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

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

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

    long test = 1;
    String line = null;
    while ((line = br.readLine()) != null) {
      char[] input = line.trim().toCharArray();
      if (input.length == 0)
        break;
      ArrayList<Integer> sumArray = new ArrayList<Integer>();
      int sum = 0;
      for (int i = 0; i < input.length; i++) {
        sum += Integer.parseInt(input[i] + "");
        sumArray.add(sum);
      }
      int N = Integer.parseInt(br.readLine().trim());
      out.println("Case " + test + ":");
      for (int i = 0; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        out.println(solve(Math.min(a, b), Math.max(a, b), sumArray, input));
      }
      test++;
    }
    out.close();
    br.close();
  }

  private static String solve(int min, int max, ArrayList<Integer> sumArray, char[] input) {
    int a = sumArray.get(min);
    int b = sumArray.get(max);
    if ((a == b || b - a + 1 == max - min + 1) && input[min] == input[max]) {
      return "Yes";
    } else {
      return "No";
    }
  }

}

UVA 1112 – Mice and Maze

This question is part of the Competitive Programming 3 book however I haven’t quite reached that chapter yet. Let me see how my approach to solving this problem changes once I get there.

Below is the way I would have done it without having reading the book.

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

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

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

    int zz = sc.nextInt();
    for (int i = 0; i &lt; zz; i++) {
      if (i != 0)
        out.println();
      int N = sc.nextInt();
      int E = sc.nextInt() - 1;
      int T = sc.nextInt();
      int M = sc.nextInt();
      Node[] graph = new Node[N];
      for (int j = 0; j &lt; N; j++) {
        graph[j] = new Node(j);
      }
      for (int j = 0; j &lt; M; j++) {
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        int c = sc.nextInt();
        graph[a].add(graph[b], c);
      }
      int[] shortest = new int[N];
      for (int j = 0; j &lt; N; j++) {
        if (shortest[j] == 0) {
          Object[] output = dfs(graph, j, E);
          if (output != null) {
            @SuppressWarnings(&quot;unchecked&quot;)
            ArrayList&lt;Integer&gt; tmp = (ArrayList&lt;Integer&gt;) output[0];
            int cost = (int) output[1];
            int size = tmp.size();
            int thing = 0;
            shortest[tmp.get(0)] = cost;
            for (int k = 1; k &lt; size; k++) {
              thing += graph[tmp.get(k - 1)].cost.get(tmp.get(k));
              shortest[tmp.get(k)] = cost - thing;
            }
          } else {
            shortest[j] = -1;
          }
          for (int k = 0; k &lt; N; k++) {
            graph[k].visited = false;
          }
        }
      }
      int ans = 0;
      for (int j = 0; j &lt; N; j++) {
        if (shortest[j] &lt;= T &amp;&amp; shortest[j] != -1) {
          ans++;
        }
      }
      out.println(ans);
    }
    out.close();
    sc.close();
  }

  @SuppressWarnings(&quot;unchecked&quot;)
  private static Object[] dfs(Node[] graph, int j, int e) {
    PriorityQueue&lt;Object[]&gt; queue = new PriorityQueue&lt;Object[]&gt;(1, new Comparator&lt;Object[]&gt;() {
      @Override
      public int compare(Object[] o1, Object[] o2) {
        return Integer.compare((int) o1[2], (int) o2[2]);
      }
    });
    queue.add(new Object[] { graph[j], new ArrayList&lt;Integer&gt;(), 0 });
    while (!queue.isEmpty()) {
      Object[] next = queue.poll();
      Node n = ((Node) next[0]);
      ((ArrayList&lt;Integer&gt;) next[1]).add(n.idx);
      n.visited = true;
      if (n.idx == e) {
        return new Object[] { next[1], next[2] };
      } else {
        for (Integer in : n.cost.keySet()) {
          if (!graph[in].visited) {
            ArrayList&lt;Integer&gt; tmp = new ArrayList&lt;Integer&gt;();
            tmp.addAll((ArrayList&lt;Integer&gt;) next[1]);
            queue.add(new Object[] { graph[in], tmp, (int) next[2] + n.cost.get(in) });
          }
        }
      }
    }
    return null;
  }

  private static class Node {
    boolean visited;
    int idx;
    HashMap&lt;Integer, Integer&gt; cost;

    public Node(int idx) {
      this.idx = idx;
      cost = new HashMap&lt;Integer, Integer&gt;();
    }

    public void add(Node n, int cost) {
      if (this.cost.containsKey(n.idx)) {
        int tmp = this.cost.get(n);
        this.cost.put(n.idx, Math.min(tmp, cost));
      } else {
        this.cost.put(n.idx, cost);
      }
    }
  }

}

UVA 10141 – Request for Proposal

Meh, missed edge case of an RFP having NO requirements at all. Other than that pretty easy problem. Could have done it without using a heap and keeping track of some variables but I used one anyways.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

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

    boolean first = true;
    int test = 1;
    String line = null;
    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line);
      int N = Integer.parseInt(st.nextToken());
      int P = Integer.parseInt(st.nextToken());
      if (N == 0 && P == 0)
        break;
      if (!first)
        out.println();
      ArrayList<String> requirements = new ArrayList<String>();
      for (int i = 0; i < N; i++) {
        requirements.add(br.readLine());
      }

      PriorityQueue<Offer> heap = new PriorityQueue<Offer>(P, new Comparator<Offer>() {
        @Override
        public int compare(Offer arg0, Offer arg1) {
          if (arg0.compliance == arg1.compliance) {
            if (arg0.price == arg1.price) {
              return Integer.compare(arg0.idx, arg1.idx);
            } else {
              return Double.compare(arg0.price, arg1.price);
            }
          } else {
            return Double.compare(arg1.compliance, arg0.compliance);
          }
        }
      });

      for (int i = 0; i < P; i++) {
        String name = br.readLine();
        st = new StringTokenizer(br.readLine());
        double price = Double.parseDouble(st.nextToken());
        int offer = Integer.parseInt(st.nextToken());
        int count = 0;
        for (int j = 0; j < offer; j++) {
          br.readLine();
          count++;
        }
        heap.add(new Offer(name, price, count, i));
      }
      out.println("RFP #" + test);
      out.println(heap.poll().name);
      test++;
      first = false;
    }

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

  private static class Offer {
    int idx;
    String name;
    double price;
    double compliance;

    public Offer(String name, double price, double compliance, int idx) {
      this.name = name;
      this.price = price;
      this.compliance = compliance;
      this.idx = idx;
    }
  }

}

UVA 661 – Blowing Fuses

Blank line after every case. :[

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

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

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

    int count = 1;
    while (sc.hasNextInt()) {

      int N = sc.nextInt();
      int M = sc.nextInt();
      int C = sc.nextInt();

      if (N == 0)
        break;

      long[] power = new long[N];
      for (int i = 0; i < N; i++)
        power[i] = sc.nextInt();

      boolean[] on = new boolean[N];
      long current = 0;
      long max = 0;
      for (int i = 0; i < M; i++) {
        int tmp = sc.nextInt() - 1;
        if (on[tmp]) {
          on[tmp] = false;
          current -= power[tmp];
        } else {
          on[tmp] = true;
          current += power[tmp];
          max = Math.max(max, current);
        }
      }

      out.println("Sequence " + count);
      if (max > C) {
        out.println("Fuse was blown.");
      } else {
        out.println("Fuse was not blown.");
        out.println("Maximal power consumption was " + max + " amperes.");
      }
      out.println();
      count++;
    }

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

}

UVA 573 – The Snail

Those boundary cases! :[ This was an important problem. Must solve!

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

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

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

    while (sc.hasNextInt()) {
      double H = sc.nextInt();
      double U = sc.nextInt();
      double D = sc.nextInt();
      double F = sc.nextInt();
      if (H == 0)
        break;

      double decrease = U * (F * 1.0 / 100);
      double current = 0;
      boolean first = true;
      int day = 0;
      while (current <= H && (first || current >= 0)) {
        day++;
        current += U;
        if (current > H)
          break;
        current -= D;
        U -= decrease;
        U = Math.max(U, 0);
        first = false;
      }
      if (current <= 0) {
        out.println("failure on day " + day);
      } else {
        out.println("success on day " + day);
      }
      out.flush();
    }

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

UVA 119 – Greedy Gift Givers

Pretty simple.

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

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

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

    boolean first = true;
    while (sc.hasNextInt()) {
      if (!first)
        out.println();
      int N = sc.nextInt();
      String[] friends = new String[N];
      HashMap<String, Integer> map = new HashMap<String, Integer>();
      for (int i = 0; i < N; i++) {
        friends[i] = sc.next();
        map.put(friends[i], i);
      }
      int[] moneys = new int[N];
      for (int i = 0; i < N; i++) {
        int idx = map.get(sc.next());
        int gift = sc.nextInt();
        int M = sc.nextInt();
        if (M > 0) {
          moneys[idx] -= gift;
          if (gift != 0 && gift % M != 0) {
            int t = gift % M;
            moneys[idx] += t;
            gift -= t;
          }
          for (int j = 0; j < M; j++) {
            moneys[map.get(sc.next())] += gift / M;
          }
        }
      }
      for (int i = 0; i < N; i++) {
        out.println(friends[i] + " " + moneys[i]);
      }
      first = false;
    }
    out.close();
    sc.close();
  }

}

UVA 12554 – A Special “Happy Birthday” Song!!!

Interesting problem that is testing my while loop condition writing skills!

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

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

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

    String[] song = { "Happy", "birthday", "to", "you", "Happy", "birthday", "to", "you", "Happy", "birthday", "to", "Rujia", "Happy", "birthday", "to", "you" };

    int N = sc.nextInt();
    String[] people = new String[N];
    for (int i = 0; i < N; i++) {
      people[i] = sc.next();
    }

    boolean done = false;
    int idxSong = 0;
    int idxPeople = 0;
    while (!done || idxSong != 0) {
      out.println(people[idxPeople] + ": " + song[idxSong]);
      idxPeople++;
      idxSong++;
      if (idxPeople == N) {
        done = true;
        idxPeople = 0;
      }
      if (idxSong == song.length)
        idxSong = 0;
    }

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

UVA 12503 – Robot Instructions

Simple input parsing. Easy.

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

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

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

    int T = sc.nextInt();
    for (int i = 0; i < T; i++) {
      int N = sc.nextInt();
      int[] moves = new int[N];
      int ans = 0;
      for (int j = 0; j < N; j++) {
        String input = sc.next();
        if (input.equals("LEFT")) {
          moves[j] = -1;
        } else if (input.equals("RIGHT")) {
          moves[j] = 1;
        } else {
          sc.next();
          moves[j] = moves[sc.nextInt() - 1];
        }
        ans += moves[j];
      }
      out.println(ans);
    }

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

}