903 - Spiral of Numbers

[XLDEV]

1. What is a semicolumn?
2. 14 appears twice in the 11x11 table.
3. is there some hidden input/output assumption?

[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...

[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???

[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!

[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.

[IRA]

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.

[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.

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.

[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

[IRA]

Thanks to rio and helloneo!
I know how to solve it.

[sapnil]

I m getting WR plz help me

Code: Select all

.....Removed

Thanks
Sapnil

[Jan]

Try the case below:

Input:

Code: Select all

301413357

Output:

Code: Select all

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

[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...!!

[moody]

Code: Select all

Accepted