10920  Spiral Tap
Moderator: Board moderators
10920  Spiral Tap
Could someone give me test cases, I got wrong answer all the time.
Should I use double or long long int??
But I try to use it, and got TLE, I couldn't find the formula, so I try to simulate it.
And if I use int, my program got wrong answer in 3.0s, but if I use long long int, I got TLE in 10.0s.
I couldn't figure out.
But first, give me some more test cases.
Thanks a lot. ^^
Should I use double or long long int??
But I try to use it, and got TLE, I couldn't find the formula, so I try to simulate it.
And if I use int, my program got wrong answer in 3.0s, but if I use long long int, I got TLE in 10.0s.
I couldn't figure out.
But first, give me some more test cases.
Thanks a lot. ^^
hi,
if you got WA with this problem,
there might be some bugs in your code or algorithm;
my program uses only 32bit integers.
and got AC.
it seems that P < 2^31 (well, P <= SZ^2)
plus output also fits in 32bit integer;
some random test cases below:
output:
if you need more, please post again:)
good luck..
if you got WA with this problem,
there might be some bugs in your code or algorithm;
my program uses only 32bit integers.
and got AC.
it seems that P < 2^31 (well, P <= SZ^2)
plus output also fits in 32bit integer;
some random test cases below:
3 2
1 1
7 2
5 7
5 8
5 9
7 16
7 49
21 137
511 3215
1001 31415
1001 314159
999 987323
2465 1048576
5001 5000
5001 20000000
19999 12857152
50001 123123124
99999 1324859802
99999 100000000
99999 3521578
99999 16515
99999 1
99999 2
0 0
output:
Line = 3, column = 2.
Line = 1, column = 1.
Line = 5, column = 4.
Line = 2, column = 4.
Line = 3, column = 4.
Line = 4, column = 4.
Line = 3, column = 2.
Line = 7, column = 7.
Line = 13, column = 5.
Line = 250, column = 284.
Line = 590, column = 504.
Line = 221, column = 779.
Line = 717, column = 3.
Line = 722, column = 721.
Line = 2495, column = 2536.
Line = 265, column = 1480.
Line = 10452, column = 8207.
Line = 19453, column = 21360.
Line = 40800, column = 68199.
Line = 45001, column = 45000.
Line = 49387, column = 50938.
Line = 49938, column = 50064.
Line = 50000, column = 50000.
Line = 50001, column = 50000.
if you need more, please post again:)
good luck..
Sorry For My Poor English..
i'm getting wrong answer . but all the test cases are matching. can anybody help plz??? here goes my code....
Code: Select all
now got acc
Last edited by mmij on Tue Oct 11, 2005 5:41 pm, edited 2 times in total.

 Learning poster
 Posts: 70
 Joined: Sat Feb 05, 2005 9:38 am
 Location: Gurukul
about 10920
i cant find any suitable way to solve this problem . can some one give me some hints ??? is there formula needed or simulation is the way to go ???
please help
Thanx in advance
please help
Thanx in advance
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
Heh, I just checked my code to see what I did and found this comment:
I used simulation (~5 secs in Java). The only thing I had "optimized" was that I built a table of squares before starting. I would do it without squares now, but it would still go onebyone.
Code: Select all
/* this is slow, but works */

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
i did it O(1) , the upper right corners are all square of consecutive odd numbers(1 9 25 49 81 etc.). i first sqrt the number and get in which interval the number lies(i.e 40 lies in the interval [25, 49) ) four straight lines connect 25 and 49, then it's easy to find in which line, in which position 40 falls. i did sqrt(), so actually my program is not O(1).
ishtiak zaman

the world is nothing but a good program, and we are all some instances of the program

the world is nothing but a good program, and we are all some instances of the program

 New poster
 Posts: 4
 Joined: Wed Jul 14, 2010 12:54 pm
Re:
ayon wrote:i did it O(1) , the upper right corners are all square of consecutive odd numbers(1 9 25 49 81 etc.). i first sqrt the number and get in which interval the number lies(i.e 40 lies in the interval [25, 49) ) four straight lines connect 25 and 49, then it's easy to find in which line, in which position 40 falls. i did sqrt(), so actually my program is not O(1).
Thank you. I got AC using your method.

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 10920  Spiral Tap
I also solved this problem by simulation. Instead of simulating it by one step per action, try to simulate it by n steps per action. n will form a sequence {1, 1, 2, 2, 3, 3, 4, 4, ...}. Good luck!lonelyone wrote:Could someone give me test cases, I got wrong answer all the time.
Should I use double or long long int??
But I try to use it, and got TLE, I couldn't find the formula, so I try to simulate it.
And if I use int, my program got wrong answer in 3.0s, but if I use long long int, I got TLE in 10.0s.
I couldn't figure out.
But first, give me some more test cases.
Thanks a lot. ^^
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?

 New poster
 Posts: 1
 Joined: Wed Jul 03, 2013 8:26 pm
Re: 10920  Spiral Tap
What is the right input size of this problem? Since I got RE, I think it is not 100000 as mentioned in problem statement?

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10920  Spiral Tap
This line from the problem statement is wrong:
SZ is the size of the border of the grid and is an odd number no larger than 100000.
There is a case where SZ is larger than 100000, but not larger than 1000000.
SZ is the size of the border of the grid and is an odd number no larger than 100000.
There is a case where SZ is larger than 100000, but not larger than 1000000.
Check input and AC output for thousands of problems on uDebug!
Re: 10920  Spiral Tap
wook,
Thanks for the test cases.
brianfry713 ,
Thanks for the information. That helped. My approach to the problem required that I switch to using the right data type because of this.
Thanks for the test cases.
brianfry713 ,
Thanks for the information. That helped. My approach to the problem required that I switch to using the right data type because of this.