NEFU 15 八阵图（概率）-白红宇

八阵图

Problem : 15

Time Limit : 1000ms

Memory Limit : 65536K

description

相传诸葛孔明御敌时以乱石堆成石阵，按遁甲分成生、伤、休、杜、景、死、惊、开八门，变化万端，可挡十万精兵。（见《三国演义》）。

现将诸葛亮的“八阵图”示意如下：

现在一般认为，八阵图就是一个巨大的迷宫。当某人陷入其中时，他可以从很多门中选择第i个门，经过ri天后即可以逃出八卦阵，也就是所谓的“生门”；也可能经过ri天后回到原处，也就是所谓的“死门”。如果你不识得八卦阵，你只有随机选择一个门；在八卦阵中，无法留下是否经过的标记，也就是说，你如果选择了“死门”回到原处，你还是只能随机选择一个门。

现在，富有冒险精神的你，携带了W天的粮食和水进入了诸葛亮的八卦阵。由于八卦阵变化多端，你不知道八卦阵的布置，你的运气平平（也就是你选择每个门的可能性相同），你能安全逃出八卦阵吗？

input

有多组测试数据，输入的第一行只有一个正整数T(1≤T≤100);

每组测试数据占三行，具有如下形式：

N r1 r2 rn

M rn+1 rn+m

其中N（0≤N≤1000）是生门的数目，M（0≤M≤1000）是死门的数目，W（0≤W≤10^9）是你携带了W天的粮食和水。ri(1≤i≤n+m, 0≤ri≤10,000)是生门或死门经过的天数。

所有的测试数据都是非负整数。

output

对于每组测试数据，输出”Alive”，如果你能在W天内走出八卦阵。否则，输出”Dead”。

注意：你走出八卦阵所需要的天数，是你随机选择后走出八卦阵所需要的天数的平均值。

sample_input

3 4 5 6

7 8 9 10 11 12 13 14

2 1 1

2 3 1

2 1 1

sample_output

Dead

Alive

hint

概率

source

湖大

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define MM(a) memset(a,0,sizeof(a))typedef long long LL;typedef unsigned long long ULL;const int maxn = 3e3+5;const int mod = 1e9+7;const double eps = 1e-8;const int INF = 0x3f3f3f3f;LL gcd(LL a, LL b){ if(b == 0) return a; return gcd(b, a%b);}int m[maxn], n[maxn];int main(){ int T, N, W, M; scanf("%d",&T); while(T--) { scanf("%d", &N); int summ = 0, sumn = 0; for(int i=0; i