OJ Board

It also can be solved using binary search + Floyd.

I think you binary search for the mean value, but can you explain how you use floyd warshall to test if a cycle with this mean (or less) exists?

Well, I know about Karp's algo (see Cormen) but I solved it using Floyd only!
Here is my idea:
I ...

Ok, I give up
Do you know some greedy that works?

FAQ wrote:Please help me some I/O please? I still got WA

Be sure you handle cases with muliple edges from a to b correctly.

Test:

1
3 5
1 2 1
2 3 5
3 1 1
3 1 5
2 3 1

Answer:
Case #1: 1.00

It also can be solved using binary search + Floyd.

Among all pairs with minimum sum of values I always take the one with minimum first element. So my code passes your test case.

I solved it in O(n) as follows:

1. Starting from any station (let's call it START) and trying to finish the lap. If it's possible then goto print answer, else let's say I couldn't get from p to p+1.

2. Starting from p+1 and trying to finish lap. (I don't need to look for the path starting from ...

I solved it using both DP and greedy.

Greedy is as follows:
1. Take one guy with maximum value
2. Take two appropriate guys with minimum sum of values

However, I have not proved it.

i used smth. like this:

mask - bit state
need - remainder to get
n - number of 1's in mask


...
map <pair<int,int>,int> m;

int solve(int mask, int need, int n){
int res=m[make_pair(mask,need)];
if (res>0) return res-1;

// here comes actual solution

m[make_pair(mask,need)]=res+1;
return ...

tywok wrote:but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!

You can do memorization using STL's map.

Problem can be solved without maximum matching.
Just think about bipartite graph and it's connected
components.

Edit: example of useless of maximum matching:

1
8 7
0 5
1 5
2 5
3 5
1 4
1 6
1 7

answer should be 4, but MM=2

Yes, it can be solved in O(n*k)

Hint:
Let c[n][k] is the answer.
Try to find reccursion like

c[n][k] = Function(c[n-1][k],c[n-1][k-1])

You can ignore "bad" random points and wait for a "good" one.

2100000056 67333

answer should be

982...016

your program get
983...016

...

see my third post at this topic

It's because of overflow

Replace
with
or

in the main program use instead of

Try to replace your part:

temp1 = temp1 - temp2 + 4.0;
temp3 = pow(10.0, temp1);
sprintf(buf1, "%.0Lf", temp3);


with this:


temp1 = temp1 - temp2;
temp3 = pow(10.0, temp1);
while (temp3<1000.0) temp3 *= 10.0;
int tmp = floor(temp3);
while (tmp>999) tmp /= 10;
sprintf(buf1, "%d ...