Page 1 of 1

10920 - Spiral Tap

Posted: Sun Oct 02, 2005 2:30 pm
by lonelyone
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. ^^

Posted: Sun Oct 02, 2005 2:46 pm
by wook
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:
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..

Posted: Mon Oct 10, 2005 9:12 pm
by mmij
i'm getting wrong answer :cry: . but all the test cases are matching. can anybody help plz??? here goes my code....

Code: Select all

now got acc

Posted: Tue Oct 11, 2005 12:44 pm
by Raj Ariyan
Hi mmij,
Your code is ok. U use %lld for taking input but u didnt write this when u print the output ( Last Line). Just replace all %d to %lld. Thanks. Good Luck. :D

Posted: Tue Oct 11, 2005 5:36 pm
by mmij
thanks ariyan.............got acc :wink:

about 10920

Posted: Sun Aug 27, 2006 5:39 am
by Riyad
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

Posted: Sun Aug 27, 2006 10:33 am
by Darko
Heh, I just checked my code to see what I did and found this comment:

Code: Select all

/* this is slow, but works */
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 one-by-one.

Posted: Sun Aug 27, 2006 7:46 pm
by ayon
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).

Re:

Posted: Wed Jul 21, 2010 4:04 am
by dubukuangye
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.

Re: 10920 - Spiral Tap

Posted: Sun Mar 27, 2011 5:11 am
by DD
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. ^^
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!

Re: 10920 - Spiral Tap

Posted: Tue Jan 07, 2014 8:45 am
by izharishaksa
What is the right input size of this problem? Since I got RE, I think it is not 100000 as mentioned in problem statement?

Re: 10920 - Spiral Tap

Posted: Wed Jan 15, 2014 12:48 am
by brianfry713
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.

Re: 10920 - Spiral Tap

Posted: Tue Mar 11, 2014 2:30 pm
by uDebug
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.