Paste will expire never.
- // Меньшиков. Тренировка 7.
- // 7А. Упорядоченные дроби [ordfrac]
- // Лобовая реализация
- // ibelyaev: 24Nov2010
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cstring>
- #include <string.h>
- #include <algorithm>
- #include <stack>
- #include <queue>
- using namespace std;
- int n;
- struct drob
- {
- int ch,zn;
- drob(){}
- drob(int Ch, int Zn)
- {
- ch = Ch;
- zn = Zn;
- }
- void output()
- {
- printf("%d/%d\n", ch, zn);
- }
- };
- bool operator < (const drob &a, const drob &b)
- {
- return (double)a.ch / a.zn < (double)b.ch / b.zn;
- }
- void input()
- {
- cin>>n;
- }
- vector<drob> mas;
- int gcd(int a, int b)
- {
- if (b == 0)
- return a;
- return gcd(b,a%b);
- }
- void solve()
- {
- for (int zn = 2; zn<=n; zn++)
- for (int ch = 1; ch<zn; ch++)
- if (gcd(ch,zn) == 1)
- mas.push_back(drob(ch,zn));
- sort(mas.begin(),mas.end());
- }
- void output()
- {
- for (int i=0;i<mas.size();i++)
- mas[i].output();
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- output();
- return 0;
- }
Editing is locked.