z-most

any hints for this:D
i guess its DP

well, I solved this task using dp but I see that there are few backtrack solutions that pass in time...

About dp..
Your state should be something like: "What friends already crossed the bridge ?"

You can define this state with one number,
where looking in binary representation 1 on i-th place represent that i-th friend crossed the bridge and 0 on i-th place represent that i-th friend didn't cross the bridge.

well i know that but what do u check?every 2^n combinations?

for i:=0 to ( 1 shl n ) - 1 do . . .

yes, you check every 2^n combination...

I mean... for final state you will need some other states, which you need to calculate the same way you calculated final state...

for example u calculate the possibility of 1,2,3 guys crossing and then i do what?for all the rest i generate all possibilites again?like all possibilites of 4,5,6...n crossing somehow?

hmmm....

well, i didn't understand what you said but here is idea:

let dp[A] detonate minimal amount of time needed for friends where is 1 in binary representation of A to cross the bridge

then we know that dp[0] = 0 ( no one crossed the bridge )...
and we are looking for dp[2^m - 1]...

and now let's just take an example for m = 3

dp[0] = 0, and we are looking for dp[111] ( I'll write numbers in binary representation here )

to state [111] we can come from:
if ( weight of first < N )
// we can come from state 011
// we try to update current state
dp[111] = min( dp[111], dp[011] + time of first friend to cross the bridge )

if ( weight of second < N )
// we can come from state 101
// we try to update current state
dp[111] = min( dp[111], dp[101] + time of second friend to cross the bridge )

if ( weight of third < N )
// we can come from state 110
// we try to update current state
dp[111] = min( dp[111], dp[110] + time of third friend to cross the bridge )

if ( weight of first + weight of second < N )
// we can come from state 001
// we try to update current state
dp[111] = min( dp[111], dp[001] + max( time of first friend to cross the bridge, time of second friend to cross the bridge ) )

if ( weight of first + weight of third < N )
// we can come from state 010
// we try to update current state
dp[111] = min( dp[111], dp[010] + max( time of first friend to cross the bridge, time of third friend to cross the bridge ) )

if ( weight of second + weight of third < N )
// we can come from state 100
// we try to update current state
dp[111] = min( dp[111], dp[100] + max( time of second friend to cross the bridge, time of third friend to cross the bridge ) )

if ( weight of first + weight of second + weight of third < N )
// we can come from state 000
// we try to update current state
dp[111] = min( dp[111], dp[000] + max( time of first friend to cross the bridge, time of second friend to cross the bridge, time of third friend to cross the bridge ) )

those are all states from which we can come to state 111...

if current state is 110 we can come to that state from states: 100, 010, 000

if current state is 010 we can come to that state only from state 000

I hope this was readable and understandable :D

it is,thanks:D
whats the time coplexity of this?
i need to find for 2^n cases the best time

O( 3^m )...

here is the explanation:

to every state i = 1 .. 2 ^ M you can come from 2 ^ ( number of 1's in binary representation of i ) states ...

and now... look at this 2 ^ ( number of 1's in binary representation of i ) ...

how many number <= 2 ^ m have k 1's in it's binary representation ?
\binom{m}{k}

so you are looking for: \sum_{k=1}^m \binom{m}{k} * 2^k which is (2 + 1)^m

hmm for m=5 u need to check for instance the possibility of 00111...and 00111 can come from 2^3 possibilitiess so for every 2^n u have to check 2^(the number of 1 in that possibility)

that is what I've written up there :D

ok was checking if i understood well:D