Google Code Jam 2004予選

もしかして、もうGoogle Code Jamは始まってますか？

もう疲労限界maxなので寝てから明日の昼とかでいいでつか？

「でつか」の「でつ」の部分がスヌーピーに見えるのでつけど、
スヌーピーかよ！って突っ込んでもらっていいでつか？

やっぱり人様の手を煩わせるのも何なので、自分で突っ込んでおきます

　　　　でつ　＜　スヌーピーかよ！

締め切り時間になったので1000ptsの問題こぴぺ。

Your company is working on a new transmission for a high-performance vehicle.

The transmission will have two sets of gears, a front set and a back set.

The numbers of teeth on each of the front gears has already been set,

but now you need to figure out how many teeth to put on all of the back gears.

It has already been decided that there will be cnt back gears.

If the front set of gears contains N gears, then there are a total of N*cnt

gear ratios. Each gear ratio is determined by the ratio of the number of

teeth on one of the front gears divided by the number of teeth on one of

the back gears. Your task is to determine how many teeth to put on each

of the cnt back gears in such a way that the largest gear has max teeth,

and the smallest gear has min teeth. Furthermore, if all of the possible

gear ratios from your assignment are sorted, you want the maximum difference

between two adjacent ratios in the sorted list to be as small as possible.

You are to return the largest difference between adjacent ratios in this

sorted list.
Definition

    

Class:

Transmission

Method:

gears

Parameters:

vector , int, int, int

Returns:

double

Method signature:

double gears(vector  front, int min, int max, int cnt)

(be sure your method is public)

    
Notes

-

Each gear must have an integral number of teeth.

Constraints

-

cnt will be between 3 and 5, inclusive.

-

min will be between 5 and 100, inclusive.

-

max will be between min+cnt-1 and 100, inclusive.

-

front will contain between 1 and 5 elements, inclusive.

-

Each element of front will be between 5 and 100, inclusive.

Examples

0)
    

{10,50,10}

5

20

3

Returns: 3.75

The best we can do here is to make the back 3 gears have 5, 8 and 20 teeth.

This gives the following list of ratios: {0.50, 1.25, 2.00, 2.50, 6.25, 10.00}

The biggest gap is between 10 and 6.25, so we return 3.75.

1)
    

{10,80}

10

50

5

Returns: 1.7333333333333334
2)
    

{5,9,30,100}

10

100

5

Returns: 1.904761904761905