Attack

Attack

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

PBH 最近在玩一个游戏。游戏中玩家有 100 的血量，目前有 n 个小怪，小怪会按顺序前来攻击玩家且小怪只会采用 1v1 的方式，玩家每次可秒杀一个小怪，并受到小怪攻击力的伤害（血量减少小怪攻击力的数值），打死小怪会掉落药水。

现在问题来了，打完这 n 个小怪最少需要喝多少瓶药水（喝药水不耗时）？

Input

先输入一个整数 t 表示数据的组数，t 不超过 1000。

对于每组数据，第一行先输入小怪的个数 n (1 <= n <= 100)，接下来的 n 行输入小怪攻击力 atki (1 <= atki <= 50) 以及小怪掉落 mi (0 <= mi <= 4) 个药水和药水所能恢复生命的值 ai (1 <= ai <= 30)。

Output

对于每组数据先输出 "Case #x: "，x 表示当前为第几组数据，之后输出打完所有小怪需要的最少药水数。如果无法杀死这 n 个小怪，即某次攻击小怪时已无药水可用且当前血量无法攻击小怪（小怪攻击大于等于当前血量），则输出 ”QAQ”。

所有输出均不包括引号。

Sample Input

3
2
50 1 20
49 0
4
50 1 10
40 0
30 3 20 30 20
10 0
3
50 3 20 15 1
45 2 1 1
27 0

Sample Output

Case #1: 0
Case #2: QAQ
Case #3: 2

Hint

请大家仔细核对 "Case #x: "，建议复制样例输出中的字符串到你的代码，以防敲错导致 Wrong Answer。

代码：

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int num;
    struct node *next,*back;
};

int main()
{
    int a,b,c,d,e,f,g,h,j,i,k,l,m,n,o;
    struct node *head,*p,*q,*t;
    scanf("%d",&a);
    for(b=1;b<=a;b++)
    {
        scanf("%d",&c);
        g=100;
        h=0;
        m=0;
        n=0;
        head=(struct node *)malloc(sizeof(struct node));
        head->next=NULL;
        q=head;
        for(d=0;d<c;d++)
        {
            scanf("%d %d",&e,&f);
            g=g-e;
            if(g>0)
            {
                for(i=0;i<f;i++)
                {
                    p=(struct node *)malloc(sizeof(struct node));
                    scanf("%d",&p->num);
                    p->next=NULL;
                    for(k=0;k<h;k++)
                    {
                        q=q->next;
                        if(p->num>q->num)
                        {
                            t=q->back;
                            t->next=p;
                            p->back=t;
                            p->next=q;
                            q->back=p;
                            break;
                        }
                    }
                    if(k==h)
                    {
                        q->next=p;
                        p->back=q;
                    }
                    q=head;
                    h++;
                }
            }
            else
            {
                for(l=0; ;l++)
                {
                    if(h==0)
                        break;
                    t=head->next;
                    g=g+t->num;
                    if(h==1)
                    {
                        free(t);
                    }
                    else
                    {
                        head->next=t->next;
                        free(t);
                        t=head->next;
                        t->back=head;
                    }
                    h--;
                    n++;
                    if(g>0)
                        break;
                    if(h==0)
                        break;

                }
                if(h==0&&g<=0)
                {
                    m=1;
                }
                for(j=0;j<f;j++)
                {
                    p=(struct node *)malloc(sizeof(struct node));
                    scanf("%d",&p->num);
                    p->next=NULL;
                    for(o=0;o<h;o++)
                    {
                        q=q->next;
                        if(p->num>q->num)
                        {
                            t=q->back;
                            t->next=p;
                            p->back=t;
                            p->next=q;
                            q->back=p;
                            break;
                        }
                    }
                    if(o==h)
                    {
                        q->next=p;
                        p->back=q;
                    }
                    q=head;
                    h++;
            }
        }
    }
    if(m==0)
        printf("Case #%d: %d\n",b,n);
    else printf("Case #%d: QAQ\n",b);
}
    return 0;
}