Single Round Match – edwinwang.com

Problem Statement for ClassScores

Problem Statement

A teacher has just finished grading the test papers for his class. To get an idea of how difficult the test was, he would now like to determine the most common score on the test. In statistics, this is called the "mode" of a set of data points. For instance, if the scores were {65, 70, 88, 70}, then the mode would be 70, since it appears twice while all others appear once.

Sometimes, in the case of a tie, the mode will be more than one number. For instance, if the scores were {88, 70, 65, 70, 88}, then the mode would be {70, 88}, since they both appear most frequently.

You are given a int[] scores. You are to return a int[] representing the mode of the set of scores. In the case of more than one number, they should be returned in increasing order.

Definition

Class:	ClassScores
Method:	findMode
Parameters:	int[]
Returns:	int[]
Method signature:	int[] findMode(int[] scores)
(be sure your method is public)

Constraints

–

scores will contain between 1 and 50 elements, inclusive.

–

Each element of scores will be between 0 and 100, inclusive.

Examples

{65, 70, 88, 70}

Returns: {70 }

The first example from the problem statement.

{88, 70, 65, 70, 88}

Returns: {70, 88 }

The second example from the problem statement.

{92, 56, 14, 73, 22, 38, 93, 45, 55}

Returns: {14, 22, 38, 45, 55, 56, 73, 92, 93 }

With no duplicates, all of the elements are the most frequent (appearing once each).

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2005, TopCoder, Inc. All rights reserved.

public class ClassScores {

public int[] findMode(int[] scores) {

int[] count = new int[101];

for (int i = 0; i < scores.length; i++)

count[scores[i]]++;

for (int i = scores.length; i ≥ 1; i—) {

int c = 0;

for (int j = 0; j ≤ 100; j++)

if (count[j] == i)

c++;

if (c > 0) {

int p = 0;

int[] ret = new int[c];

for (int j = 0; j ≤ 100; j++)

if (count[j] == i) {

ret[p] = j;

p++;

}

return ret;

}

return new int[0];

}

Problem Statement for AutoLoan

Problem Statement

Auto dealerships frequently advertise tempting loan offers in order to make it easier for people to afford the "car of their dreams". A typical sales tactic is to show you various cars, and then talk in terms of what your monthly payment would be, to say nothing of how much you are actually paying for the car, how much interest you pay, or how long you have to make payments.

A typical auto loan is calculated using a fixed interest rate, and is set up so that you make the same monthly payment for a set period of time in order to fully pay off the balance. The balance of your loan starts out as the sticker price of the car. Each month, the monthly interest is added to your balance, and the amount of your payment is subtracted from your balance. (The payment is subtracted after the interest is added.) The monthly interest rate is 1/12 of the yearly interest rate. Thus, if your annual percentage rate is 12%, then 1% of the remaining balance would be charged as interest each month.

You have been checking out some of the cars at your local dealership, TopAuto. An excited salesman has just approached you, shouting about how you can have the car you are looking at for a payment of only monthlyPayment for only loanTerm months! You are to return a double indicating the annual percentage rate of the loan, assuming that the initial balance of the loan is price.

Definition

Class:	AutoLoan
Method:	interestRate
Parameters:	double, double, int
Returns:	double
Method signature:	double interestRate(double price, double monthlyPayment, int loanTerm)
(be sure your method is public)

Notes

–

Because of the way interest is compounded monthly, the actual interest accrued over the course of a year is not necessarily the same as (balance * yearly interest rate). In fact, it's usually more.

–

In a real situation, information like this would typically need to be disclosed, but since you aren't at a point of signing any paperwork, the salesman has no legal obligation to tell you anything.

–

The return value must be within 1e-9 absolute or relative error of the actual result.

Constraints

–

price will be between 1 and 1000000, inclusive.

–

monthlyPayment will be between 0 and price / 2, inclusive.

–

loanTerm will be between 1 and 600, inclusive.

–

The resulting interest rate will be between 0 and 100, inclusive.

Examples

Returns: 1.3322616182218813E-13

Noting that 68 payments of 100 equals the total price of 6800, so there is no interest.

Returns: 9.56205462458368

Here, we do pay a little interest. At 9.562% annual interest, that means each month we pay 0.7968% of the balance in interest. Our payment schedule looks like this:

Month | + Interest | - Payment | = Balance
------------------------------------------
      |            |           |  2000.00
   1  |     15.94  |   510.00  |  1505.94
   2  |     12.00  |   510.00  |  1007.94
   3  |      8.03  |   510.00  |   505.97
   4  |      4.03  |   510.00  |     0.00

Returns: 7.687856394581649

This is similar to what purchasing a new car with no money down might look like, if you make payments for 4 years.

public class AutoLoan {

private double amort(double principal, double payment, int term, double interest) {

double m = interest / 1200;

if (principal * m > payment)

return 1;

for (int i = 0; i < term; i++)

principal = principal * (1 + m) – payment;

return principal;

}

public double interestRate(double price, double monthlyPayment, int loanTerm) {

double ret = 0;

double inc = 1000000000;

while (inc ≥ 1.0E-18) {

double d = amort(price, monthlyPayment, loanTerm, ret + inc);

if (d ≤ 0) {

ret += inc;

}

inc /= 2.0;

}

return ret;

}

Problem Statement for MissileTarget

Problem Statement

You are working for a defense agency that is testing the accuracy of a new missile guidance system. As part of this effort, several missiles have been fired off. Each missile fired was programmed with the same target coordinates, although the actual points of impact vary.

Your task is to determine the "best fit" point to describe the location where the missiles actually landed. To determine how well a point describes the location, calculate the cartesian distance from the point to each of the landing points. Then, total the sum of the squares of these distances. The best fit point is the point that minimizes this sum.

You are given int[]s x and y, both containing the same number of elements, where the i-th element of x and the i-th element of y describe the coordinates of the i-th missile landing point. You are to return a int[] with exactly two elements, describing the coordinates of the lattice point (point with integral coordinates) that is closest to the "best fit" point. The first element should be the x-coordinate, and the second element should be the y-coordinate.

Definition

Class:	MissileTarget
Method:	bestFit
Parameters:	int[], int[]
Returns:	int[]
Method signature:	int[] bestFit(int[] x, int[] y)
(be sure your method is public)

Notes

–

The cartesian distance between two points (x1, y1) and (x2, y2) is defined as Sqrt((x2-x1)^2 + (y2-y1)^2).

–

The return value must be within 1e-9 absolute or relative error of the actual result.

Constraints

–

x will contain between 1 and 50 elements, inclusive.

–

x and y will contain the same number of elements.

–

Each element of x will be between -1000000 and 1000000, inclusive.

–

Each element of y will be between -1000000 and 1000000, inclusive.

–

The actual (possibly non-lattice) best fit point will be at least 1e-2 closer to the correct return value than to any other lattice point.

Examples

{750, -500, -250}

{-1000, 500, 500}

Returns: {0, 0 }

These three impacts are all pretty close to the origin, and sure enough, the origin is the best fit point.

{765}

{834}

Returns: {765, 834 }

With only one point, it is its own best fit.

{100, 200}

{200, 400}

Returns: {150, 300 }

With only two points, the best fit is the midpoint between the two.

{123456, -987654, 97531, -86420}

{14703, 25814, 36924, -47036}

Returns: {-213272, 7601 }

{0, 5, 5, 6, 8, 8}

{0, 0, 0, 0, 0, 0}

Returns: {5, 0 }

In this case, notice that the actual best fit point possible is (5.333, 0). If we look at lattice points only, then our best fit is (6, 0), however, we are interested in the lattice point that is closest to the actual best fit point, so we return (5, 0).

This is another problem that is fairly easily solved with a bit of grunt work to calculate out the desired values. Since we are looking for the lattice point that is closest to our best fit, our best bet is to first calculate the location of the actual best fit point (using floating point, that is), and then find the closest lattice point.

To find the best fit point, we one important observation: calculating the best fit x-coordinate and the best fit y-coordinate separately will give us our best fit point. Why? Since the scoring of a point as being best fit is based upon the sum of the squares of the distances from each of the points, we see that:

score = sum(d^2) = sum(sqrt((x – x0)^2 – (y – y0)^2)^2)
= sum((x – x0)^2 + (y – y0)^2)
= sum((x – x0)^2) + sum((y – y0)^2)

So, to minimize the score, it suffices to minimize each sum separately.

To minimize each sum, a ternary search works well. However, in this case, if you were inclined to do the mathematical gruntwork, then you found a nice shortcut. The average of the x-coordinates will give you the x-coordinate of the best fit point, and the same goes for the y-coordinates. (Why? Hint: Use calculus to prove where the minimum value is.)

Either way, once you have the location of the best fit point it's just simply a matter of finding the closest lattice point, and the easiest way to do this is by rounding. (Note the constraints were intended to prohibit the case where a point was equidistant from multiple lattice points.)

本来想试试昨天的TopCoder(R) Single Round 的的，起得太晚了，没赶上Registration ，哎～～～可惜。。。
贴上题目做做吧

SubstitutionCode Point 250
　Division Two – Level One

Problem Statement for SubstitutionCode

Problem Statement

A simple, easy to remember system for encoding integer amounts can be very useful. For example, dealers at flea markets put the information about an item on a card that they let potential buyers see. They find it advantageous to encode the amount they originally paid for the item on the card.

A good system is to use a substitution code, in which each digit is encoded by a letter. An easy to remember 10-letter word or phrase, the key, is chosen. Every '1' in the value is replaced by the first letter of the key, every '2' is replaced by the second letter of the key, and so on. Every '0' is replaced by the last letter of the key. Letters that do not appear in the key can be inserted anywhere without affecting the value represented by the code.. This helps to make the resulting code much harder to break (without knowing the key).

Create a class SubstitutionCode that contains the method getValue that is given the Strings key and code as input and that returns the decoded value.

Definition

Class:	SubstitutionCode
Method:	getValue
Parameters:	String, String
Returns:	int
Method signature:	int getValue(String key, String code)
(be sure your method is public)

Constraints

–

code contains between 1 and 9 characters inclusive, all uppercase letters 'A'-'Z'

–

code contains at least one letter that is found in key

–

key contains exactly 10 uppercase letters 'A'-'Z', all distinct from each other

Examples

"TRADINGFEW"

"LGXWEV"

Returns: 709

The L,X, and V are ignored since they do not appear in the key. G is the seventh letter in the key, W is the 10th letter, and E is the 9th letter.

"ABCDEFGHIJ"

"XJ"

Returns: 0

"CRYSTALBUM"

"MMA"

Returns: 6

BridgePts Point 500
　Division Two – Level Two

Problem Statement for BridgePts

Problem Statement

A deck of cards contains 52 cards. Each card has a suit (Clubs,Diamonds,Hearts,Spades) and a value (Ace,2,3,…,9,10,Jack,Queen,King). In the game of bridge a hand consists of 13 cards from the deck.

A player needs to evaluate his hand, giving it a point value. The standard method is as follows: count 4 points for each Ace, 3 points for each King, 2 points for each Queen, and 1 point for each Jack. For each suit, count 1 point if the hand contains exactly two cards of that suit, 2 points if exactly one card, and 3 points if the hand contains no cards of that suit. The point value of the hand is the sum of all these points.

Create a class BridgePts that contains a method pointValue that is given a int[] hand and that returns the point value of the hand.

Each element of hand indicates a card. The clubs are numbered 1 to 13, the diamonds are 14 to 26, the hearts are numbered 27 to 39, and the spades are numbered 40 to 52. Within each suit, the cards are numbered in the order Ace, 2, 3, …, 9, 10, Jack, Queen, King. So, for example, the King of Hearts is numbered 39 and the Ace of Spades is numbered 40.

Definition

Class:	BridgePts
Method:	pointValue
Parameters:	int[]
Returns:	int
Method signature:	int pointValue(int[] hand)
(be sure your method is public)

Constraints

–

hand will contain exactly 13 elements, all distinct.

–

Each element of hand will have a value between 1 and 52 inclusive.

Examples

{25,14,15,16,17,18,19,20,21,22,23,24,26}

Returns: 19

This hand contains all diamonds, so it has one Ace, one King, one Queeen, and one Jack, and it contains no cards in three suits. So its point value is 4 + 3 + 2 + 1 + 3 + 3 + 3 = 19.

{2,3,4,15,18,28,29,30,41,42,43,16,17}

Returns: 0

This hand contains only 2's, 3's, 4's and one 5. It has 3 or 4 cards in each suit.

TimeCard Point 1000
　Division Two – Level Three

Problem Statement for TimeCard

Problem Statement

When I start my shift at work I punch in my starting time, and when I leave I punch out. The times are printed on a card using exactly 8 characters in the format

           hh:mm,xx

where hh is the 2 digit representation of the hour, mm is the 2 digit representation of the minute, and xx is either am or pm. The ':' and ',' are literal. "12:00,am" denotes midnight, while "12:00,pm" denotes noon.

The difference between that time I punch in and the time I punch out is the amount of time I have worked so, for example, if I punch in at 03:33pm and punch out at 03:34pm I have worked 1 minute.

No shift is allowed to be more than 20 hours long. This is my last shift of the week and I am supposed to work 40 hours during the week. Create a class TimeCard that contains a method leave that is given a String[] time of all the times on this week's timecard and that returns a String (using the same format) that tells when I can leave and have exactly 40 hours for the week. Return "BELOW 40" or "ABOVE 40" if it is not possible to get exactly 40 hours. In all cases, the return should contain exactly 8 characters.

The elements of time alternate: punch in time, punch out time, punch in time, … with the final element being the time I just punched in on my final shift.

Definition

Class:	TimeCard
Method:	leave
Parameters:	String[]
Returns:	String
Method signature:	String leave(String[] time)
(be sure your method is public)

Constraints

–

time will contain an odd number of elements between 1 and 49 inclusive.

–

Each element of time will be formatted as above.

–

In each element of time hh will be between 01 and 12 inclusive.

–

In each element of time mm will be between 00 and 59 inclusive.

–

time will contain no shift that exceeds 20 hours in duration.

Examples

{"03:00,pm"}

Returns: "BELOW 40"

This is my one and only shift, and I am only allowed to work 20 hours on a shift.

{"09:00,am","05:00,pm","09:00,am","05:00,pm",
    "09:00,am","05:00,pm","09:00,am","05:00,pm","09:00,am"}

Returns: "05:00,pm"

I have worked 4 previous shifts of 8 hours, so I need 8 hours on this shift to make 40.

{"12:00,am","08:00,pm","12:00,am","08:00,pm","12:00,am"}

Returns: "12:00,am"

I have already worked 2 shifts of 20 hours so I already have exactly 40 hours. I should go home immediately.

{"12:00,pm","08:00,pm","12:00,am","08:00,pm","12:00,am"}

Returns: "12:00,pm"

{"09:00,am","04:31,pm","09:00,am","04:31,pm",
     "09:00,am","05:00,pm","09:00,am","05:00,pm","03:53,am"}

Returns: "12:51,pm"