【nyist】Personal Contest.3（比赛题解）

小鱼儿 2022-08-25 15:56 136阅读 0赞

比赛链接：http://www.bnuoj.com/bnuoj/contest\_show.php?cid=3489

全是大水题。AK掉了、、、虽然不是第一个。

题目考代码能力和思路的比较多！

G题：

# HT的奖金 #

Time Limit: 2000ms

Case Time Limit: 2000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][]

Font Size:\+\-

五一将近，HT所在的公司又要发节日慰问金了，但他们发奖金的方式非常奇特，老板会拿着N（N<=4000）张百元大钞到HT面前，让HT从中选出连续的K张，并要求这K张的连号的（但它们可以不是按顺序排列的）。现在HT想知道，对于给定的钞票序列，他最多能拿到多少奖金呢=，=

## Input ##

一个整数N，表示一共有N张钞票

接下来N行，按顺序给出每张钞票的编号。钞票编号以两个大写字母HT开头，后面紧跟8个数字。【假设这里木有假钞，所以也不可能有同号的钞票。。。】

## Output ##

一个整数P，表示HT最多能得到的奖金数目

## Sample Input ##

5
    HT00000001
    HT00000006
    HT00000002
    HT00000004
    HT00000003

## Sample Output ##

300

## 这个题目是第二个做出来的，感觉自己的思路比较好，详细说一下。首先就是提取出来存在一个数组中，比如说1 0 2 11 6 5 7 8，然后对他进行排序。 ##

结果为： 0 1 2 5 6 7 8 11

位置为： 2 1 3 6 5 7 8 4

其中连续的有0 1 2 和 5 6 7 8.

位置分别为2 1 3和 6 5 7 8，即找出排序后位置最大的既为结果。当时感觉行巧妙！看代码吧

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    struct Node
    {
        int num;
        int x;
    };
    Node a[12000];
    int comp(Node k,Node y)
    {
        if(k.x!=y.x)
            return k.x<y.x;
    }
    int solve(int y,int len)
    {
        //printf("%d %d\n",len,y);
        int b[12000],l=0;
        for(int i=y-len-1;i<y;i++)
        {
            b[l++]=a[i].num;
        }
        sort(b,b+l);
        //for(int i=0;i<l;i++)
          //  printf("%d ",b[i]);
        int tmp=1,max=0;
        for(int i=1;i<=l;i++)
        {
            //printf("%d\n",tmp);
            if(b[i]-b[i-1]==1)
                tmp++;
            else
            {
                if(tmp>max)
                    max=tmp;
                tmp=1;
            }
        }
        //printf("%d\n",max);
        return max;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            char p,pp,ppp;
            string s;
            for(int i=0;i<n;i++)
            {
                scanf("%c%c%c",&ppp,&p,&pp);
                cin>>s;
                while(s[0]=='0')
                {
                    s.erase(0,1);
                }
                int tmp=0,tt=1;
                for(int j=s.size()-1;j>=0;j--)
                {
                    tmp=tmp+(s[j]-'0')*tt;
                    tt*=10;
                }
                a[i].x=tmp;a[i].num=i+1;
            }
            //for(int i=0;i<n;i++)
              //  printf("%d ",a[i].x);
            sort(a,a+n,comp);
            int len=0,max=0;
            for(int i=1;i<=n;i++)
            {
                if(a[i].x-a[i-1].x==1)
                {
                    len++;
                }
                else
                {
                    int kk=solve(i,len);
                    if(kk>max)
                        max=kk;
                    len=0;
                }
            }
            printf("%d\n",max*100);
        }
        return 0;
    }
    /*
    10
    GH000001
    GH000009
    GH00003
    GH00002
    GH00004
    GH000010
    GH000065
    GH0000544
    GH00007
    GH00008
    */

后面的都比较水，直接贴代码了。考代码能力了。

按照我做题的顺序贴。

F题：

# F. 顺序做题法 #

Time Limit: 2000ms

Case Time Limit: 2000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 1]

Font Size:\+\-

一年一度的校赛开始了，某L虽然不需要参赛，却还得参与赛前的题目测试工作。为了保证比赛题目数据无误，大牛要求某L必须把每一个题都做一遍— —||。在无法抗命的情况下，某L决定采用“顺序做题法”，即从第一题开始做，做完之后再做第二题，然后是第三题，以此类推……由于时间和能力有限，某L每天最多只能做K分钟的题目，且每个题目只能在一天内做完（i.e. 如果有一个题第一天只完成了一部分，则第二天必须从头开始做此题，因为他已经看不懂自己前一天写的代码了=，=）。现在已知某L做每个题所需要的时间，问某L最少需要多少天才能完成所有的题目。

## Input ##

第一行读入一个数T（T<50），表示数据组数，对于每组数据，先读入两个数N（0<N<=10^4）、K（0<K<=1000），表示有N个题，某L每天最多做题K分钟。接下来是N个数a\[0\]--a\[N-1\]，分别表示做每个题所需的时间（分钟）。题目保证a\[i\]<=K（0<=i<=N-1）。

## Output ##

对于每组数据，输出一个数D，表示某L最少需要多少天才能完成所有的题目。

## Sample Input ##

2
    3 3
    1 2 3
    3 3
    1 3 3

## Sample Output ##

2
    3

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    int a[12000];
    int main()
    {
        int T;
        scanf("%d",&T);
        int n,k;
        while(T--)
        {scanf("%d%d",&n,&k);
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            int ans=0,tmp=0;
            for(int i=0;i<n;i++)
            {
                tmp+=a[i];
                if(tmp==k)
                {
                    ans++;
                    tmp=0;
                }
                else if(tmp>k)
                {
                    ans++;
                    tmp=a[i];
                }
            }
            if(tmp>0)
                ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

I题：

# 萌萌的萌数列 #

Time Limit: 5000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 2]

Font Size:\+\-

萌萌很喜欢数列，数列有很多基本的属性，像什么平均值啦、最大值啦、最小值啦、方差啦、平均差啦等等等等。但是萌萌觉得并不是所有的序列都很萌，他觉得如果一个数列的最大值和最小值之差大于100，那么这个数列就不是萌数列。现在给你一个数列，萌萌需要你帮他判断这个序列是否是萌数列。

## Input ##

第一行：一个整数N（0<N<=100000），表示这个数列有多少项。

第二行：N个数，以空格隔开，第i个数表示该数列的第i项，每一项的取值范围都是\[-1000000,1000000\]。

## Output ##

如果这个数列是萌数列，则输出一行“Yes”，否则输出一行“No”。

## Sample Input ##

5
    1 2 3 4 5

## Sample Output ##

Yes

[Submit][]

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int max=-9999999,min=9999999,x;
            for(int i=0;i<n;i++)
            {
                scanf("%d",&x);
                if(x>max)
                    max=x;
                if(x<min)
                    min=x;
            }
            if(max-min>100)
                printf("No\n");
            else
                printf("Yes\n");
        }
        return 0;
    }

D题：

# 庞大的矩阵 #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 3]

Font Size:\+\-

线性代数是个让大家都感到非常头痛的课程，其中的矩阵乘法尤为复杂，往往一道题要废无数张草稿纸 — —||。在做A\*B=C的题目时，某L总是对自己的答案信心不足，于是，验证三个矩阵A、B、C是否满足A\*B=C就成为了一个非常必要的事情，因此他想到了用电脑来解决这个问题，但不幸的是，他还要去给校赛出题，所以这个任务就交给你了~

## Input ##

读入一个整数T（T<=15），表示数据的组数，接下来T组数据，每组先读入一个整数N（0<N<=100），表示矩阵的大小，接下来会依次读入三个大小为N\*N的矩阵A、B、C，请你验证A\*B是否等于C（A、B、C矩阵的所有元素均为int范围内的整数）

## Output ##

每行输出一个单词“Right”或“Wrong”（不含引号），Right表示等式成立，Wrong表示某L不幸算错了。

## Sample Input ##

2
    
    2
    1 1
    1 1
    
    1 1
    1 1
    
    2 2
    2 2
    
    2
    1 2
    0 1
    
    0 2
    2 1
    
    0 0
    0 0

## Sample Output ##

Right
    Wrong

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int a[120][120],b[120][120],c[120][120];
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                    scanf("%d",&a[i][j]);
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                    scanf("%d",&b[i][j]);
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                    scanf("%d",&c[i][j]);
            }
            int ok=1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    int tt=0;
                    for(int k=1;k<=n;k++)
                    {
                        tt+=a[i][k]*b[k][j];
                    }
                    if(tt!=c[i][j]){
                        ok=0;break;
                    }
                }
                if(ok==0)
                    break;
            }
            if(ok)
                printf("Right\n");
            else
                printf("Wrong\n");
        }
        return 0;
    }

H题：

# 密码长度计算 #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 4]

Font Size:\+\-

龚治经常喜欢修改他实验室的电脑的开机密码，但是他有个习惯，他喜欢通过修改一个已有密码的部分字符来产生新的密码。有一天他突发奇想，给每两个相同长度的密码定义了一个距离。距离的计算方法是将两个密码对应位置的字符的ASCII码值的差值累和。例如密码”asdf”和密码”bsdg”的距离就是1+0+0+1=2。现在给你两个长度相同的密码，你需要修改第一个密码中不同的K位（不能不修改）。请你帮他计算他的所有修改方案中，修改后的第一个密码和第二个密码的距离的最小值。

## Input ##

第一行：一个整数T，表示有T组数据

每组数据由三行组成：前两行是两个密码，长度（不超过1000）相同。第三行包含一个整数K（0<=K<=1000），表示你需要修改第一个密码中的K位。

## Output ##

每组数据输出一行一个整数，表示符合题目条件的密码距离最小值。

## Sample Input ##

3
    asdf
    bsdg
    0
    aaa
    baz
    1
    aa
    aa
    2

## Sample Output ##

2
    1
    2

[Submit][]

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    int flag[1200];
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            memset(flag,0,sizeof(flag));
            int k;
            string s,t;
            cin>>s>>t;
            scanf("%d",&k);
            while(k--)
            {
                int zhi=0,p=0;
                for(int i=0;i<s.size();i++)
                {
                    int kk=fabs(t[i]-s[i]);
                    if(kk>=zhi&&flag[i]==0){
                        zhi=kk;
                        p=i;
                    }
                }
                if(zhi==0)
                {
                    s[p]=t[p]-1;flag[p]=1;
                }
                else
                {
                    s[p]=t[p];flag[p]=1;
                }
            }
            //cout<<s<<endl;
            int ans=0;
            for(int i=0;i<s.size();i++)
            {
                ans+=fabs(t[i]-s[i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

C题：

# 座位编号 #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 5]

Font Size:\+\-

第十届北京师范大学程序竞赛开始了，大牛51isoft准备采用两种传统的方法给比赛机房的各台机器编号，一种可以成为横”S”方式，另种可称为竖“S”方式（如下图所示）

![number.bmp][]

规定两种编号方法均从右侧开始将机器编为第一列，从最上方将机器编为第一行。ch0588同学作为刚入学的大一新生自然也要参加这场比赛，因此赛前他想向大牛51isoft询问他具体的比赛位置，大牛则会选择以下两种方式告诉ch0588他具体的比赛位置，一是告诉ch0588比赛时的机器位于第几行第几列，二是告诉他机器的编号。

## Input ##

输入包括多组数据，每组数据包含两行，第一行三个整数m,n,c，代表机房有m行n列机器(0<m,n<100)，c代表机器将采用何种方式编号，1表示采用横“S”行，2表示竖“S”型，第二行先输入一个整数1或2代表51isoft将选择哪种方式告诉ch0588，若输入为1则再输入两个整数i，j表示ch0588将在第i行第j列的机器上比赛；若输入2，则再输入一个整数k，表示ch0588将在编号为k的机器上比赛；若输入0表示该组数据输入结束。当n=m=c=0时表示所有数据输入结束

## Output ##

对于大牛的每次选择，若51isoft选择第一种方式告诉ch0588，则输出该位置上机器的编号；若大牛选择第二种方式告诉ch0588（囧~~），则输出编号为k的机器位于机房的第几行第几列(输出的行和列用空格分开)，如此ch0588就能很快的找到自己比赛的机器了！

## Sample Input ##

5 5 1
    1 1 1
    2 7
    0
    0 0 0

## Sample Output ##

1
    2 4

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    int map1[125][125],map2[125][125];
    int sum1(int x,int y)  //行列
    {
        int ok,be=1;
        for(int i=1; i<=x; i++)
        {
            if(i%2==1)
            {
                ok=1;
                be=y*(i-1)+1;
            }
            else
            {
                ok=0;
                be=y*i;
            }
            for(int j=1; j<=y; j++)
            {
                if(ok)
                {
                    map1[i][j]=be++;
                }
                else
                {
                    map1[i][j]=be--;
                }
            }
        }
        /*for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                printf("%d ",map1[i][j]);
            }
            printf("\n");
        }*/
    }
    int sum2(int x,int y)
    {
        int ok,be=1;
        for(int i=1; i<=y; i++)
        {
            if(i%2==1)
            {
                ok=1;
                be=x*(i-1)+1;
            }
            else
            {
                ok=0;
                be=x*i;
            }
            for(int j=1; j<=x; j++)
            {
                if(ok)
                {
                    map2[j][i]=be++;
                }
                else
                {
                    map2[j][i]=be--;
                }
            }
        }
        /*for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                printf("%d ",map2[i][j]);
            }
            printf("\n");
        }*/
    }
    int main()
    {
        int m,n,k;
        while(~scanf("%d%d%d",&m,&n,&k))
        {
            memset(map1,0,sizeof(map1));
            memset(map2,0,sizeof(map2));
            if(k==1)
                sum1(m,n);
            else if(k==2)
                sum2(m,n);
            if(m==0&&n==0&&k==0)
                break;
            int flag;
            while(scanf("%d",&flag))
            {
                if(flag==0)
                    break;
                if(flag==1)
                {
                    int i,j;
                    scanf("%d%d",&i,&j);
                    if(k==1)
                        printf("%d\n",map1[i][j]);
                    else if(k==2)
                        printf("%d\n",map2[i][j]);
                }
                else if(flag==2)
                {
                    int x,ans_i,ans_j,ok=0;
                    scanf("%d",&x);
                    for(int i=1; i<=m; i++)
                    {
                        for(int j=1; j<=n; j++)
                        {
                            if(k==1)
                            {
                                if(map1[i][j]==x)
                                {
                                    ans_i=i,ans_j=j;
                                    ok=1;
                                    break;
                                }
                            }
                            else if(k==2)
                            {
                                if(map2[i][j]==x)
                                {
                                    ans_i=i,ans_j=j;
                                    ok=1;
                                    break;
                                }
                            }
                        }
                        if(ok)
                            break;
                    }
                    printf("%d %d\n",ans_i,ans_j);
                }
            }
        }
        return 0;
    }

A题：

# 牛式 #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 6]

Font Size:\+\-

下面是一个乘法竖式，如果用我们给定的n个数字来取代\*，可以使式子成立的话，我们就叫这个式子牛式。

* * *
       x    * *
        -------
          * * *
        * * *
        -------
        * * * *

数字只能取代\*，当然第一位不能为0。

注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.

写一个程序找出所有的牛式。

## Input ##

Line 1:数字的个数n（1<=n<=9）。

Line 2:N个用空格分开的数字（每个数字都E \{1,2,3,4,5,6,7,8,9\}）。

## Output ##

共一行，输出一个数字。表示牛式的总数。

## Sample Input ##

5
    2 3 4 6 8

## Sample Output ##

## Hint ##

下面是样例的那个牛式。

2 2 2
    x     2 2
    ---------
        4 4 4
      4 4 4
    ---------
      4 8 8 4

注意 结果只能4位数

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int ok[15]= {0};
    
    int solve(int x)
    {
        while(x)
        {
            if(ok[x%10]==0)
                return false;
            x/=10;
        }
        return true;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            memset(ok,0,sizeof(ok));
            for(int i=0; i<n; i++)
            {
                int x;
                scanf("%d",&x);
                ok[x]=1;
            }
            int ans=0,i,j;
            for(i=100; i<=999; i++)
            {
                if(solve(i)==false)
                {
                    continue;
                    printf("Yes\n");
                }
                for(j=10; j<=99; j++)
                {
                    if(solve(j)==false)
                        continue;
                    if(i*j>9999 || solve(i*j)==false)
                        continue;
                    int k=j;
                    if(j%10*i>999 || solve(j%10*i)==false)
                        continue;
                    if((j/10)%10*i>999 || solve((j/10)%10*i)==false)
                        continue;
                    ans++;
                }
                /*
                while(k)
                {
                    if(solve(i*(k%10))==false)
                        break;
                    k/=10;
                }*/
    
            }
            printf("%d\n",ans);
        }
    }

B题：

# Alkane or Alkene?? #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 7]

Font Size:\+\-

烷烃（Alkane）和烯烃（Alkene）是两类最简单的有机化合物，它们的通式想必大家应该在高中时都学过吧，分别是CnH2n+2和CnH2n。现在你的任务来了，给你一个烃的结构简式（如下图）判断一下它是烷烃还是烯烃

![aoa.bmp][]

## Input ##

输入一个字符串，代表烃的结构简式，简式的长度不大于100，不包含任何空格，且只包含C、H、数字和 ( ), ( )既可以表示支链，也可以表示相同基团写在一起的情况，括号中不会再有括号出现。保证紧跟在C原子后面的数字不超过9，而原子的总数也不会超过109。相同的基团可以用括号写在一起，也可以分开写

## Output ##

输出它是哪种烃，输出“Alkane”代表它是烷烃，输出“Alkene”代表它是烯烃

## Sample Input ##

CH4

## Sample Output ##

Alkane

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    using namespace std;
    int main()
    {
        string s;
        while(cin>>s)
        {
            stack<string> v;
            int h=0,c=0,ok=0,tc=0,th=0;
            string tmp="";
            for(int i=0;i<s.size();i++)
            {
                if(ok==0 && s[i]=='C')
                {
                    //printf(" %d ",i);
                    if(s[i+1]>='0' && s[i+1]<='9'){
                        c+=(s[i+1]-'0');
                        i++;
                    }
                    else{
                        c++;
                    }
                }
                if(ok==0 && s[i]=='H')
                {
                    int tmp=0,j;
                    for(j=i+1;j<s.size();j++)
                    {
                        if(s[j]>='0' && s[j]<='9')
                        {
                            tmp=tmp*10+(s[j]-'0');
                        }
                        else
                            break;
                    }
                    if(tmp==0)
                        tmp=1;
                    h+=tmp;i=j-1;
                }
                if(s[i]=='(')
                {
                    ok=1;
                }
                if(ok==1 && s[i]=='C')
                {
                    if(s[i+1]>='0' && s[i+1]<='9'){
                        tc+=(s[i+1]-'0');
                        i++;
                    }
                    else
                        tc++;
                }
                if(ok==1 && s[i]=='H')
                {
                    int tmp=0,j;
                    for(j=i+1;j<s.size();j++)
                    {
                        if(s[j]>='0' && s[j]<='9')
                        {
                            tmp=tmp*10+(s[j]-'0');
                        }
                        else
                            break;
                    }
                    if(tmp==0)
                        tmp=1;
                    th+=tmp;i=j-1;
                }
                if(s[i]==')')
                {
                    int tmp=0,j;
                    for(j=i+1;j<s.size();j++)
                    {
                        if(s[j]>='0' && s[j]<='9')
                        {
                            tmp=tmp*10+(s[j]-'0');
                        }
                        else
                            break;
                    }
                    if(tmp==0)
                        tmp=1;
                    c+=(tc*tmp);
                    h+=(th*tmp);
                    tc=0,th=0;
                    ok=0;
                    i=j-1;
                }
            }
            if(h>c && h==c*2)
                printf("Alkene\n");
            else if(h>c && h==(c*2+2))
                printf("Alkane\n");
            //printf("%d %d\n",c,h);
        }
        return 0;
    }
    /*
    CH4
    (CH3)3CC(CH3)3
    CH2CHCH3
    CH3CH2C(C2H5)2CH2CH3
    */

最后E题：（最水的一个）

# 外星人的监视 #

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

[Submit][] [Status][Status 8]

Font Size:\+\-

在浩瀚的宇宙中，除了人类，当然还有别的智慧型生命体，比如克林贡星人、沃贡星人、天顶星人还有那美克星人等等... “情报统合思念体”和“天盖领域”是两个不为人知的外星人种（以下以“情”、“天”作为简称），他们有着高度的智慧和严密的组织，在宇宙的各处监视着一切事物。尽管已经进化到了高度发达的状态，可他们依然在宇宙中探求成为超神的途径。最近，他们查觉地球上有一个T犇有可能为他们带来进化的信息，于是决定组成一个联盟共同在暗中监视T犇的一举一动。这个联盟组织有着严格且互为牵制的上下线关系：每一个下线的成员，都有一个与他不同种族的上线，而这种关系是传递的。没想到的是，表面真诚的“天”摆了盟友一道，他们给每一个“天”的下线都秘密地额外安排了一个“天”的成员作为上线，于是当“天”的成员向他的上线汇报的时候，可以对“情”有所保留。诚实而高尚的“情”很快察觉到了这一猫腻，但为了顾全大局，他们只是调查清了联盟组织真实的上下线关系而没有点破。如果一个成员的直接上线被称为1级上线，而该成员的1级上线的上线被称为2级上线，然后以此类推直到n级上线，那么，作为一个优秀的“情”特工，你知道每一个成员的n级上线的真实情报吗？

## Input ##

第1行为整数T代表case数。2到T+1行的每一行都有两个整数c和n，c为1代表当前成员为“情”成员，为2代表“天”成员，n是不大于40的正整数。

## Output ##

每一行输出两个数fn和sn，以空格隔开。fn代表当前成员的n级上线中“情”的 个数，sn代表“天”的个数。

## Sample Input ##

4
    1 1
    1 2
    1 3
    2 1

## Sample Output ##

0 1
    1 1
    1 2
    1 1

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    using namespace std;
    int q[100]={0},t[100]={0};
    void isit()
    {
        q[1]=1,t[2]=1;
        for(int i=3;i<=45;i++)
        {
            q[i]=t[i-1];
            t[i]=q[i-1]+t[i-1];
            //printf("%d %d\n",q[i],t[i]);
        }
    }
    int main()
    {
        int T;isit();
        scanf("%d",&T);
        while(T--)
        {
            int k,n;
            scanf("%d%d",&k,&n);
            if(k==1)
            {
                printf("%d %d\n",q[n+1],t[n+1]);
            }
            else
                printf("%d %d\n",q[n+2],t[n+2]);
        }
    }

[Submit]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#
[Status]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/G
[Status 1]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/F
[Status 2]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/I
[Status 3]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/D
[Status 4]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/H
[Status 5]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/C
[number.bmp]: http://www.bnuoj.com/bnuoj/img/number.bmp
[Status 6]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/A
[Status 7]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/B
[aoa.bmp]: http://www.bnuoj.com/bnuoj/img/aoa.bmp
[Status 8]: http://www.bnuoj.com/bnuoj/contest_show.php?cid=3489#status/E