Prime PatternProblem code: PRIMPATT |
All submissions for this problem are available.
The problem statement (Input Para) has been updated at 11:00 pm Indian Standard Time on 1st June, 2010.
There is a very large field, colored white and divided into squares. There is a coordinate system attached to the field: y-axis goes from south to north and x-axis goes from west to east. Sides of the squares are parallel to the axes. There is a robot in the (0, 0) square. Robot starts to move in spiral as depicted. First it moves one step east and one step north. Then two steps west and two steps south. Then three steps east and three steps north, four steps west and four steps south and so on. It moves to a new square with each step. As it moves it counts squares it passes and, if the number of the square is the prime number, then the robot fills this square with black color. The (0, 0) square has the number 0. Given the coordinates of a square you are to calculate the distance from this square to the nearest to it black square. For two squares with coordinates (x1, y1) and (x2, y2) the distance between those squares is |x1-x2|+|y1-y2|.
Input
Input file consists of a set of tests. The first line of the file is number T – the number of tests (T <= 500). Following T lines contains two integers each separated with a space: x and y – the coordinates of the square (-2000001 < x < 2000001, -2000001 < y < 2000001).
Output
For each coordinate pair in the input file you are to output the distance between this square and the nearest to it black square.
Example
Input:
8
0 0
1 0
1 1
0 1
3 3
-3 -3
-1 2
0 -3
Output:
1
1
0
0
1
1
2
2
| Author: | spooky |
| Date Added: | 3-05-2010 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Is there a diagram missing?
Is there a diagram missing?
Diagram Missing !
Diagram Missing !
pls add the diagram!!! cant
pls add the diagram!!!
cant solve without it...
The link to the image is
The link to the image is broken, and should be https://www.spoj.pl/content/spookycookie:spiral . (And incase your browser refuses to open it, save it as a png).
What are the bounds on T?
What are the bounds on T?
T is about 500
T is about 500
x-axis goes from south to
x-axis goes from south to north and y-axis goes from west to east?
Is that correct? based on the picture and the example input , i see the x-asis goes from west to east.
since the input 1 0 result to 1
-2000001<x<20000001
-2000001<x<20000001 OR -2000001<x<2000001 (five zeros or six). is that a mistake?
@Nitin: Good eye. That
@Nitin: Good eye. That should be 2000001 (two million and one)
Are we supposed to consider
Are we supposed to consider squares outside of the bounds on x and y when computing the shortest distance? For example, given (2000000, 2000000) as input; say (20000001, 2000000) had a prime number, should we output 1 or is this square considered "unreachable"?
@Ben Cousins: yes, the
@Ben Cousins: yes, the sqaures outside those bounds are counted. The robot never stops, and the field is actually inifinte.
@Admin -- My timings are not
@Admin -- My timings are not getting updated in right panel when I resubmitted the code.
Here on codechef it doesn't
Here on codechef it doesn't :P
@Admin :I resubmitted an AC
@Admin :
I resubmitted an AC code with better runtime, but still in problem's ranklist,
it's showing first AC code's runtime.
comment removed by admin
comment removed by admin
@ritesh discussing test cases
@ritesh discussing test cases is against the rules; you will be disqualified if you continue to do so.
can anyone tell any way of
can anyone tell any way of declaring a 2d array of size,say array[4100000][4100000] without exceeding range limit in c or c++..so that if a pt (2000001,2000001) can be covered?Plz help.
Can anyone tell any way of
Can anyone tell any way of declaring a 2d array of size,say array[4100000][4100000] without exceeding range limit in C or C++?
No such way exists ! You are
No such way exists ! You are using too much memory
@abhijith: I just wish
@abhijith: I just wish brilliant people like Akhilesh come to topcoder, especially after seeing the speeds with which he got the problems accepted! Guess it will be nice to see people like him beat Petr and ACRush by a huge margin! :D :D
Can it be done by a 2D array
Can it be done by a 2D array or some other data st.?
Someone plz help in explaing how to make the robo move in its path.Using 2D array would have been a cakewalk but its consuming too much space.What to do?
Please don't ask for hints
Please don't ask for hints during the contest - wait until after the contest has finished.
@all http://www.codechef.com/
@all
http://www.codechef.com/users/akhilesh890
@abhijith:
@abhijith: http://www.codechef.com/users/brightsparks
Have a look at this one too! :)
Hi everyone, I would like to
Hi everyone,
I would like to know how you deal with large numbers in C++. For example if you are given the coordinates (100000, 100000) the number which comes in this square is greater than 10^10 which cannot be stored with the datatype long int. I am getting the right answers for small numbers but I have a problem with large numbers. Please give me some advice.... Thanks..
can any one tell me how to
can any one tell me how to compare two floating type variables equality(==) condition doesn't always works
@Archit: I don't know why
@Archit: I don't know why you would need floating point operations for this problem, but if your code could tolerate some errors, you could replace a==b by abs(a-b) < EPS for some small EPS (like 1e-6 or so).