The solution to this problem is straightforward. We can enumerate the elements in the given order, and store every one of them in an appropriate array. For instance, we can adopt four arrays A, B, C and D, which represent "rat", "woman and child", "man" and "captain", respectively. For each element, we just put it into the correct array and finally we output the elements stored in the arrays in the order of A, B, C and D.
We can simulate the process of training and count the number of coins that we need to meet the requirement. We can adopt a hash table H[n] to represent the number of people belonging to different ranks. For instance, H[i] denotes the number of people belonging to rank i. Then, we scan the hash table H[n] from k-1 to 1, and as the problem claims, whenever we find that H[i]>0, we just decrease H[i] by 1 while increasing H[i+1] by 1. The above operations should be repeated until we find that H[k]=n is satisfied, and the number of loops is just the answer.
At first, we enumerate all the integers from 0 (in fact this is 0000) to 9999, inclusively. For each enumeration, if all the four digits are different, then it can be viewed as a reasonable integer that is selected by the thinker. Given such an integer, for each guessed number, we can directly calculate the number of digits that give both correct values and positions, and the number of digits that only give correct values but incorrect positions as well. Then, we compare these results with the number of "bulls" and "cows". If they are exactly the same for all the guessed numbers, it means that the integer in the current enumeration can serve as a correct "data". After all the enumeration has been completed, if the number of correct "data" is larger than 1, it means that we "Need more data"; if the number of correct "data" is exactly equal to 1, it means that the "data" is enough and we can just output this correct "data"; if the number of "data" is equal to 0, it means that the thinker must have made a mistake and we should output "Incorrect data".
For problem like this one, we can fill the grids like a snake. If a is an even number, we can start from the upper left corner and go down first to fill the first column, and then we reach the bottom of the second column and go up to fill the second column, and so on. If a is an odd number, we should start from the bottom left corner and go up first to fill the first column, and then we arrive at the top of the second column and go down to fill the second column, and so on. With the above operations, it can be seen that we can "safely" switch from the last column of "b*a square" to the first column of "d*c square".
I think this is really a nice problem to practice the bit-mask technique, and be familiar with the transition among different states, which has also been frequently used in bit-mask Dynamic Programming technique. I think it mainly contains the following steps:
1) Given M positions, we usually use "1" to denote that some position has been taken while "0" to denote that the position is NULL. Therefore, the total number of states should be (1<<M)=2^M. If M<32, it suffices to use an "int" to cover all the potential states, since the binary form of "int" just consists of "0" or "1". For instance, for an integer i=5 with binary form of i=(101), it means that the first and third position have been taken while the other ones are NULL. Alternatively, one can also use the most significant bit to denote the first position.
2) For each state S, it can transit to another state T by implementing some "move". In general, we still use an "int" to denote the "move", as done in step 1). However, for many problems (not all), a reasonable "move" should satisfy the following condition
(S & move) == move
This constraint implies that we can only take away "1" at state S rather than "0", since "0" means NULL and there is nothing can be taken. For instance, S=(101), thus move=(100) is reasonable however move=(110) is not.
3) With a reasonable move, another state T can be reached by T= (S ^ move). (S ^ move) in fact achieves the effect that some "1"s at state S have been taken by the "move". For instance, S=(101), move=(100), and thus we have T= S ^ move=(001).
4) In general, we can enumerate all the states from 0 to (1<<M)-1, inclusively, or from (1<<M)-1 to 0, according to the problem. For each enumeration, we generate all the possible "move" and only select the reasonable ones to obtain the next states that can be transited to. For instance, for this problem we are taking away "1" from some state S, and thus we can start the enumeration from 0 to (1<<M)-1. The state S=0 is initialized to be "losing state". Note that for each state S during the enumeration, (S ^ move)< S always holds. Thus, the next states that S can transit to have been already determined to result in "winning state" or "losing state", and the current state S can be determined as well.
Comments (0)
