10920 - Spiral Tap

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

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

[mmij]

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

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

[mmij]

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

[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

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

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

[dubukuangye]

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.

[DD]

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!

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

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

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