jzoj 1591. 【普及模拟】游戏

发布于 2019-03-22  980 次阅读

 

题目描述

两个核武器科学家Patrick和Roland，在研究核武器时突然觉得无聊，玩起了游戏，游戏当然也是跟核武器有关，游戏一开始在桌子上放了一些核材料，两个人轮流玩，Patrick先玩。游戏规则是每次玩家可以从这些核材料里选一些材料放到反应堆去，当然结果就是化为乌有，由于游戏太危险，所以只有A,B,C,D四种材料，而且允许的反应只有以下5种：

1.       AABDD

2.       ABCD

3.       CCD

4.       BBB

5.       AD

当某个人选不到材料进行反应时就输了，大家要知道两个人都是绝顶聪明的。

 

输入

第一行输入一个整数N(1<=N<=100)，表示游戏次数，接下来N行，每行四个整数，分别表示游戏开始时A,B,C,D四种材料的数量。假设一开始每种材料的数量都在0到60之间。

输出

    对于每次游戏输出赢者的名字。

记忆化搜索，要用函数来实现，每次标记，不然会超时

 

const
  w:array[1..5,1..4] of integer=((2,1,0,2),(1,1,1,1),(0,0,2,1),(0,3,0,0),(1,0,0,1));
var
  f:array[0..60,0..60,0..60,0..60] of longint;
  i,j,k,n,m,s,a,b,c,d:longint;

function dfs(a,b,c,d:longint):longint;
var
  i,j,k:longint;
begin
  if f[a,b,c,d]<>0 then exit(f[a,b,c,d]);
  for i:=1 to 5 do
    begin
      if (a>=w[i,1]) and (b>=w[i,2]) and (c>=w[i,3]) and (d>=w[i,4]) then
        begin
          if dfs(a-w[i,1],b-w[i,2],c-w[i,3],d-w[i,4])=2 then
            begin
              f[a,b,c,d]:=1;
              exit(1);
            end;
        end;
    end;
  f[a,b,c,d]:=2;
  exit(2);
end;

begin
   assign(input,'j5.in');reset(input);
 assign(output,'j5.out');rewrite(output);
  readln(n);
  for i:=1 to n do
    begin
      readln(a,b,c,d);
      if dfs(a,b,c,d)=2 then writeln('Roland')
        else writeln('Patrick');
    end;
end.

 

]]>