随笔-141  评论-9  文章-3  trackbacks-0
USACO 2.1.2 Ordered Fractions

/*
ID: lorelei3
TASK: frac1
LANG: C++
*/

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int MAX = 165;

typedef struct Frac{
    int a,b;
    double val;

    bool operator < (const Frac &t)const{
        return val < t.val;
    }
}Frac;

int gcd(int a, int b){
    if(b==0)
        return a;
    else
        return gcd(b, a%b);
}

int n;
Frac num[MAX*MAX];

int main(){

    ifstream in("frac1.in");
    ofstream out("frac1.out");

    in>>n;

    int k=0;
    for(int b=1; b<=n; ++b)
        for(int a=1; a<b; ++a){
            if(!(a%2) && !(b%2))
                continue;
            if(gcd(a,b)==1){
                num[k].a=a;
                num[k].b=b;
                num[k].val=(double)a/b;
                k++;
            }
        }
            
    sort(num, num+k);

    out<<"0/1\n";
    for(int i=0; i<k; ++i)
        out<<num[i].a<<"/"<<num[i].b<<endl;
    out<<"1/1\n";
    return 0;
}
posted on 2010-11-21 00:44 小阮 阅读(107) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮