NYOJ 85 有趣的数——————简单思维

刺骨的言语ヽ痛彻心扉 2022-05-11 12:14 106阅读 0赞

## 有趣的数 ##

时间限制：3000 ms | 内存限制：65535 KB  
难度：2

## 描述 ##

把分数按下面的办法排成一个数表。

1/1 1/2 1/3 1/4…

2/1 2/2 2/3…

3/1 3/2 …

4/1…  
…

我们以z字型方法给上表的每项编号。特定方法：第一项是1/1，然后是1/2、2/1、3/1、2/2、1/3、1/4、2/3……。编程输入项号N（1<=N<=100000），输出表中第N项。

## 输入 ##

第一行有一个整数m(0<m<=10)，表示有m组测试数据；  
随后有m行，每行有一个整数N；  
输出  
输出表中第N项

## 样例输入 ##

4  
3  
14  
7  
12345

## 样例输出 ##

2/1  
2/4  
1/4  
59/99

--------------------

前三十项：  
1 1 2 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 7 6 5 4 3 2 1 1 2  
1 2 1 1 2 3 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7  
分子用数组a来存储  
分母用数组b来存储  
那么可以啊观察到  
 a 为 1 1 &ThickSpace; 2 3 &ThickSpace; 2 &ThickSpace; 1 1 &ThickSpace; 2 &ThickSpace; 3 &ThickSpace; 4 5 &ThickSpace; 4 &ThickSpace; 3 &ThickSpace; 2 &ThickSpace; 1 1 &ThickSpace; 2 &ThickSpace; 3 &ThickSpace; 4 &ThickSpace; 5 &ThickSpace; 6 7 &ThickSpace; 6 &ThickSpace; 5 &ThickSpace; 4 &ThickSpace; 3 &ThickSpace; 2 &ThickSpace; 1 &ThickSpace; 1 &ThickSpace; 2... b 为 1 2 &ThickSpace; 1 1 &ThickSpace; 2 &ThickSpace; 3 4 &ThickSpace; 3 &ThickSpace; 2 &ThickSpace; 1 1 &ThickSpace; 2 &ThickSpace; 3 &ThickSpace; 4 &ThickSpace; 5 6 &ThickSpace; 5 &ThickSpace; 4 &ThickSpace; 3 &ThickSpace; 2 &ThickSpace; 1 1 &ThickSpace; 2 &ThickSpace; 3 &ThickSpace; 4 &ThickSpace; 5 &ThickSpace; 6 &ThickSpace; 7 8 &ThickSpace; 7... a 为 1 \\quad 1 \\;2\\quad 3\\; 2\\; 1\\quad 1 \\;2 \\;3\\; 4\\quad 5\\; 4 \\;3\\; 2\\; 1 \\quad 1\\; 2\\; 3\\; 4 \\;5 \\;6 \\quad7 \\;6 \\;5\\; 4 \\;3\\; 2\\; 1\\; \\quad 1\\; 2...\\\\ b 为1 \\quad 2 \\;1 \\quad 1 \\;2\\; 3 \\quad4 \\;3\\; 2\\; 1\\quad 1 \\;2 \\;3\\; 4 \\;5 \\quad 6 \\;5\\; 4 \\;3 \\;2 \\;1 \\quad 1 \\;2\\; 3\\; 4 \\;5 \\;6 \\;7 \\quad 8 \\;7... a为112321123454321123456765432112...b为121123432112345654321123456787...

规律很简单了…

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5+7;
    int a[MAXN+10];
    int b[MAXN+10];
    int main()
    {
        
            //打个表
            int cnt=0;
            int num=1;
            while(cnt<MAXN-1)
            {
        
                    for(int i=1;i<=num;i++)
                    {
        
                            if(num&1)
                            {
        
                                    a[cnt]=num-i+1;
                                    b[cnt]=i;
                                    cnt++;
                            }
                            else
                            {
        
                                    a[cnt]=i;
                                    b[cnt]=num-i+1;
                                    cnt++;
                            }
                            if(cnt>=MAXN)   break;
                    }
                    num++;
            }
    //        for(int i=0;i<30;i++)
    //                printf("%d ",a[i]);puts("");
    //        for(int i=0;i<30;i++)
    //                printf("%d ",b[i]);
    //                printf("%d/%d ",a[i],b[i]);
            int t;
            scanf("%d",&t);
            while(t--)
            {
        
                    int n;
                    scanf("%d",&n);
                    n--;
                    printf("%d/%d\n",a[n],b[n]);
            }
            return 0;
    }