## 1915 - Funny spiral

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender:  ### 1915 - Funny spiral

ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: ### Re: 1915 - Funny spiral

I have tried this code, and I think my mistake is in the presicion, so I ask for someone to find a test case where it gives WA, cos i'm getting WA, and I checked it with another AC code and the output for several (10000) random inputs gives correct results, thanks in advance...

Code: Select all

``````#include <cstdio>
#include <cmath>
typedef long long i64;
int d = {{ 0, 0, 2, 2 }, { 0, 1, 1, 2 }} ;
inline i64 cal(int n, int c) {
return 2 * (n / 4) + d[c][n % 4];
}
int main() {
int t; scanf("%d", &t);
while(t--){
i64 L; scanf("%lld", &L);
if(L==0){
printf("0.00\n"); continue;
}
int n = ceil((sqrt(8 * L + 1) - 1) / 2);
i64 x, y;
i64 Ln = (i64) n * (n - 1) / 2;
if (n % 2 == 0){
x = cal(n, 0); y = cal(n - 1, 1);
x = x - n + L - Ln;
}
else {
x = cal(n - 1, 0); y = cal(n, 1);
y = y - n + L - Ln;
}
double ans = n % 2 == 0 ? sqrt(x * x + y * y + x * y) :	sqrt(x * x + y * y - x * y);
printf("%.2lf\n", ans);
}
}
``````

laygr
Posts: 4
Joined: 6 years ago
Gender: ### Re: 1915 - Funny spiral

Hi,
I'm having the same trouble as you. Did you were able of solving it?

-Lay

ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: ### Re: 1915 - Funny spiral

yeah, I was, but by using another approach cos that one failed I don't remember why...

facug91
Posts: 12
Joined: 6 years ago
Gender: ### Re: 1915 - Funny spiral

I have a similar problem. I've made this solution, it passed all the tests I could imagine, and then made random tests, and they passed too. So I don't know why I still get WA. If someone have some tricky test case, or see some problem on my code, I'll be greatful.

Code: Select all

``````#include <cstdio>
#include <cmath>

using namespace std;

long long t, L, l, Li, Lj, seg, cor, mid, ang;
double ans;

long long binary_search () {

long long begin = 1, end = (L/2 > 2000000000ll)?2000000000ll:L/2, middle = begin+(end+begin)/2, aux;
while (begin < end) {
middle = begin + (end-begin)/2;
aux = (middle*(middle+1))/2;
if (aux == L) return (middle+1);
else if (aux < L) begin = middle+1;
else end = middle-1;
}

middle = begin + (end-begin)/2;
aux = (middle*(middle+1))/2;
while (aux > L) {
middle--;
aux = (middle*(middle+1))/2;
}

return (middle+1);

}

int main() {

scanf("%lld", &t);

while (t--) {

scanf("%lld", &L);

if (L == 1) {
ans = 1.0;
} else {

l = binary_search();
Li = (l*(l-1))/2;

if (l % 4 == 1) {

seg = l/2;

if (Li+seg == L) {
ans = (double) seg;
} else {

if (Li+seg < L) {
ang = 1;
cor = L - (Li + seg);
} else {
ang = -1;
cor = (Li + seg) - L;
}

ans = sqrt((double)((seg*seg+cor*cor)-(seg*cor*ang)));

}

} else if (l % 4 == 2) {

if (l==2) {
if (L==2) ans = 1.73;
else if (L==3) ans = 2.65;
} else {

seg = l/2;
mid = (l-2)/2;

if (Li+mid == L) {
ans = (double) seg;
} else {

if (Li+mid < L) {
ang = -1;
cor = L - (Li + mid);
} else {
ang = 1;
cor = (Li + mid) - L;
}

ans = sqrt((double)((seg*seg+cor*cor)-(seg*cor*ang)));

}

}

} else if (l % 4 == 3) {

seg = (l+1)/2;
mid = l/2;

if (Li+mid == L) {
ans = (double) seg;
} else {

if (Li+mid < L) {
ang = 1;
cor = L - (Li + mid);
} else {
ang = -1;
cor = (Li + mid) - L;
}

ans = sqrt((double)((seg*seg+cor*cor)-(seg*cor*ang)));

}

} else if (l % 4 == 0) {

seg = l/2;

if (Li+seg == L) {
ans = (double) seg;
} else {

if (Li+seg < L) {
ang = -1;
cor = L - (Li + seg);
} else {
ang = 1;
cor = (Li + seg) - L;
}

ans = sqrt((double)((seg*seg+cor*cor)-(seg*cor*ang)));

}

}
}

printf("%.2lf\n", ans);

}

return 0;
} ``````
I don't think it might be a precision problem, because the only calculation I make with double, is sqrt(), and once per test case.