any implementation suggestions? breadth first search, kruskal's?
from what i understand is that i need to build a tree
and each node will have 10 freakin' children (number of combinations on 3 passengar boat).
blarrrrrg
any tips/hints would be greatly appreciated.
----------------------------------------
PART B. Programming part. [100]
In the alien world of Faloutsonia, there is a river,
and the creatures cross this river daily.
The only way to cross is a boat with a guard
and the boat has 3 positions for passengers.
There are two species that cross the river:
the Xerons and the Omons.
The Xerons can eat the Omons. (The Omons are vegetarians.)
The guard has to transfer Xerons and Omons across the river with the following rules:
* There must never be more Xerons than Omons in one side of the river without the guard,
because then the Xerons will eat the Omons.
Note: if the guard is present, she can make sure that none gets eaten.
Also, if Omons are equal to or more than the Xerons, then none gets eaten.
* The passengers in the boat can not exceed the boat capacity
However, they can be less than the capacity or even zero.
You can have passengers from either species.
While on the boat, the guard is present, so none gets eaten.
The fees: Every time the boat crosses the river the guard has to pay taxes to evil Michalorg, supreme ruler of Faloutsonia.
The tarif is as follows:
* empty boat: C_e dollars (they are alien dollars with an exchange rate of 1:10000 to US$)
* Xeron: C_x dollars per head
* Ommons C_o dollars per head
The cost is additive: for a ride with 1 Xeron and two Omons, the cost is:
C_e + C_x + 2 * C_o
Naturally all costs are non-negative (positive or zero).
Every morning, the guard has to transport X Xerons, and O Omons,
from the A side of the river to the B side of the river
without anybody getting eaten and with the minimum cost in taxes.
You are friends with the guard and you want to write a C++ program to help
him find safe and least costly way of boat rides (sum of taxes payed should be minimum).
The input of the program is the number of Xerons, X, the number of Omons, O and the costs
C_e , C_x, C_o. Everybody is on the A side of the river.
The output should be:
a. [10] if there is a way to transfer everybody across (Print Yes or No).
b. [10] the minimum number of times that the boat has to cross the river
(total crossings in either direction).
c. [30] the exact sequence of states and moves of a safe for all trip.
The required output is like this:
A -> B: X_a O_a move 1, 1
B -> A: X_a-1 O_a - 1 move 1, 0
where X_a O_a is the number of creatures on side A
before you put anyone in the boat,
and "move 1, 1" means that you intend to move one Xeron and one Omon
from the X_a and O_a.
In the second line, "move 1 0" means that you intend to move 1 Xeron from B to A.
from what i understand is that i need to build a tree
and each node will have 10 freakin' children (number of combinations on 3 passengar boat).
blarrrrrg
any tips/hints would be greatly appreciated.
----------------------------------------
PART B. Programming part. [100]
In the alien world of Faloutsonia, there is a river,
and the creatures cross this river daily.
The only way to cross is a boat with a guard
and the boat has 3 positions for passengers.
There are two species that cross the river:
the Xerons and the Omons.
The Xerons can eat the Omons. (The Omons are vegetarians.)
The guard has to transfer Xerons and Omons across the river with the following rules:
* There must never be more Xerons than Omons in one side of the river without the guard,
because then the Xerons will eat the Omons.
Note: if the guard is present, she can make sure that none gets eaten.
Also, if Omons are equal to or more than the Xerons, then none gets eaten.
* The passengers in the boat can not exceed the boat capacity
However, they can be less than the capacity or even zero.
You can have passengers from either species.
While on the boat, the guard is present, so none gets eaten.
The fees: Every time the boat crosses the river the guard has to pay taxes to evil Michalorg, supreme ruler of Faloutsonia.
The tarif is as follows:
* empty boat: C_e dollars (they are alien dollars with an exchange rate of 1:10000 to US$)
* Xeron: C_x dollars per head
* Ommons C_o dollars per head
The cost is additive: for a ride with 1 Xeron and two Omons, the cost is:
C_e + C_x + 2 * C_o
Naturally all costs are non-negative (positive or zero).
Every morning, the guard has to transport X Xerons, and O Omons,
from the A side of the river to the B side of the river
without anybody getting eaten and with the minimum cost in taxes.
You are friends with the guard and you want to write a C++ program to help
him find safe and least costly way of boat rides (sum of taxes payed should be minimum).
The input of the program is the number of Xerons, X, the number of Omons, O and the costs
C_e , C_x, C_o. Everybody is on the A side of the river.
The output should be:
a. [10] if there is a way to transfer everybody across (Print Yes or No).
b. [10] the minimum number of times that the boat has to cross the river
(total crossings in either direction).
c. [30] the exact sequence of states and moves of a safe for all trip.
The required output is like this:
A -> B: X_a O_a move 1, 1
B -> A: X_a-1 O_a - 1 move 1, 0
where X_a O_a is the number of creatures on side A
before you put anyone in the boat,
and "move 1, 1" means that you intend to move one Xeron and one Omon
from the X_a and O_a.
In the second line, "move 1 0" means that you intend to move 1 Xeron from B to A.
