frac1.cpp

USACO Section 2.1的全部AC的代码 OIer专用.

/*
NAME:lemon_c1
LANG:C++
PROG:frac1
*/
#include<fstream>
using namespace std;
ifstream cin("frac1.in");
ofstream cout("frac1.out");
class node
{
	public:
		int f,m;
		double v;
		node(int f1=0,int m1=0):f(f1),m(m1){v=(double)f/(double)m;}
		node(const node &s):f(s.f),m(s.m),v(s.v){}
		operator double()
		{
			return v;
		}
		friend ostream & operator << (ostream &o,node &s)
		{
			o<<s.f<<'/'<<s.m;
			return o;
		}
};
node t[25601];
int size=2;
int n;
int cmp(const void *t1,const void *t2)
{
	return (*(node *)t1)>(*(node *)t2)?1:-1;
}
int main(void)
{
	cin>>n;
	t[0]=node(0,1);
	t[1]=node(1,1);
	for(int r=2;r<=n;r++)
		for(int i=1;i<r;i++)
			t[size++]=node(i,r);
	qsort(t,size,sizeof(node),cmp);
	int size1=size;
	for(int i=0;i<size1-1;i++)
		if(t[i]==t[i+1])
		{
			int j;
			for(j=i+1;t[j]==t[i];j++,size--)t[j].v=2;
			i=j;
		}
	qsort(t,size1,sizeof(node),cmp);
	for(int i=0;i<size;i++)
		cout<<t[i]<<endl;
	return 0;
}