/*
ID: himuhas1
TASK: frac1
LANG: C++
link: http://cerberus.delos.com:790/usacoprob2?a=0Hi6SPQOgMg&S=frac1
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define gi(a) sf("%d", &a)
#define gi2(a, b) sf("%d%d", &a, &b)
#define gi3(a, b, c) sf("%d%d%d", &a, &b, &c)
#define gi4(a, b, c, d) sf("%d%d%d%d", &a, &b, &c, &d)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read freopen("input.txt", "r", stdin)
#define write freopen("output.txt", "w", stdout)
using namespace std;
vector<paii>fractions;
bool comp(paii a, paii b)
{
return a.fr*b.sc < a.sc * b.fr;
}
int gcd(int a, int b)
{
if(a%b == 0) return b;
return gcd(b, a%b);
}
int main()
{
freopen("frac1.in", "r", stdin);
freopen("frac1.out", "w", stdout);
int n;
paii frac;
gi(n);
fractions.pb(MP(0,1));
for(int i=1; i<=n; i++)
{
for(int j=i; j<=n; j++)
{
if(gcd(i, j) > 1 ) continue;
frac.fr = i;
frac.sc = j;
fractions.pb(frac);
}
}
sort(all(fractions), comp);
loop(i, SZ(fractions))
{
pf("%d/%d\n", fractions[i].fr, fractions[i].sc);
}
return 0;
}
Category Archives: Sorting
(UVa) 10258 – Contest Scoreboard
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1199
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
bool attendedteam[101];
struct DATA{
int id;
ll total;
ll tried[10];
bool solved[10];
int totalsolved;
};
DATA teamdata[101];
bool comp(DATA a, DATA b)
{
if(b.totalsolved > a.totalsolved)
{
return false;
}
else if(a.totalsolved == b.totalsolved)
{
if(a.total < b.total)
{
return true;
}
else
{
return a.id < b.id;
}
}
else
{
return true;
}
}
int main()
{
bool blank = false;
FOR(i, 1, 101)
{
teamdata[i].id = i;
}
int kases;
getint(kases);
cin.ignore();
cin.ignore();
stringstream ss;
string str;
int teamid, probid, timesplit;
char verdict;
while(kases--)
{
if(blank) pf("\n");
blank = true;
mem(attendedteam, 0);
FOR(i, 1, 101)
{
teamdata[i].total = 0;
teamdata[i].totalsolved = 0;
FOR(j, 1, 10)
{
teamdata[i].tried[j] = 0;
teamdata[i].solved[j] = 0;
}
}
while(true)
{
getline(cin, str);
if(SZ(str) == 0) break;
ss.clear();
ss<<str;
ss>>teamid>>probid>>timesplit>>verdict;
attendedteam[teamid] = 1;
if(teamdata[teamid].solved[probid] == 0)
{
if(verdict == 'C' )
{
teamdata[teamid].totalsolved++;
teamdata[teamid].solved[probid] = 1;
teamdata[teamid].total += teamdata[teamid].tried[probid] + timesplit;
}
else if(verdict == 'I')
{
teamdata[teamid].tried[probid] += 20;
}
}
}
vector<DATA>v;
FOR(i, 1, 101)
{
if(attendedteam[i])
{
v.pb(teamdata[i]);
}
}
sort(all(v), comp);
int len = SZ(v);
loop(i, len)
{
pf("%d %d %lld\n", v[i].id, v[i].totalsolved, v[i].total);
}
}
return 0;
}
(CodeForces) C. k-Multiple Free Set
0
/*
user: hasib
link: http://codeforces.com/contest/275/problem/C
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define MAXX 100002
using namespace std;
int number_of_elements;
ll nums[MAXX];
ll k;
int low, high, mid;
bool search(ll n)
{
low = 0;
high = number_of_elements - 1;
while(low <= high)
{
mid = (low+high)/2;
if(nums[mid] == n)
{
break;
}
else if(n < nums[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
if(low <= high)
return true;
else return false;
}
int main()
{
getint(number_of_elements);
cin>>k;
loop(i, number_of_elements)
{
getint(nums[i]);
}
sort(nums, nums + number_of_elements);
int taken = 0;
ll a;
map<int, bool>visited;
loop(i, number_of_elements)
{
if( visited[nums[i]] == 0 )
{
a = nums[i];
if(search(a*k))
{
if(search(a*k*k))
{
visited[a*k] = 1; //nished
taken++;
}
else
{
visited[a*k] = 1;
taken++;
}
}
else
{
taken++;
}
}
}
cout<<taken<<endl;
return 0;
}
(UVa) 103 – Stacking Boxes
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=39
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
struct DATA{
int ara[11];
char pos;
};
DATA boxes[31];
int number_of_boxes, count_dimentions;
int dir[31];
int dp[31];
bool compare(DATA a, DATA b)
{
loop(i, count_dimentions)
{
if(a.ara[i] > b.ara[i])
{
return false;
}
}
return true;
}
bool test(DATA a, DATA b)
{
loop(i, count_dimentions)
{
if(a.ara[i] >= b.ara[i])
{
return false;
}
}
return true;
}
int longest(int u)
{
int &ret = dp[u];
if( ret != -1) return ret;
int maxi = 0;
for(int v=u+1; v<number_of_boxes; v++)
{
if(test(boxes[u], boxes[v]))
{
if(maxi < longest(v))
{
maxi = longest(v);
dir[u] = v;
}
}
}
return ret = maxi + 1;
}
int main()
{
int LIS;
int from;
while(scanf("%d %d", &number_of_boxes, &count_dimentions) == 2)
{
loop(i, number_of_boxes)
{
boxes[i].pos = i;
loop(j, count_dimentions)
{
getint(boxes[i].ara[j]);
}
}
loop(i, number_of_boxes)
{
sort(boxes[i].ara, boxes[i].ara+count_dimentions);
}
sort(boxes, boxes+number_of_boxes, compare);
mem(dp, -1);
mem(dir, -1);
LIS = -1;
loop(i, number_of_boxes)
{
if(longest(i) > LIS)
{
LIS = longest(i);
from = i;
}
}
printf("%d\n", LIS);
while(dir[from] != -1)
{
printf("%d ", boxes[from].pos+1);
from = dir[from];
}
printf("%d\n", boxes[from].pos+1);
}
return 0;
}
(UVa) 11239 – Open Source
0
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2180
*/
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
struct Team{
string projectName;
int students;
};
map<string, int>studentVSproject;
Team project[102];
bool compare(Team a, Team b)
{
if(a.students > b.students) return true;
if(a.students < b.students) return false;
if(a.projectName < b.projectName) return true;
return false;
}
int main()
{
string input;
int temp;
int project_iterator = 0;
while(getline(cin, input))
{
if(input == "0")
{
break;
}
if( input != "1")
{
if('A' <= input[0] && input[0] <='Z' )
{// it's team name;
project[project_iterator].projectName = input;
project[project_iterator].students = 0;
project_iterator++;
}
else
{//it's userid
temp = studentVSproject[input];
if(temp == 0)
{//new student who has not yet submit anywhere
studentVSproject[input] = project_iterator;
project[project_iterator - 1].students++;
}
else if(temp < 150 && temp != project_iterator)
{
project[temp-1].students--;
studentVSproject[input] = 500;
}
}
}
else
{
sort(project, project+project_iterator, compare);
for(int i=0; i<project_iterator; i++)
{
printf("%s %d\n", project[i].projectName.c_str(), project[i].students);
}
project_iterator = 0;
studentVSproject.clear();
}
}
return 0;
}
(UVa) 10107 – What is the Median?
0
/*
user: php
time: 0.024 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1048
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#define loop(i, n) for(int i=0; i<n; i++)
#define loopfrom1(i, n) for(int i=1; i<n; i++)
#define mem(array, value) memset(array, value, sizeof(array))
#define MIN(a, b) (a<b?a:b)
#define MAX(a, b) (a>b?a:b)
#define pb(a) push_back(a)
#define SZ size()
#define getint(n) scanf("%d", &n)
#define pi acos(-1.0)
#define inf 536870912 // 1<<29
#define debug cout<<"ok"<<endl
#define ll long long int
using namespace std;
int main()
{
int n;
int a[10001];
int i;
ll sum;
int position=0;
a[0] = -1;
while(getint(n) == 1)
{
for(i=position; i>-1; i--)
{
if(a[i] <= n)
{
a[i+1] = n;
break;
}
else
{
a[i+1] = a[i];
}
}
position++;
if(position % 2 == 1)
{
printf("%d\n", a[(position+1)/2] );
}
else
{
int g1 = a[position/2];
int g2 = a[position/2 + 1];
sum = (g1 + g2) / 2;
printf("%lld\n", sum);
}
}
return 0;
}
UnLucky Codes 