Back
Close
  • 1757

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

There is a rectangle of given width w and height h,

On the width side, you are given a list of measurements.
On the height side, you are given another list of measurements.

Draw perpendicular lines from the measurements to partition the rectangle into smaller rectangles.

In all sub-rectangles (include the combinations of smaller rectangles), how many of them are squares?


Example

w = 10
h = 5
measurements on x-axis: 2, 5
measurements on y-axis: 3

   ___2______5__________ 
| | | |
| | | |
3|___|______|__________|
| | | |
|___|______|__________|

Number of squares in sub-rectangles = 4 (one 2x2, one 3x3, two 5x5)
Input
Line 1: Integers w h countX countY, separated by space
Line 2: list of measurements on the width side, countX integers separated by space, sorted in asc order
Line 3: list of measurements on the height side, countY integers separated by space, sorted in asc order
Output
Line 1: the number of squares in sub-rectangles created by the added lines
Constraints
1 ≤ w, h ≤ 20,000
1 ≤ number of measurements on each axis ≤ 500
Example
Input
10 5 2 1
2 5
3
Output
4

A higher resolution is required to access the IDE