Thank you guys, now I understand the solution. The tutorial says that we must find a rectangle with 4 of its cornors are 1, and I really don't know what the heck 1 is =))

Care cái sỏi

I can't understand D's solution. Can anybody explain more clearly?

My idea in problem D is: Take an arbitary silo u and check the total danger of all possible S which are adjacent to u.

Let deg[u] be the number of silos which has a passage to u. Consider an arbitary passage (u,v) which has danger c. Assume that (u,v) appears in S, then the total danger increases by c. So we must find out how many times (u,v) appears, which is equals to how many S which contains (u,v). We must choose (k-1) other silos from the set of the other (deg[u]-1) silos, so it would be C(deg[u]-1,k-1).

Every passage from u appears exactly C(deg[u]-1,k-1) times, so let s[u] be the sum of the danger of all passages from u. The total danger of all possible S adjacent to u is: s[u]*C(deg[u]-1,k-1).

Then, the answer of the problem is: (s[1]*C(deg[1]-1,k-1)+s[2]*C(deg[2]-1,k-1])+...) / C(n,k) (C(n,k) is the number of all S possible)

The problem here is: how to handle the C(n,k), which should be huge?

I use Extended in Pascal and /C(n,k) by every s[u]*C(deg[u]-1,k-1). It's easy to see that C(deg[u]-1,k-1)/C(n,k)=k/(n-k+1)*(deg[u]-1-0)/(n-0)*(deg[u]-1-1)/(n-1)*...

It's not very precise and I got WA on test 21:

Output

1999999999

Answer

2000000000

Anybody has an idea how to handle this? Coding big number would be too complicated.

care?