Category Archives: Competitive Programming 3

UVA 11764 – Jumping Mario

Super simple linear scan.

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

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

	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 = 1; i <= T; i++) {
			int N = sc.nextInt();
			int high = 0;
			int low = 0;
			int last = sc.nextInt();
			for (int j = 1; j < N; j++) {
				int t = sc.nextInt();
				if (t < last) {
					low++;
				} else if (t > last) {
					high++;
				}
				last = t;
			}
			out.println("Case " + i + ": " + high + " " + low);
		}

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

}

UVA 11679 – Sub-prime

I was doing this wayy too complicatedly before using an ArrayList and a counter to see if I could greedily find the appropriate match or not. The easiest way I realized mid coding process was to just let the transactions go through and then check at the end if everyone ends up with a positive or 0 balance.

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

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		while (sc.hasNextInt()) {
			int B = sc.nextInt();
			int N = sc.nextInt();
			if (B == N && B == 0)
				break;
			
			int[] reserves = new int[B];
			for (int i = 0; i < reserves.length; i++)
				reserves[i] = sc.nextInt();

			for (int i = 0; i < N; i++) {
				int from = sc.nextInt() - 1;
				int to = sc.nextInt() - 1;
				int amt = sc.nextInt();
				reserves[from] -= amt;
				reserves[to] += amt;
			}

			if (isCool(reserves)) {
				out.println("S");
			} else {
				out.println("N");
			}
		}
		out.close();
		sc.close();
	}

	private static boolean isCool(int[] reserves) {
		for (int i = 0; i < reserves.length; i++) {
			if (reserves[i] < 0)
				return false;
		}
		return true;
	}

}

UVA 11559 – Event Planning

This was fun. First program so far for which I used an extra class. Easy problem. 8)

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

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

		while (sc.hasNextInt()) {
			int N = sc.nextInt();
			int B = sc.nextInt();
			int H = sc.nextInt();
			int W = sc.nextInt();

			Hotel[] hotels = new Hotel[H];
			for (int i = 0; i < H; i++) {
				hotels[i] = new Hotel();
				hotels[i].price = sc.nextInt();
				for (int j = 0; j < W; j++) {
					hotels[i].maxBeds = Math.max(hotels[i].maxBeds,
							sc.nextInt());
				}
			}
			Arrays.sort(hotels);
			boolean found = false;
			for (int i = 0; i < H; i++) {
				if (hotels[i].price * N <= B && hotels[i].maxBeds >= N) {
					out.println(hotels[i].price * N);
					found = true;
					break;
				}
			}
			if (!found)
				out.println("stay home");
		}
		out.close();
		sc.close();
	}

	private static class Hotel implements Comparable<Hotel> {
		int price;
		int maxBeds;

		@Override
		public int compareTo(Hotel o2) {
			if (this.price == o2.price) {
				return Integer.compare(o2.maxBeds, this.maxBeds);
			} else {
				return Integer.compare(this.price, o2.price);
			}
		}
	}

}

UVA 11332 – Summing Digits

Yay recursion!

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

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

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

		while (true) {
			long x = sc.nextLong();
			if (x == 0)
				break;
			out.println(solve(x));
		}

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

	private static long solve(long x) {
		if (x < 10)
			return x;

		long sum = 0;
		while (x > 0) {
			sum += x % 10;
			x /= 10;
		}

		return solve(sum);
	}

}

UVA 10963 – The Swallowing Ground

Really really simple problem. Need to remember not to make incorrect assumptions. Problem gets easily solved once you use absolute values and you read the question again which tells you to print a blank line between outputs. :[

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

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

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

		int W = sc.nextInt();
		for (int i = 0; i < W; i++) {
			int C = sc.nextInt();
			boolean bad = false;
			int last = Math.abs(sc.nextInt() - sc.nextInt());
			for (int j = 1; j < C; j++) {
				int tmp = Math.abs(sc.nextInt() - sc.nextInt());
				if (last != tmp)
					bad = true;
			}
			if (bad) {
				out.println("no");
			} else {
				out.println("yes");
			}
			if (i < W-1)
				out.println();
		}

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

}

UVA 10300 – Ecological Premium

This was super easy. No need for doubles like I had initially thought.

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

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

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

		int N = sc.nextInt();
		while (N > 0) {
			int f = sc.nextInt();
			long ans = 0;
			for (int i = 0; i < f; i++) {
				int sizeOfFarm = sc.nextInt();
				sc.nextInt();
				int eco = sc.nextInt();
				ans += sizeOfFarm * eco;
			}
			out.println(ans);
			N--;
		}

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

}

UVA 10114 – Loansome Car Buyer

This problem was truly annoying and yet extremely simple at the same time. This has been ever so rightly starred in Competitive Programming 3 book. I messed up with an edge case and I wrote `break` instead of `continue` (big oops) in one of my many submissions. The problem mentions that we need to use files as input and output but that is not the case! That lost me a couple of tries as well :[

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

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

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

		while (true) {
			int duration = sc.nextInt();
			double downpayment = sc.nextDouble();
			double loan = sc.nextDouble();
			int depreciations = sc.nextInt();
			if (duration < 0) {
				break;
			}
			double valOfCar = loan + downpayment;
			double monthlyPayment = loan / duration;

			int[] depList = new int[depreciations];
			double[] depVal = new double[depreciations];
			for (int i = 0; i < depreciations; i++) {
				depList[i] = sc.nextInt();
				depVal[i] = sc.nextDouble();
			}

			int lastMonth = 0;
			double lastVal = depVal[0];

			valOfCar *= (1 - lastVal);

			if (loan < valOfCar) {
				out.println("0 months");
				continue;
			}

			lastMonth = 1;

			for (int i = 1; i < depList.length; i++) {
				int nextMonth = depList[i];
				double nextMonthDepreciation = depVal[i];
				while (lastMonth <= nextMonth) {
					if (nextMonth == lastMonth) {
						lastVal = nextMonthDepreciation;
					}
					valOfCar *= (1 - lastVal);
					loan -= monthlyPayment;
					lastMonth++;
					if (loan < valOfCar) {
						break;
					}
				}
				if (loan < valOfCar) {
					break;
				}
			}
			while (loan > valOfCar) {
				valOfCar *= (1 - lastVal);
				loan -= monthlyPayment;
				lastMonth++;
			}

			lastMonth--;
			if (lastMonth == 1) {
				out.println("1 month");
			} else {
				out.println(lastMonth + " months");
			}
		}
		out.close();
		sc.close();
	}

}

UVA 621 – Secret Research

This was a particularly annoying question. Mainly because the answer choices don’t have an option for ‘Don’t know’. This would ofcourse make the problem much harder (comparitively) but the question allows for inputs such as 190435 which are unclassifiable. I just assumed simple input and my solution worked, so that’s that I suppose.

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

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int T = sc.nextInt();
    while (T > 0) {
      String input = sc.next();
      if (input.endsWith("35")) {
    	  out.println("-");
      } else if (input.startsWith("190")) {
    	  out.println("?");
      } else if (input.equals("1") || input.equals("4") || input.equals("78")) {
    	  out.println("+");
      } else {
    	  out.println("*");
      }
      T--;
    }
    out.close();
    sc.close();
  }

}

UVA 12577 – Hajj-e-Akbar

Really, really long question.

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

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    String line;
    int count = 1;
    while ((line = sc.next()) != null) {
      if (line.trim().equals(&quot;*&quot;))
        break;
      out.print(&quot;Case &quot; + count + &quot;: &quot;);
      if (line.equals(&quot;Hajj&quot;)) {
        out.println(&quot;Hajj-e-Akbar&quot;);
      } else {
        out.println(&quot;Hajj-e-Asghar&quot;);
      }
      count++;
    }
    out.close();
    sc.close();
  }

}

UVA 12403 – Save Setu

Simple .equals() with an if statement.

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

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

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    int T = sc.nextInt();
    int count = 0;
    while (T > 0) {
      if (sc.next().equals("donate")) {
        count += sc.nextInt();
      } else {
        out.println(count);
      }
      T--;
    }
    out.close();
    sc.close();
  }

}