CURVY ROADS AHEAD
All submissions for this problem are available.
On the planet curvy everything is curved. Even light travel in a curve there. They imported a rectangular grid and some very delicious tsquare donuts from nearby planet straighty. The size of grid is m x n and area of a donut is one unit square.
Donuts are placed such that :
For every value of x from 0 to m, a series is created which determines the position of y coordinate on which donut is placed :
Yn = Yn-1 + n
Yn = y coordinate of current donut.
Yn-1 = y-coordinate of previous donut.
n = number of donut for current series.
Y1 is equal to the x coordinate for that particular series.
for eg x=1 donuts are placed at
Y=1, Y=3, Y=6, Y=10 , ...
For x=2 donuts are placed at:
Y=2, Y=4, Y=7 ...
Equation of curve of line of sight at position (0,0) is given by:
On the day of competition contestant are asked to stand at a position (0,b). Now you have to determine how many donuts does that contestant can see.
Note that since area of donut is 1 unit square, if a donut is placed at (h,k) then is visible from
(x,y) such that : ( ( h - 0.5 ) < x <= ( h + 0.5 ) ) and ( ( k - 0.5 ) < y <= ( k + 0.5 ) )
The first line of the input contains an integer T denoting the number of test cases, each test case contains size of grid (MxN) i.e value of M & N followed by values of a & b.
For each test case, output a single line with number of donuts visible to person.
- 1 <= T <= 100
- 1 <= M <= 200
- 1 <= N <= 1000
- 0 <= a <= 1000
- 0 <= b <= 1000
Input: 2 10 10 1 2 25 50 2 5 Output: 5 14
Case 1 : for grid 10x10 and person standing at (0,2) , donuts visible to him are at coordinates
(1,1) , (2,2) , (3,3), (3,5) , (4,9)
Case 2 : for grid 25x50 and person standing at (0,5) , donuts visible to him are at coordinates
(1,1) , (1,3), (3,3), (4,4), (4,6), (5,7), (5,10),
(6,15), (6,20), (7,21), (7,27), (8,35), (8,43), (9,44)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.