TopCoder problem "Cannibals" used in SRM 305 (Division II Level Three)



Problem Statement

    

M missionaries and C cannibals want to cross a river using a rowboat that can carry at most R people at a time. Everybody starts out on one side of the river, and they all want to end with everybody on the other side of the river. Although the cannibals and missionaries are friends and are trying to cooperate, if the cannibals ever outnumber the missionaries on either side of the river, or in the rowboat, they will succumb to temptation and eat the poor souls. Given M, C, and R, you are to return the smallest number of river crossings needed to get everyone safely to the other side of the river. If it is impossible to get everyone safely across the river, return -1.

Each trip from one side of the river to the other counts as one crossing, so a round trip would count as two river crossings. Also, each crossing requires at least one person in the boat to row. Finally, note that, whenever the boat reaches shore, everybody in the boat temporarily disembarks for the purposes of determining whether the cannibals outnumber the missionaries on that side of the river.

As an example, consider the classic version of this puzzle, where you start with 3 missionaries, 3 cannibals, and a rowboat that can hold up to 2 people. For the first crossing, you must send at least two people, because if you sent only one person, that person would have to immediately bring the rowboat back. If you send two missionaries, the remaining missionary gets eaten by the cannibals. You could safely send two cannibals and have one bring the boat back. Alternatively, you could send one missionary and one cannibal, and then have the missionary bring the boat back (because if the cannibal brought the boat back, the two missionaries on the original side of the river would be eaten). Either way, after two crossings, you have one cannibal on the opposite side of the river.

 

Definition

    
Class:Cannibals
Method:minCrossings
Parameters:int, int, int
Returns:int
Method signature:int minCrossings(int M, int C, int R)
(be sure your method is public)
    
 

Constraints

-M, C, and R will be between 2 and 100, inclusive.
-C will not be greater than M.
 

Examples

0)
    
3
3
2
Returns: 11
One way for everybody to cross in 11 crossings is as follows:
  • Two cannibals cross; one cannibal comes back.
  • Two cannibals cross; one cannibal comes back.
  • Two missionaries cross; one missionary and one cannibal comes back.
  • Two missionaries cross; one cannibal comes back.
  • Two cannibals cross; one cannibal comes back.
  • Two cannibals cross.
1)
    
4
4
2
Returns: -1
It is impossible for everybody to cross safely.
2)
    
10
8
3
Returns: 17
3)
    
100
100
20
Returns: 21
4)
    
100
99
2
Returns: 395

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6410

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9826&pm=6410

Writer:

vorthys

Testers:

PabloGilberto , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Search