• CF-48E. Ivan the Fool VS Gorynych the Dragon(bfs+dfs+判重回路)

    E. Ivan the Fool VS Gorynych the Dragon
    time limit per test
    2 seconds
    memory limit per test
    256 megabytes
    input
    standard input
    output
    standard output

    Once upon a time in a kingdom far, far away… Okay, let’s start at the point where Ivan the Fool met Gorynych the Dragon. Ivan took out his magic sword and the battle began. First Gorynych had h heads and t tails. With each strike of the sword Ivan can either cut off several heads (from 1 to n, but not more than Gorynych has at the moment), or several tails (from 1 to m, but not more than Gorynych has at the moment). At the same time, horrible though it seems, Gorynych the Dragon can also grow new heads and tails. And the number of growing heads and tails is determined uniquely by the number of heads or tails cut by the current strike. When the total number of heads and tails exceeds R, Gorynych the Dragon strikes its final blow and destroys Ivan the Fool. That’s why Ivan aims to cut off all the dragon’s heads and tails as quickly as possible and win. The events can also develop in a third way: neither of the opponents can win over the other one and they will continue fighting forever.

    The tale goes like this; easy to say, hard to do. Your task is to write a program that will determine the battle’s outcome. Consider that Ivan strikes consecutively. After each blow Gorynych grows a number of new heads and tails depending on the number of cut ones. Gorynych the Dragon is defeated if after the blow he loses all his heads and tails and can’t grow new ones. Ivan fights in the optimal way (fools are lucky), i.e.

    • if Ivan can win, he wins having struck the least number of blows;
    • if it is impossible to defeat Gorynych, but is possible to resist him for an infinitely long period of time, then that’s the strategy Ivan chooses;
    • if Gorynych wins in any case, Ivan aims to resist him for as long as possible.

    Input

    The first line contains three integers ht and R (0?≤?h,?t,?R?≤?2000?<?h?+?t?≤?R) which represent the initial numbers of Gorynych’s heads and tails and the largest total number of heads and tails with which Gorynych the Dragon does not yet attack. The next line contains integer n (1?≤?n?≤?200). The next n contain pairs of non-negative numbers "hi ti" which represent the number of heads and the number of tails correspondingly, that will grow if Gorynych has i heads (1?≤?i?≤?n) cut. The next line contains an integer m (1?≤?m?≤?200) and then — the description of Gorynych’s behavior when his tails are cut off in the format identical to the one described above. All the numbers in the input file do not exceed 200.

    Output

    Print "Ivan" (without quotes) in the first line if Ivan wins, or "Zmey" (that means a dragon in Russian) if Gorynych the Dragon wins. In the second line print a single integer which represents the number of blows Ivan makes. If the battle will continue forever, print in the first line "Draw".

    Sample test(s)
    input
    2 2 4
    2
    1 0
    0 1
    3
    0 1
    0 1
    0 0
    
    output
    Ivan
    2
    
    input
    2 2 4
    1
    0 1
    1
    1 0
    
    output
    Draw
    
    input
    2 2 5
    1
    1 1
    1
    3 0
    
    output
    Zmey
    2

    思路:本题数据最多就两百,因此可以使用广搜出猎人斩龙的最佳路数,如果猎人无法斩龙,那就深搜判断是否组成回路,从而形成永久的对战模式,还是不行那就更新猎人最终成为龙的食物的最大路数。


    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int mm=250;
    const int oo=1e9;
    int vis[mm][mm];
    bool yes;
    int h,t,r,n,m;
    class node
    {
      public:int h,t,c;
    }hh[mm],tt[mm];
    queue<node >q,p;
    int dfs(int x,int y)
    { int&ret=vis[x][y];
      int tx,ty;
      if(x+y>r)return 0;
      if(vis[x][y]==-2)
      {
        yes=1;return 0;
      }
      else if(vis[x][y]==-1)
      {
        ret=-2;int dd=-oo,z;
        int bbs;
        bbs=n<x?n:x;
        for(int i=0;i<bbs;i++)
          {
            tx=x+hh[i].h-i-1;ty=y+hh[i].t;
            z=dfs(tx,ty)+1;
            dd=dd>z?dd:z;
          }
          bbs=m<y?m:y;
          for(int i=0;i<bbs;i++)
          {
            tx=x+tt[i].h;ty=y+tt[i].t-i-1;
            z=dfs(tx,ty)+1;
            dd=dd>z?dd:z;
          }
          ret=dd;
      }
      return ret;
    }
    int main()
    {
      while(cin>>h>>t>>r)
      {
        cin>>n;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
          cin>>hh[i].h>>hh[i].t;
        }
        cin>>m;
        for(int j=0;j<m;j++)
        {
          cin>>tt[j].h>>tt[j].t;
        }
        vis[h][t]=1;
         int x,y,zz;
         while(!q.empty())q.pop();
         node z,p;yes=0;
         z.h=h;z.t=t;z.c=0;
         q.push(z);
         while(!q.empty()&&!yes)
         { z=q.front();q.pop();
          int bbs=n<z.h?n:z.h;
          for(int j=0;j<bbs;j++)
          {
            x=z.h+hh[j].h-j-1;y=z.t+hh[j].t;
            if(x+y>r)continue;
            if(!vis[x][y])
            {vis[x][y]=1;
             p.h=x;p.t=y;p.c=z.c+1;
             if(x==0&&y==0)
              { cout<<"Ivan\n"<<p.c<<"\n";yes=1;
                break;
              }
             ///if(x+y>r&&d>z.c){d=z.c;continue;}
             q.push(p);
            }
          }
          bbs=m<z.t?m:z.t;
          for(int j=0;j<bbs;j++)
          {
            x=z.h+tt[j].h;y=z.t+tt[j].t-j-1;
            if(x+y>r)continue;
            if(!vis[x][y])
            {vis[x][y]=1;
             p.h=x;p.t=y;p.c=z.c+1;
             if(x==0&&y==0)
              { cout<<"Ivan\n"<<p.c<<"\n";yes=1;
                break;
              }
             ///if(x+y>r&&d>z.c){d=z.c;continue;}
             q.push(p);
            }
          }
        }
        if(yes)continue;
        memset(vis,-1,sizeof(vis));
        int ans=dfs(h,t);
        if(yes)cout<<"Draw\n";
        else cout<<"Zmey\n"<<ans<<"\n";
      }
    }
    
    相关文章
    相关标签/搜索
    每日一句
      每一个你不满意的现在,都有一个你没有努力的曾经。
    公众号推荐
       一个历史类的公众号,欢迎关注
    一两拨千金
    4887铁算王中王开奖结果小说 达尔| 慈利县| 黄石市| 山丹县| 中山市| 彩票| 海门市| 祥云县| 介休市| 杭锦后旗| 平定县| 唐海县| 七台河市| 大安市| 丁青县| 定远县| 广州市| 平顶山市| 仲巴县| 塘沽区| 简阳市| 大田县| 肇源县| 郯城县| 岑溪市| 蕉岭县| 工布江达县| 淳化县| 余江县| 思茅市| 乐安县| 晋中市| 班戈县| 明星| 大同市| 措勤县| 霍邱县| http://fa.hz0j1r1vo.fun http://fa.hz0j1r8vo.fun http://fa.hz0j1r0vo.fun http://fa.hz0j1r4vo.fun http://fa.hz0j2r0vo.fun