## 10920 - Spiral Tap

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

Moderator: Board moderators

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

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

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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..
Sorry For My Poor English..

mmij
New poster
Posts: 10
Joined: Mon Jul 11, 2005 7:13 am
Location: PlanetEarth
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.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul
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.
Some Love Stories Live Forever ....

mmij
New poster
Posts: 10
Joined: Mon Jul 11, 2005 7:13 am
Location: PlanetEarth
thanks ariyan.............got acc

Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada
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
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

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

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10920 - Spiral Tap

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!
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

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

brianfry713
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.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### 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.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.