OJ Board

How do you find the interval to search next?

JP.

Sorry for confusing you,
I wrote that "inc = 1" means 1 degree ( PI/180 ), not 1.

for the interval, I choice a middle point, and add/sub a range to form the new one.
In the begining, mid = PI/4.0, range = PI/4.0, interval will be ( 0, PI/2.0 ...

hujialie wrote:Hi,Even.

Thank you for your reply.
I have changed 1000 into 2000,but still got Wrong Answer.
Do you think my algorithm is OK?

mm... you should treat capital one and lowercase letter as different

It means that if( word[0][j] != temp[j] ) diff++

Hello, hujialie

try to declare more large, such as word[2000][2000]

Hello, LA-Z-BOy

the case you give will not happen.
you can read the problem description one more time.

Thanks for your answer. Sorry :oops: I got mixed up with the inputs. I add two more for cheking a possible overflow, they are:

INPUT:
1000000000
10000000001

OUTPUT:
400000000
1600000000

second one
9897840000

10000000001 = 101 x 3541 x 27961

Actually, the problem describes that n ...

You have 23 input, but 25 ouput??

btw, the first 23 ouput is correct

I've thinked a lot trying to find a way to do this problem without caring about the number of words, but I couldn't find any.

I coded with mallocs ... no problems with that, and I made a dfs to find the solution. It's ok , but I got TLE .

I optimized it with a matrix pre calculating the ...

The description of this problem include: The number of words are unlimited! But I don't know how many words there are in one case at most.

One method, you can use malloc, because first line of each case will tell you how many words and how long of each word.

But, since the problem descript that ...

Maybe you can try this

Input

5 5

Output

5 divides 5!

987654321 = 3^2 x 17^2 x 379721

it has three prime factors 3, 17, 379721

your prime table only up to 32000.

in this case, you lost the last one prime 379721

and your answer become

987654321 * ( 1-1/3 ) * ( 1-1/17 ) = 619704672

and the correct answer is

987654321 * ( 1-1/3 ) * ( 1-1/17 ) * (1 ...

Thanks for your reply. I have inserted the code for these cases, but I still get wrong answer.
Can someone tell me the output for:
4
5 5 5 0.1 6.42
5 5 5 0.1 5.998
5 5 5 0.0005 10
20 -24 6 25 -30
My program prints:
0.100
0.001
0.000
1.810


My program ( AC ) output ...

0.100
0.001
0.001
1.810 ...

I just wonder that if 'Same' occurs ...how to express area ? 0.00 ?

and after 'Same' ... all cases should be 0.00 ... right ?

plz.. give me more test case, thx

The largest rectangle is simply infinitely large.
I think your proposition need some more definitions.
Maybe you want to put the constraints on the rectangle that should
have at least a certain number of points on the boundary or something else...I don't know


hmm...only one constrain ... fit ...

thank Ivan Golubev and Adrian Kuegel...

I starts form theta = 0, inc = 1 to searching for the smallest rectangle.
Then decreasing inc to inc/10, searching in smaller interval...
repeat ...10 times ... WA ... 11 times ... AC :)

thank you all ....

and If I wanna search the "largest" rectangle ...

is there always one side of input polygon be the same side of the smallest rectangle ? I'm not sure about this. My accepted solution computes convex hull and then rotates it from 0 to pi/2 to find smallest possible rectangle.

mm.. I rotate it from -PI~PI using rotation matrix, inc theta by PI ...

hello Ivan...

is there always one side of input polygon be the same side of the smallest rectangle ?

I always consider one side of convex ( form by input )
be one side of the smallest rectangle ...but WA... ><