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

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

10920 - Spiral Tap

Post by lonelyone » Sun Oct 02, 2005 2:30 pm

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

Post by wook » Sun Oct 02, 2005 2:46 pm

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

Post by mmij » Mon Oct 10, 2005 9:12 pm

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

Post by Raj Ariyan » Tue Oct 11, 2005 12:44 pm

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
Some Love Stories Live Forever ....

mmij
New poster
Posts: 10
Joined: Mon Jul 11, 2005 7:13 am
Location: PlanetEarth

Post by mmij » Tue Oct 11, 2005 5:36 pm

thanks ariyan.............got acc :wink:

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

about 10920

Post by Riyad » Sun Aug 27, 2006 5:39 am

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

Post by Darko » Sun Aug 27, 2006 10:33 am

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

Post by ayon » Sun Aug 27, 2006 7:46 pm

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:

Post by dubukuangye » Wed Jul 21, 2010 4:04 am

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

Post by DD » Sun Mar 27, 2011 5:11 am

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

Post by izharishaksa » Tue Jan 07, 2014 8:45 am

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

Post by brianfry713 » Wed Jan 15, 2014 12:48 am

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!

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

Re: 10920 - Spiral Tap

Post by uDebug » Tue Mar 11, 2014 2:30 pm

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.

Post Reply

Return to “Volume 109 (10900-10999)”