1915 - Funny spiral
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.
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.
- 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[2][4] = {{ 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);
}
}
Re: 1915 - Funny spiral
Hi,
I'm having the same trouble as you. Did you were able of solving it?
-Lay
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...
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.
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.
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;
}