AOJ 762.分数数列

193


题目



Description  


一个数列的前6项为:1/2,3/5,4/7,6/10,8/13,9/15等,试求数列的第n项(n<2000)



Input  


输入一个整数n(0< n < 2000)



Output  


输出数列的第n项



Sample Input  


1980



Sample Output  


3203/5183


题解



找规律



对于第n项

分子为前n-1项未出现的自然数中最小的一个

分母为分子+n


(真难找,感谢我瑞)

代码



/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;
 
//DEBUG MODE
#define debug 0
 
//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 6000;
bool Has[maxn];
bool Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;
    memset(Has,false,sizeof(Has));
    int last = 1;
    for(int i = 1;i <= n;i++) {
        int j;
        for(j = last;Has[j];j++);
        Has[j] = true;
        Has[j + i] = true;
        last = j;
        if(i == n)
            printf("%d/%d\n",j,j + i);
    }
    return true;
}
 
int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论