TopCoder problem "BedroomFloor" used in SRM 442 (Division I Level Two)



Problem Statement

    

You have decided to put new floor tiles on your bedroom floor. Consider an infinite pattern made of 1x5 wooden panels as in the picture below. The top-left corner of the picture has coordinates (0, 0). X coordinates increase from left to right, and y coordinates increase from top to bottom.



You have chosen a rectangular area within this infinite pattern that matches the exact size of your bedroom. The top-left corner of the rectangle is at (x1, y1) and the bottom-right corner is at (x2, y2). You want to reproduce this section on your bedroom floor.



The store that sells wooden floor panels only carries 1x5 panels. You can cut panels to get smaller panels, but you can't glue panels together to get larger ones. For example, you can cut a 1x5 panel to get one 1x3 panel and one 1x2 panel, or two 1x2 panel and one 1x1 panel, etc.







The picture above shows the rectangular area (8, 5, 20, 16). You need twenty-three 1x5 panels, six 1x2 panels and five 1x1 panels. You have to buy total of 27 panels to make these.



You are given ints x1, y1, x2 and y2. Return the minimum number of panels you must buy at the store to produce the pattern in the given rectangular area.

 

Definition

    
Class:BedroomFloor
Method:numberOfSticks
Parameters:int, int, int, int
Returns:long
Method signature:long numberOfSticks(int x1, int y1, int x2, int y2)
(be sure your method is public)
    
 

Notes

-You can throw away any part of a panel that you don't need.
 

Constraints

-x1, y1, x2 and x2 will be between 0 and 1000000, inclusive.
-x2 will be strictly greater than x1.
-y2 will be strictly greater than y1.
 

Examples

0)
    
0
0
5
5
Returns: 5
This rectangular area contains five 1x5 panels.
1)
    
0
0
10
2
Returns: 5
This rectangular area contains two 1x5 panels and five 1x2 panels. We have to buy 5 panels to make these.
2)
    
2
2
8
8
Returns: 12
This rectangle contains twelve 1x3 panels. We can't glue panels together, so we have to buy 12 panels.
3)
    
8
5
20
16
Returns: 27
The example depicted in the problem statement.
4)
    
0
0
1000000
1000000
Returns: 200000000000

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4810

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13750&pm=4810

Writer:

kalinov

Testers:

PabloGilberto , ivan_metelsky

Problem categories:

Greedy, Math