1915 - Funny spiral

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=1915

[ReynaldoGil]

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);
	}
}

[laygr]

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

-Lay

[ReynaldoGil]

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

[facug91]

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.