首页 > ACM题库 > HDU-杭电 > Hdu 1183 Not magic,but logic. 待解决 [解题报告] C++
2013
12-03

Hdu 1183 Not magic,but logic. 待解决 [解题报告] C++

Not magic,but logic.

问题描述 :

He(Harry) pulled open the next door, both of them hardly daring to look at what came next – but there was nothing very frightening in here, just a table with seven differently shaped bottles standing on it in a line.
‘Snape’s,’ said Harry. ‘What do we have to do?’
They stepped over the threshold and immediately a fire sprang up beind them in the doorway. It wasn’t ordinary fire either; it was purple. At the same instant, black flames shot up in the doorway leading onwards.They were trapped.
‘Look!’ Hermione seized a roll of paper lying next to the bottles. Harry looked over her shoulder to read it:

Danger lies before you, while safety lies behind,

Two of us will help you, whichever you would find,

One among us seven will let you move ahead,

Another will transport the drinker back instead,

Some among our number hold only nettle wine,

And others are killers, waiting hidden in line.

Choose, unless you wish to stay here for evermore,

To help you in your choice, we give you these clues:

Now,they must make a choice, could you help them?
However, we call the bottle who can take you ahead A,and the bottle who can take you back is named B.

输入:

The first line of the input is three integer N,M,P. It means there is N bottles of wine, M bottles of poison and P clues.(0<=N,M<=100,0<P<=1000)
Next P line would be one of these four:

No. i from left/right is safe/dangrous .
All wine/poison have a wine/poison on the left/right .
The A/B have a wine/poison/A/B on the left and a wine/poison/A/B on the right .
No. i from left/right cannot take you back/ahead .

输出:

Output will have only one line:
If you are sure where A and B is, just tell Harry their number from left.
If you aren’t sure, you only can say: ‘God help them.’
If you find that’s impossible, just say: ‘That’s impossible.’

样例输入:

2 4 6 
All wine have a poison on the left . 
The B have a poison on the left and a poison on the right . 
The A have a wine on the left and a poison on the right . 
No. 4 from right is safe . 
No. 4 from left is safe . 
No. 2 from right cannot take you back .

样例输出:

5 2

Hint
Both PBPWAPPW and PBPWAPWP are possible solutions,where 'P' means poison and 'W' means wine.But however,we know where A and B are.


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?