USACO chapter 2 section 2.1 Ordered Fractions

USER: tianbing tianbing [tbbd4261]
TASK: frac1
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 2928 KB]
Test 2: TEST OK [0.000 secs, 2928 KB]
Test 3: TEST OK [0.000 secs, 2928 KB]
Test 4: TEST OK [0.011 secs, 2928 KB]
Test 5: TEST OK [0.011 secs, 2928 KB]
Test 6: TEST OK [0.000 secs, 2928 KB]
Test 7: TEST OK [0.011 secs, 2928 KB]
Test 8: TEST OK [0.054 secs, 2928 KB]
Test 9: TEST OK [0.043 secs, 2928 KB]
Test 10: TEST OK [0.108 secs, 2928 KB]
Test 11: TEST OK [0.313 secs, 2928 KB]
All tests OK.

YOUR PROGRAM ('frac1') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.

Here are the test data inputs:

------- test 1 -------
1
------- test 2 -------
2
------- test 3 -------
4
------- test 4 -------
7
------- test 5 -------
10
------- test 6 -------
15
------- test 7 -------
24
------- test 8 -------
50
------- test 9 -------
75
------- test 10 -------
100
------- test 11 -------
160
Keep up the good work!

Thanks for your submission!

数据范围小,直接做就可以了

/*
ID:tbbd4261
PROG:frac1
LANG:C++
*/
#include
<iostream>
#include
<vector>
#include
<algorithm>
#include
<fstream>
using namespace std;
ifstream fin(
"frac1.in");
ofstream fout(
"frac1.out");
typedef 
struct 
{
  
int x,y;
} type;

vector
<type>vec;

int gcd(int x, int y)
{
    
if(!x||!y)return x>y?x:y;
    
for(int t; t=x%y; x=y,y=t)
       ;
    
return y;
}

bool f(type a,type b)
{
     
return a.x*1.0/a.y<b.x*1.0/b.y;
}

void solve (int n)
{
     type tem;
     
int a=0,b=1;
     
for(b=1; b<=n; b++)
     
for(a=0; a<=b; a++)
     {
        
if(gcd(a,b)==1)
        {
          tem.x
=a; tem.y=b;
          vec.push_back(tem);
          }
     }
     sort(vec.begin(),vec.end(),f);
     
for(int i=0; i<vec.size(); i++)
     fout
<<vec[i].x<<"/"<<vec[i].y<<endl;
}

int main()
{
  
    
    
int n;
    fin
>>n;
    solve(n);
   
// system("pause");
    return 0;
}

posted on 2010-06-18 10:52 田兵 阅读(106) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜