USACO chapter 2 section 2.1 Ordered Fractions

```USER: tianbing tianbing [tbbd4261]
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!

/*
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

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

• 随笔 - 65
• 文章 - 2
• 评论 - 17
• 引用 - 0

•

• 积分 - 23608
• 排名 - 667