USACO : Ordered Fractions



/*
ID: tausiq11
PROG: frac1
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100000
#define LL long long

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Pr(x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) cout << *it << " "; cout << endl;
#define Set(a, s) memset(a, s, sizeof (a))
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

struct node {
	int numerator;
	int demonimator;
	int val;
};

node a [N];
int len;
int n;

int gcd (int p, int q)
{
	if ( q == 0 ) return p;
	return gcd (q, p % q);
}

bool cmp (node p, node q)
{
	if ( p.val < q.val ) return true;
	return false;
}

int main ()
{
	Rd ("frac1.in");
	Wt ("frac1.out");

	scanf ("%d", &n);

	a [0].numerator = 0;
	a [0].demonimator = 1;
	a [0].val = 0;

	a [1].numerator = 1;
	a [1].demonimator = 1;
	a [1].val = 100000000;

	len = 2;

	for ( int i = 1; i < n; i++ ) {
		for ( int j = i + 1; j <= n; j++ ) {
			if ( gcd (i, j) == 1 ) {
				a [len].numerator = i;
				a [len].demonimator = j;
				a [len].val = (int) (((double)i / (double)j) * 100000000.0);
				len++;
			}
		}
	}

	sort (a, a + len, cmp);

	for ( int i = 0; i < len; i++ ) {
		printf ("%d/%d\n", a [i].numerator, a [i].demonimator);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Judge Response

USER: [tausiq11]
TASK: frac1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4224 KB]
   Test 2: TEST OK [0.000 secs, 4224 KB]
   Test 3: TEST OK [0.000 secs, 4224 KB]
   Test 4: TEST OK [0.000 secs, 4224 KB]
   Test 5: TEST OK [0.000 secs, 4224 KB]
   Test 6: TEST OK [0.000 secs, 4224 KB]
   Test 7: TEST OK [0.000 secs, 4224 KB]
   Test 8: TEST OK [0.000 secs, 4224 KB]
   Test 9: TEST OK [0.000 secs, 4224 KB]
   Test 10: TEST OK [0.000 secs, 4224 KB]
   Test 11: TEST OK [0.011 secs, 4224 KB]

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s