Wednesday, February 8, 2012

UVa_10154_Weights_and_Measures.java

Problem Links:

uva10154,

Problem:


Problem F: Weights and Measures

I know, up on top you are seeing great sights,
But down at the bottom, we, too, should have rights.
We turtles can't stand it. Our shells will all crack!
Besides, we need food. We are starving!" groaned Mack.

The Problem

Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the five thousand, six hundred and seven turtles ordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.
Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams. The strength, also in grams, is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are at most 5,607 turtles.
Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input

300 1000
1000 1200
200 600
100 101

Sample Output

3



Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Using Dynamic Programming;
 * dp[i][j] represents: get the minimum weight of choosing j turtles from first
 * ith turtles;
 * 
 * For this problem, the list requires to be sorted first, let the turtle with
 * max-weight and min-weight located at the last.
 */

/**
 * @author antonio081014
 * @since Feb 3, 2012, 6:30:30 PM
 */
class Main {
    public List<Turtle> list;

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.init();
        System.out.println(main.solve());
    }

    public void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        list = new ArrayList<Turtle>();
        String strLine;
        while ((strLine = br.readLine()) != null) {
            String[] str = strLine.split(" ");
            int w = Integer.parseInt(str[0]);
            int s = Integer.parseInt(str[1]) - w;
            list.add(new Turtle(w, s));
        }
    }

    public int solve() {
        Collections.sort(list);
        // for (int i = 0; i < list.size(); i++)
        // System.out
        // .println(list.get(i).weight + ", " + list.get(i).strength);
        int N = list.size();
        int[][] dp = new int[N][N + 1];
        for (int i = 0; i < N; i++)
            for (int j = 0; j <= N; j++)
                dp[i][j] = (j == 0 ? 0 : Integer.MAX_VALUE);
        dp[0][1] = list.get(0).weight;
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= i + 1; j++) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
                if (list.get(i).strength > dp[i - 1][j - 1]) {
                    dp[i][j] = Math.min(dp[i][j],
                            dp[i - 1][j - 1] + list.get(i).weight);
                }
            }
        }
        for (int i = N; i >= 0; i--)
            if (dp[N - 1][i] != Integer.MAX_VALUE)
                return i;
        return 0;
    }
}

class Turtle implements Comparable<Turtle> {
    public int weight;
    public int strength;

    public Turtle(int w, int s) {
        this.weight = w;
        this.strength = s;
    }

    @Override
    public int compareTo(Turtle o) {
        if (this.strength == o.strength)
            return this.weight - o.weight;
        return (this.strength) - (o.strength);
    }
}

Friday, February 3, 2012

UVa_10066_The_Twin_Towers.java

Problem Links:

uva10066,

Problem:


Problem B
The Twin Towers
Input: standard input
Output: standard output

Once upon a time, in an ancient Empire, there were two towers of dissimilar shapes in two different cities. The towers were built by putting circular tiles one upon another. Each of the tiles was of the same height and had integral radius. It is no wonder that though the two towers were of dissimilar shape, they had many tiles in common.
However, more than thousand years after they were built, the Emperor ordered his architects to remove some of the tiles from the two towers so that they have exactly the same shape and size, and at the same time remain as high as possible. The order of the tiles in the new towers must remain the same as they were in the original towers. The Emperor thought that, in this way the two towers might be able to stand as the symbol of harmony and equality between the two cities. He decided to name them the Twin Towers.
Now, about two thousand years later, you are challenged with an even simpler problem: given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.


Input
The input file consists of several data blocks. Each data block describes a pair of towers.
The first line of a data block contains two integers N1 and N2 (1 <= N1, N2 <= 100) indicating the number of tiles respectively in the two towers. The next line contains N1 positive integers giving the radii of the tiles (from top to bottom) in the first tower. Then follows another line containing N2 integers giving the radii of the tiles (from top to bottom) in the second tower.
The input file terminates with two zeros for N1 and N2.

Output
For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.

Sample Input
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output
Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6



Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Classic Longest Common Subsequence problem.
 * Problem: UVA 10066.
 */

/**
 * @author antonio081014
 * @since Feb 3, 2012, 3:08:02 PM
 */
class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strLine;
        int ncase = 0;
        while ((strLine = br.readLine()) != null) {
            ncase++;
            String[] str = strLine.split(" ");
            int N = Integer.parseInt(str[0]);
            int M = Integer.parseInt(str[1]);
            if (N == 0 && M == 0)
                break;
            String[] strsA = br.readLine().split(" ");
            String[] strsB = br.readLine().split(" ");

            int[][] dp = new int[N + 1][M + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (strsA[i - 1].compareTo(strsB[j - 1]) == 0) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    }
                    else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            System.out.println("Twin Towers #" + Integer.toString(ncase));
            System.out.println("Number of Tiles : " + dp[N][M]);
            System.out.println();
        }

    }
}