I DONT SEE IT STRAIGHT
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 square 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:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, PERL, SCM qobi, LUA, JS, PERL6|
Fetching successful submissions
If you are still having problems, see a sample solution here.