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

. but all the test cases are matching. can anybody help plz??? here goes my code....

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.

Posted: **Tue Oct 11, 2005 5:36 pm**

by **mmij**

thanks ariyan.............got acc

### 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:

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.