Category Archives: Competitive Programming 3

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

}

UVA 12468 – Zapping

Just do it in two cases. Where a < b and where b < a. [java] import java.io.PrintWriter; import java.util.Scanner; /** * * @author Sanchit M. Bhatnagar * @see http://uhunt.felix-halim.net/id/74004 * */ public class P12468 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); while (sc.hasNextInt()) { int a = sc.nextInt(); int b = sc.nextInt(); if (a == -1) break; if (b < a) { out.println(Math.min(a - b, 100 - a + b)); } else { out.println(Math.min(b - a, 100 - b + a)); } out.flush(); } out.close(); sc.close(); } } [/java]

UVA 12157 – Tariff Plan

I had initially accidentally written “Case #1” instead of “Case 1” :[

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

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

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

    int T = sc.nextInt();
    for (int zz = 1; zz <= T; zz++) {
      int N = sc.nextInt();
      int mileCost = 0;
      int juiceCost = 0;
      for (int i = 0; i < N; i++) {
        int talkTime = sc.nextInt();
        mileCost += (int) Math.ceil(talkTime / 30.0) * 10;
        if (talkTime % 30 == 0)
          mileCost += 10;
        juiceCost += (int) Math.ceil(talkTime / 60.0) * 15;
        if (talkTime % 60 == 0)
          juiceCost += 15;
      }
      out.print("Case " + zz + ": ");
      if (mileCost < juiceCost) {
        out.println("Mile " + mileCost);
      } else if (juiceCost < mileCost) {
        out.println("Juice " + juiceCost);
      } else {
        out.println("Mile Juice " + mileCost);
      }
    }

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

UVA 12015 – Google is Feeling Lucky

Simple!

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

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

    ArrayList<String> ans;
    int N = sc.nextInt();
    for (int i = 1; i <= N; i++) {
      int max = -1;
      ans = new ArrayList<String>();
      for (int j = 0; j < 10; j++) {
        String tmp = sc.next();
        int val = sc.nextInt();
        if (val > max) {
          ans.clear();
          ans.add(tmp);
          max = val;
        } else if (val == max) {
          ans.add(tmp);
        }
      }
      out.println("Case #" + i + ":");
      for (String t : ans) {
        out.println(t);
      }
    }

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

UVA 11942 – Lumberjack Sequencing

Two linear scans to figure out if its ascending or descending. If one of them works then Ordered else Unordered.

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

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int N = sc.nextInt();
    out.println("Lumberjacks:");
    for (int i = 0; i < N; i++) {
      int[] arr = new int[10];
      for (int j = 0; j < 10; j++)
        arr[j] = sc.nextInt();

      int bad = 0;
      for (int j = 1; j < 10; j++) {
        if (arr[j - 1] > arr[j]) {
          bad++;
          break;
        }

      }

      for (int j = 1; j < 10; j++) {
        if (arr[j - 1] < arr[j]) {
          bad++;
          break;
        }
      }

      if (bad == 1) {
        out.println("Ordered");
      } else {
        out.println("Unordered");
      }
    }

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

}

UVA 11799 – Horror Dash

Clowns must run at (Math.max)imum speed! :D

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

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

		int N = Integer.parseInt(br.readLine());
		for (int i = 1; i &lt;= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int ans = 0;
			while (st.hasMoreTokens()) {
				ans = Math.max(ans, Integer.parseInt(st.nextToken()));
			}
			out.println(&quot;Case &quot; + i + &quot;: &quot; + ans);
		}
		out.close();
		br.close();
	}
}