903 - Spiral of Numbers

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
XLDEV
New poster
Posts: 3
Joined: Fri Sep 29, 2006 7:58 pm

903 - Spiral of Numbers

Post by XLDEV » Fri Sep 29, 2006 8:02 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Sep 29, 2006 11:21 pm

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...
Ami ekhono shopno dekhi...
HomePage

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Sep 30, 2006 4:17 am

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???
"Life is more beautiful with algorithm"

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Sat Dec 16, 2006 10:19 am

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!

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Dec 16, 2006 12:01 pm

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
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Sat Dec 16, 2006 5:06 pm

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Dec 17, 2006 12:09 pm

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.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Dec 17, 2006 2:55 pm

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
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Mon Dec 18, 2006 1:05 pm

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

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 903 - Spiral of Numbers

Post by sapnil » Wed Jun 25, 2008 4:57 am

I m getting WR plz help me

Code: Select all


.....Removed

Thanks
Sapnil
Last edited by sapnil on Thu Jul 03, 2008 7:02 pm, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 903 - Spiral of Numbers

Post by Jan » Wed Jun 25, 2008 9:55 pm

Try the case below:

Input:

Code: Select all

301413357
Output:

Code: Select all

301343915;301413356;301482805;
301343916;301413357;301482806;
301343917;301413358;301482807;
Ami ekhono shopno dekhi...
HomePage

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 903 - Spiral of Numbers

Post by Ron » Thu Oct 09, 2008 2:11 am

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
New poster
Posts: 9
Joined: Tue Sep 24, 2013 2:19 am

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

Post by moody » Sat Oct 19, 2013 11:10 pm

Code: Select all

Accepted

Post Reply

Return to “Volume 9 (900-999)”