UVA Solution 493 – Rational Spiral – Solution in C, C++

UVA Onilne Judge Solution UVA-Volume 4

UVA Solution 493 – Rational Spiral – Solution in C, C++UVA Online Judge Solution 493 – Rational Spiral | Volume 4

UVA Problem Link – 493 – Rational Spiral code

Problem Name: 493 – Rational Spiral  solve
Problem Number : UVA – 493 – Rational Spiral  solution
Online Judge : UVA Online Judge Solution
Volume: 4
Solution Language : C plus plus

UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list

UVA Solution 493 – Rational Spiral Code in CPP:

#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
set<unsigned long long> S;
int
gcd(int x, int y) {
int
t;
while
(x%y)
t = x, x = y, y = t%y;
return
y;
}

int
x = 0, y = 1, i, j;
int
X[500005], Y[500005];
int
idx = 0;
void
check() {
if
(!x) return;
static
int g, tx, ty;
static
unsigned long long s;
tx = x, ty = y;
g = gcd(abs(y), abs(x));
tx /= g, ty /= g;
if
(tx < 0) ty = -ty, tx = -tx;
X[idx] = tx, Y[idx] = ty;
s = ((unsigned long long)tx)<<32 | (unsigned)ty;
if
(S.find(s) == S.end())
idx++, S.insert(s);
}

int
main() {
for
(i = 2; idx <= 500000; i += 2) {
for
(j = 0; j < i && idx <= 500000; j++, x++)
check();
x--, y--;
for
(j = 0; j < i && idx <= 500000; j++, y--)
check();
y++, x--;
for
(j = 0; j < i && idx <= 500000; j++, x--)
check();
x++, y++;
for
(j = 0; j < i && idx <= 500000; j++, y++)
check();
}

int
n;
while
(scanf("%d", &n) == 1) {
printf("%d / %dn", Y[n], X[n]);
}

return
0;
}

Tags: UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list, UVA 493 – Rational Spiral  code in C, UVA UVA Solution 493 – Rational Spiral – Solution in C, C++ code in C++, UVA solution in C, UVA 493 – Rational Spiral solution

Leave a Reply

Your email address will not be published.