2008年9月26日

623 - 500!

UVa網站題目連結
My Solved Problems Performance

In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm.

As an examples we can give programs which calculate primary numbers.

One can also imagine a program which calculates a factorial of given numbers. In this case it is the time complexity of order O(n) which makes troubles, but the memory requirements. Considering the fact that 500! gives 1135-digit number no standard, neither integer nor floating, data type is applicable here.

Your task is to write a programs which calculates a factorial of a given number.

Assumptions: Value of a number ``n" which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a small limit).

Input

Any number of lines, each containing value ``n" for which you should provide value of n!

Output

2 lines for each input case. First should contain value ``n" followed by character `!'. The second should contain calculated value n!.

Sample Input

`103050100`

Sample Output

`10!362880030!26525285981219105863630848000000050!30414093201713378043612608166064768844377641568960512000000000000100!93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000`

Solution

`import java.io.BufferedInputStream;import java.math.BigInteger;import java.util.Scanner;public class Main {    static int size = 1001;    static Scanner in = new Scanner(new BufferedInputStream(System.in));    static BigInteger[] bigIntArray = new BigInteger[size];    static int input;    public static void main(String[] args) {        bigIntArray[0] = BigInteger.ONE;        bigIntArray[1] = BigInteger.ONE;        for (int i=2; i<size; i++) {            bigIntArray[i] = bigIntArray[i-1].multiply(new BigInteger(String.                             valueOf(i)));        }        while (in.hasNext()) {            input = in.nextInt();            System.out.println(input+"!");            System.out.println(bigIntArray[input]);        }    }}`

326 - Extrapolation Using a Difference Table

UVa網站題目連結
My Solved Problems Performance

A very old technique for extrapolating a sequence of values is based on the use of a difference table. The difference table used in the extrapolation of a sequence of 4 values, say 3, 6, 10, and 15, might be displayed as follows:

The original sequence of values appears in the first column of the table. Each entry in the second column of the table is formed by computing the difference between the adjacent entries in the first column. These values (in the second column) are called first differences. Each entry in the third column is similarly the difference between the adjacent entries in the second column; the third column entries are naturally called second differences. Computation of the last column in this example should now be obvious (but beware that this value is not always zero). Note that the last column will always contain only a single value. If we begin with a sequence of n values, the completed difference table will have n columns, with the single value in column n representing the single n-1st difference.

To extrapolate using a difference table we assume the n-1st differences are constant (since we have no additional information to refute that assumption). Given that assumption, we can compute the next entry in the n-2nd difference column, the n-3rd difference column, and so forth until we compute the next entry in the first column which, of course, is the next value in the sequence. The table below shows the four additional entries (in boxes) added to the table to compute the next entry in the example sequence, which in this case is 21. We could obviously continue this extraolation process as far as desired by adding additional entries to the columns using the assumption that the n-1st differences are constant.

Input and Output

The input for this problem will be a set of extraolation requests. For each request the input will contain first an integer n, which specifies the number of values in the sequence to be extended. When n is zero your program should terminate. If n is non-zero (it will never be larger than 10), it will be followed by n integers representing the given elements in the sequence. The last item in the input for each extrapolation request is k, the number of extrapolation operations to perform; it will always be at least 1. In effect, you are to add k entries to each column of the difference table, finally reporting the last value of the sequence computed by such extrapolation. More precisely, assume the first n entries (the given values) in the sequence are numbered 1 through n.

Your program is to determine the n+kth value in the sequence by extrapolation of the original sequence k times.

Hint: no upper limit is given for k, and you might not be able to acquire enough memory to construct a complete difference table.

Sample Input

`4 3 6 10 15 14 3 6 10 15 23 2 4 6 206 3 9 12 5 18 -4 100`

Sample Output

`Term 5 of the sequence is 21Term 6 of the sequence is 28Term 23 of the sequence is 46Term 16 of the sequence is -319268`

Solution

`import java.io.BufferedInputStream;import java.util.Scanner;import java.util.Vector; public class Main {     static Scanner in = new Scanner(new BufferedInputStream(System.in));    static int n, k;    static Vector<Vector<Integer>> int2DArray = new Vector<Vector<Integer>>();     public static void main(String[] args) {         while ((n=in.nextInt())!=0) {             int2DArray = new Vector<Vector<Integer>>();            for (int i=0; i<n; i++) {                int2DArray.add(new Vector<Integer>());            }            for (int i=0; i<n; i++) {                int2DArray.elementAt(0).add(i, in.nextInt());            }            k = in.nextInt();            for (int i=1; i<n; i++) {                for (int j=0; j<n-i; j++) {                    int2DArray.elementAt(i).add(j, int2DArray.elementAt(i-1).                                         elementAt(j+1)-int2DArray.elementAt(i-1)                                         .elementAt(j));                }            }             for (int i=0; i<k; i++) {                for (int j=n-1; j>=0; j--) {                    if (j!=n-1) {                        int2DArray.elementAt(j).add(int2DArray.elementAt(j).                                             lastElement()+int2DArray.elementAt(                                             j+1).lastElement());                    } else {                        int2DArray.elementAt(j).add(int2DArray.elementAt(j).                                             lastElement());                    }                }            }            System.out.println("Term " + (n+k) + " of the sequence is " +                               int2DArray.elementAt(0).lastElement());        }    }}`

324 - Factorial Frequencies

In an attempt to bolster her sagging palm-reading business, Madam Phoenix has decided to offer several numerological treats to her customers. She has been able to convince them that the frequency of occurrence of the digits in the decimal representation of factorials bear witness to their futures. Unlike palm-reading, however, she can't just conjure up these frequencies, so she has employed you to determine these values.

Recall that the definition of n! (that is, n factorial) is just . As she expects to use either the day of the week, the day of the month, or the day of the year as the value of n, you must be able to determine the number of occurrences of each decimal digit in numbers as large as 366 factorial (366!), which has 781 digits.

Input and Output

The input data for the program is simply a list of integers for which the digit counts are desired. All of these input values will be less than or equal to 366 and greater than 0, except for the last integer, which will be zero. Don't bother to process this zero value; just stop your program at that point. The output format isn't too critical, but you should make your program produce results that look similar to those shown below.

Madam Phoenix will be forever (or longer) in your debt; she might even give you a trip if you do your job well!

`381000`

Sample Output

`3! --(0)    0    (1)    0    (2)    0    (3)    0    (4)    0(5)    0    (6)    1    (7)    0    (8)    0    (9)    08! --(0)    2    (1)    0    (2)    1    (3)    1    (4)    1(5)    0    (6)    0    (7)    0    (8)    0    (9)    0100! --(0)   30    (1)   15    (2)   19    (3)   10    (4)   10(5)   14    (6)   19    (7)    7    (8)   14    (9)   20`

Solution

`import java.io.BufferedInputStream;import java.math.BigInteger;import java.util.Scanner; public class Main {     static Scanner in = new Scanner(new BufferedInputStream(System.in));    static int input, temp;    static int[] intArray = new int[10];    static BigInteger bigInt = new BigInteger("1");    static BigInteger[] bigIntArray = new BigInteger[367];     public static void main(String[] args) {        bigIntArray[0] = new BigInteger("0");        bigIntArray[1] = new BigInteger("1");        for (int i=2; i<367; i++) {            bigIntArray[i] = bigIntArray[i-1].multiply(new BigInteger(                             String.valueOf(i)));        }         while ((input=in.nextInt())!=0) {            process(input);        }    }     private static void process(int input) {        for (int i=0; i<intArray.length; i++) {            intArray[i]=0;        }        bigInt = bigIntArray[input];        while (bigInt.compareTo(BigInteger.ZERO)>0) {            temp = bigInt.divideAndRemainder(BigInteger.TEN)[1].intValue();            bigInt = bigInt.divide(BigInteger.TEN);            intArray[temp]++;        }        System.out.println(input+"! --");        System.out.println("   (0)   "+intArray[0]+"   (1)   "+intArray[1]+                           "   (2)   "+intArray[2]+"   (3)   "+intArray[3]+                           "   (4)   "+intArray[4]);        System.out.println("   (5)   "+intArray[5]+"   (6)   "+intArray[6]+                           "   (7)   "+intArray[7]+"   (8)   "+intArray[8]+                           "   (9)   "+intArray[9]);    }}`

305 - Joseph

UVa網站題目連結
My Solved Problems Performance

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, ..., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

`340`

`530`

Solution

`import java.io.BufferedInputStream;import java.util.Scanner;public class Main {    static Scanner in = new Scanner(new BufferedInputStream(System.in));    static int k, m, p, now, kill;    public static void main (String[] args) {        while ((k=in.nextInt())!=0) {            Joseph(k);        }    }    private static void Joseph(int k) {        p = 2*k;        now = 1;        m = 2;        while (p > k) {            kill = (now+m-1)%p;            if ((kill<=k)&&(kill!=0)) {                p = 2*k;                m++;                now = 1;            } else {                now = (kill==0) ? 1 : kill;                p--;            }        }        System.out.println(m);    }}`

136 - Ugly Numbers

UVa網站題目連結
My Solved Problems Performance

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

Input and Output

There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.

Solution

`public class Main {    public static void main (String[] args) {        int size = 1500;        int counter = 1;        int result = 0;        for (int i=2; counter<size; i++) {            int x = i;            while ((x%5==0)) {                x/=5;            };            while ((x%3==0)) {                x/=3;            };            while ((x%2==0)) {                x/=2;            };            if (x==1) {                counter++;            }            if (counter == size) result = i;        }        System.out.println("The 1500'th ugly number is " + result + ".");        // The 1500'th ugly number is 859963392.    }}`

2008年9月25日

102 - Ecological Bin Packing

UVa網站題目連結
My Solved Problems Performance

Background

Bin packing, or the placement of objects of certain weights into different bins subject to certain constraints, is an historically interesting problem. Some bin packing problems are NP-complete but are amenable to dynamic programming solutions or to approximately optimal heuristic solutions.

In this problem you will be solving a bin packing problem that deals with recycling glass.

The Problem

Recycling glass requires that the glass be separated by color into one of three categories: brown glass, green glass, and clear glass. In this problem you will be given three recycling bins, each containing a specified number of brown, green and clear bottles. In order to be recycled, the bottles will need to be moved so that each bin contains bottles of only one color.

The problem is to minimize the number of bottles that are moved. You may assume that the only problem is to minimize the number of movements between boxes.

For the purposes of this problem, each bin has infinite capacity and the only constraint is moving the bottles so that each bin contains bottles of a single color. The total number of bottles will never exceed 2^31.

The Input

The input consists of a series of lines with each line containing 9 integers. The first three integers on a line represent the number of brown, green, and clear bottles (respectively) in bin number 1, the second three represent the number of brown, green and clear bottles (respectively) in bin number 2, and the last three integers represent the number of brown, green, and clear bottles (respectively) in bin number 3. For example, the line 10 15 20 30 12 8 15 8 31

indicates that there are 20 clear bottles in bin 1, 12 green bottles in bin 2, and 15 brown bottles in bin 3.

Integers on a line will be separated by one or more spaces. Your program should process all lines in the input file.

The Output

For each line of input there will be one line of output indicating what color bottles go in what bin to minimize the number of bottle movements. You should also print the minimum number of bottle movements.

The output should consist of a string of the three upper case characters 'G', 'B', 'C' (representing the colors green, brown, and clear) representing the color associated with each bin.

The first character of the string represents the color associated with the first bin, the second character of the string represents the color associated with the second bin, and the third character represents the color associated with the third bin.

The integer indicating the minimum number of bottle movements should follow the string.

If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.

Sample Input

`1 2 3 4 5 6 7 8 95 10 5 20 10 5 10 20 10`

Sample Output

`BCG 30CBG 50`

Solution

`import java.io.BufferedInputStream;import java.util.Scanner;public class Main {    static String sArray[] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};    static int iArray[] = new int[6];    static int inArray[] = new int[9];    static Scanner in = new Scanner(new BufferedInputStream(System.in));    public static void main (String[] args) {        while (in.hasNext()) {            process();        }    }    private static void process() {        int total = 0;        for (int i=0; i<9; i++) {            inArray[i] = in.nextInt();            total += inArray[i];        }        iArray[0] = total - inArray[0] - inArray[5]  - inArray[7];        iArray[1] = total - inArray[0] - inArray[4]  - inArray[8];        iArray[2] = total - inArray[2] - inArray[3]  - inArray[7];        iArray[3] = total - inArray[2] - inArray[4]  - inArray[6];        iArray[4] = total - inArray[1] - inArray[3]  - inArray[8];        iArray[5] = total - inArray[1] - inArray[5]  - inArray[6];        int min = iArray[0];        int result = 0;        for (int i=1; i<6; i++) {            if (min > iArray[i]) {                min = iArray[i];                result = i;            }        }        System.out.println(sArray[result] + " " + iArray[result]);    }}`

100 - The 3n + 1 problem

UVa網站題目連結
My Solved Problems Performance

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

` 1.   input n 2.   print n 3.   if n = 1 then STOP 4.      if n is odd then   5.      else   6.   GOTO 2`

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

`1 10100 200201 210900 1000`

Sample Output

`1 10 20100 200 125201 210 89900 1000 174`

Solution

`import java.io.BufferedInputStream;import java.util.Scanner;public class Main {    public static void main (String[] args) {        int in1, in2, x, min, max, counter = 0, counterMax = 0;        Scanner in = new Scanner(new BufferedInputStream(System.in));        while (in.hasNext()) {            in1 = in.nextInt();            in2 = in.nextInt();            if (in1 > in2) {                max=in1;                min=in2;            } else {                max=in2;                min=in1;            }            counterMax = 0;            for (x=min; min<=max; min++) {                x = min;                for (counter = 1; x!=1; counter++) {                    if ((x&1)==1) x=3*x+1;                    else x>>=1;                }                if (counter>counterMax)counterMax =counter;            }            System.out.println(in1 + " " + in2 + " " + counterMax);        }    }}`

320x250

420x250