Page 1 of 1

903 - Spiral of Numbers

Posted: Fri Sep 29, 2006 8:02 pm
by XLDEV
1. What is a semicolumn?
2. 14 appears twice in the 11x11 table.
3. is there some hidden input/output assumption?

Posted: Fri Sep 29, 2006 11:21 pm
by Jan
1. What is a semicolumn?
I think it should be 'semicolon'. Spelling mistake.
2. 14 appears twice in the 11x11 table.
Another mistake. It should be 24.
3. is there some hidden input/output assumption?
I dont know. I believe there is something wrong. Still checking...

Posted: Sat Sep 30, 2006 4:17 am
by Timo
I believe that something was wonrg with judge input and output. after 77 submission no one got AC??
I've made 2 program,one with formula,and the second one I simulate that spiral. The result of two my program are exactly the same.
I wonder why WE got Wrong Answer???

Posted: Sat Dec 16, 2006 10:19 am
by IRA
Who can show me some good idea or algorithm to speed up the problem.
First,I find the the coordinate of the number.
Second,I use the coordinate to find other number.
I use this method then got TLE.
Thanks in advance!

Posted: Sat Dec 16, 2006 12:01 pm
by rio
I used the same algorithm and got AC with 0.355.

I think your implementation of
function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

Posted: Sat Dec 16, 2006 5:06 pm
by IRA
rio wrote:I used the same algorithm and got AC with 0.355.

I think your implementation of
function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

My step1 & step2 isn't efficient enough.
I can't think how to speed it.
My method is find the number on which loop then step by step to find the
coordinate.
It is too slow.

Posted: Sun Dec 17, 2006 12:09 pm
by rio
IRA wrote:
rio wrote:I used the same algorithm and got AC with 0.355.

I think your implementation of
function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

My step1 & step2 isn't efficient enough.
I can't think how to speed it.
My method is find the number on which loop then step by step to find the
coordinate.
It is too slow.
I used the same method and used binary search for finding the loop.
I think the process of finding the loops takes almost of the time.
So If you are using linear searh for finding the loop, try binary search.

Posted: Sun Dec 17, 2006 2:55 pm
by helloneo
I just did a linear search and got AC with 0.414 sec

function: number -> coordinate
You can get the bounds and only need to search n/4

function: coordinate -> number
You can find a formular and get it directly

Posted: Mon Dec 18, 2006 1:05 pm
by IRA
Thanks to rio and helloneo!
I know how to solve it.

Re: 903 - Spiral of Numbers

Posted: Wed Jun 25, 2008 4:57 am
by sapnil
I m getting WR plz help me

Code: Select all


.....Removed

Thanks
Sapnil

Re: 903 - Spiral of Numbers

Posted: Wed Jun 25, 2008 9:55 pm
by Jan
Try the case below:

Input:

Code: Select all

301413357
Output:

Code: Select all

301343915;301413356;301482805;
301343916;301413357;301482806;
301343917;301413358;301482807;

Re: 903 - Spiral of Numbers

Posted: Thu Oct 09, 2008 2:11 am
by Ron
Why WA ??

Code: Select all

#include<iostream>
#include<string>
using namespace std;
int main(){
	unsigned int i,n,j,k,l,d,m;
	char c[11][27]={
	"2",
	"7;8;9;\n6;1;2;\n5;4;3;",
	"8;9;10;\n1;2;11;\n4;3;12;",
	"1;2;11;\n4;3;12;\n15;14;13;",
	"6;1;2;\n5;4;3;\n16;15;14;",
	"19;6;1;\n18;5;4;\n17;16;15;",
	"20;7;8;\n19;6;1;\n18;5;4;",
	"21;22;23;\n20;7;8;\n19;6;1",
	"22;23;24;\n7;8;9;\n6;1;2;",
	"23;24;25\n8;9;10;\n1;2;11;"};

	while(cin>>n){
		if(n<10){
			puts(c[n]);
			continue;
		}
		i=1;
		while(i*i<n)	i+=2;
		j=i*i;
		k=(i+2)*(i+2);
		l=(i-2)*(i-2);
		if(j==n)
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-2,k-1,k,j-1,j,j+1,l,l+1,j+2);
		else if(j-i+2<n){
			d=j-n;
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,k-d-1,k-d,n-1,n,n+1,l-d,l-d+1,l-d+2);
		}
		else if(j-i+2==n)
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i,k-i+1,k-i+2,n-1,n,n+1,n-2,l-i+3,l-i+4);
		else if(j-i+1==n)
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i-1,k-i,k-i+1,k-i-2,n,n+1,k-i-3,n-1,l-i+3);
		else if(j-i==n)
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i-2,n+1,n+2,k-i-3,n,l-i+3,k-i-4,n-1,l-i+2);
		else if(j-2*i+3<n){
			d=j-n;
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,l-d+3,k-d-4,n-1,l-d+2);
		}
		else if(j-2*i+3==n){
			d=j-n;
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,l-d+3,k-d-4,n-1,n-2);
		}
		else if(j-2*i+2==n){
			d=j-n;
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,n-1,k-d-4,k-d-5,k-d-6);
		}
		else if(j-2*i+1==n){
			d=j-n;
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",n+2,l-d+5,l-d+4,n+1,n,n-1,k-d-4,k-d-5,k-d-6);
		}
		else if(l+(i-2)+2<n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,m+d-3,m+d-4,n+1,n,n-1,j+d+4,j+d+3,j+d+2);
		}
		else if(l+(i-2)+2==n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,m+d-3,n-2,n+1,n,n-1,j+d+4,j+d+3,j+d+2);
		}
		else if(l+(i-2)+1==n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,n+1,n,j+d+1,j+d+4,j+d+3,j+d+2);
		}
		else if(l+(i-2)==n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,m+d-1,n,j+d+1,n+2,n+1,j+d+2);
		}
		else if(l+2<n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,m+d-1,n,j+d+1,m+d,n+1,j+d+2);
		}
		else if(l+2==n){
			d=n-l;
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",n-2,n-1,j+d,m+d-1,n,j+d+1,m+d,n+1,j+d+2);
		}
		else{
			m=(i-4)*(i-4);
			printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",j-1,j,j+1,l,n,j+2,m+1,n+1,j+3);
		}
	}
	return 0;
}

thnx in advance for help...!!

903 - Spiral of Numbers-WA-passed all test cases

Posted: Sat Oct 19, 2013 11:10 pm
by moody

Code: Select all

Accepted