There is a m wild, Nuke, (M ≤ N) can sit on the C person. 1. C = 1, no solution; 2. C = 2, to the smaller M, N, for larger M, N ingredient, such as M = N = 4, c = 2 unexpension; 3. C = 3, the situation is the same; 4. c> 3, discussion is as follows: (1) m = n, at this time, it can be designed according to the following scheme (below SAVAGE, R represents the monks Religious, b means the boat Boat , || Represents River) Solution 1:
M s || (MC) S || CS (M-C 1) s || (C-1) S (M-C 1) s || (C-1) S (M-C 2) S || (C-2) SM R || => M r || => M r || => (M-C 1) R || (C-1) R => (M-C 2 ) R || (c-2) RB || || B b || || B b ||
So returned to the beginning of the beginning, S, R equal on both sides and the boat on the left bank, and there was already C-2 S and C-2 R passing the river. In order to do it, all people will cross the river; there is also a solution: Solution 2: MS || (M- [C / 2]) s || [C / 2] S (M- [C / 2] 1) s || ([C / 2] -1) SMR || => (M- [C / 2]) R || [C / 2] r => (M- [C / 2] 1) R || ([C / 2] -1) R b || || B B || will eventually go to both sides of strait S, R, and the ship is on the left bank, there is [C / 2] -1 S and R Have a river. When c is an even number, the river speed of the scheme one and the program second is the same; when C is an odd number, the plan is faster than the scheme. When m = N, some special cases need to be considered: a. K ≥ M N, let everyone cross the river once; b. K ≥ M, with the above scheme one;
(2) N> M, 1N = m 1, and less than one of the following situations: (a) c is an even number, the scheme is as follows:
third solution:
MS || (MC) S || CS (M-C 1) s || (C-1) S (M-C 1) s || (C-1) S (M-C 1) S || (C-1) SNR || => nr || => nr || => (nc) r || CR => (N-C 1) r || (C-1) R b || || B B || || B B ||
Let M '= M-C 1, N' = N-C 1, the case of n '= m' 1 is repeated; (b) c is an odd number, set C = 2H 1, obviously A The plan is also available, and there is also the following protocol:
Program four
MS || (MH) S || HS (MH) S || HS NR || => (NH-1) r || (H 1) R => (NH) R || HR B || || B b ||
Let M '= M-H, N' = N-H, and returns to N '= m' 1. Follow this scheme each h in H 1 R cross the river, then 1 R is back.
When C is an odd number, the river speed of the two programs of A and B.
2N ≥ M 2: (a) C is an odd number, can use n = m 1 case four.
(b) C is an even number, set C = 2h, you can pass each time H-1 S, H 1 R, then come back to a R, each double H, H r, h back, back Specifically, as shown below: Scenary 5:
MS || (M-H 1) s || (H-1) S (M-H 1) s || (H-1) S (M-2H 1) s || (2H-1) S (M-2H 1) s || (2H-1) SNR || => (NH-1) R || (H 1) R => (NH) r || hr => (N-2H ) R || 2hr => (N-2H 1) r || (2H-1) R b || || B b || || B b ||
Let M '= M-2H 1, N' = N-2H 1, repeat the above process.
The integration of algorithm design is that people who cross the river as much as possible, people come back as little as possible, when n> m, C≥2 is always known.
The above algorithms have been very clear, and you should be able to write it yourself.
This problem is the topic of the NOI rematch, the topic is not difficult, but it should be aware of the discussion.
