The Bridge problem (uva 10037) is one of the tricky and interesting problem in programming challenge from competitive programming. Which can be stated as (from online judge)
There are n number of persons (entered by user) standing on one side of the bridge. Only two persons can cross the bridge at a time and they have only one torch common in all. Thus, we have to find sequence of peoples such that overall time taken is minimum.
The person is denoted by time required by that person to cross bridge (e.g if person named 1, then it takes 1 unit of time to cross bridge). If 1 and 5 cross bridge then time taken to cross bridge will be 5 since max time is considered.
Our goal is to cross all persons at another side of bridge. Since only two persons at a time can cross bridge and they have only one torch, thus one should have to return to give torch to other peoples.
If you observe all the possible method, there are two methods found to be at minimum time, Consider A, B, C, D as four persons (lowest to highest i.e A requires min time and D requires max time).
1) A and B go, A return, C and D go, B return, then A and B go.
2) A and B go, A return, A and C go, A return, A and D go.
if we consider time required to cross bridge in both cases, we get two equations as,
1) B+A+D+B+B
2) B+A+C+A+D
After removing common terms from both equations we obtain
2B and A+C as two equations. Now we check among those equations which has lower value, and proceed that way.
Sample Input
1
4
1
2
5
10
Sample Output
17
1 2
1
5 10
2
1 2
Explanation
The first line of input contains n, followed by n lines giving the crossing times for each of the people. We have to calculate the min time consuming method and print result in order of total time taken, sequence of peoples crossing bridge.
Code
def Bridge(l1, size):
Obt = str()
TIME = 0
while(1):
A = l1[0]
if(size==1):
Obt += str(A)
TIME += A
break
B = l1[1]
if(size==2):
Obt += str(A) +" "+ str(B)
TIME += B
break
if(size==3):
Obt += str(A) +" "+ str(B) +"\n"+ str(A) +"\n"+ str(A) +" "+ str(l1[2])
TIME += B+A+l1[2]
break
Z = l1[size-1]
Y = l1[size-2]
if(A+Y < (2*B)): #due to C(A,C)+A+D(A,D)+A
Obt += str(A)+" "+str(Z)+"\n"+str(A)+"\n"+str(A)+" "+str(Y)+"\n"+str(A)+"\n"
TIME += Z+A+Y+A
else: #due to B(A,B)+A+D(C,D)+B
Obt += str(A)+" "+str(B)+"\n"+str(A)+"\n"+str(Y)+" "+str(Z)+"\n"+str(B)+"\n"
TIME += B+A+Z+B
l1.remove(Y)
l1.remove(Z)
size = len(l1)
print("\n",TIME,"\n",Obt)
loop = int(input())
print("\n\n")
for i in range(0, loop):
size = int(input())
l = []
for i in range(0, size):
l.append(int(input()))
l.sort()
Bridge(l, size)
First, we sort the list of peoples and assign A as 0th index (lowest value) and Z as n-1th index (highest value). Then we simply substitute values in our equation and find out which method takes less time. After that, just print the result, thats it.
Hope, this article found helpful to you. Thank you.
Related keywords: the bridge, bridge uva, bridge problem, bridge online judge, bridge solution, bridge explanation, bridge problem source code, bridge problem programming challenge, bridge python, uva 10037, uva 10037 source code, uva 10037 solution, uva 10037 explanation.
Comments
Post a Comment