TORONTO KIDS COMPUTER CLUB | PMCA Friday 19:00 Python Homework 20.06.26.
17826
post-template-default,single,single-post,postid-17826,single-format-standard,ajax_fade,page_not_loaded,,qode-theme-ver-7.6.2,wpb-js-composer js-comp-ver-6.10.0,vc_responsive

PMCA Friday 19:00 Python Homework 20.06.26.

02 Jul PMCA Friday 19:00 Python Homework 20.06.26.

Question:
Alice took a clean sheet of paper and drew h horizontal and v vertical lines onto the paper.

The horizontal lines have y-coordinates y1,,yh, and the vertical lines have x-coordinates x1,,xv.

Given these coordinates, count the number of squares that appeared on the paper.

(The whole boundary of the square has to be drawn. The inside of the square does not have to be empty.)

Input

The first line of input contains the integers h and v (0h,v1500).

The second line of input contains a strictly increasing sequence consisting of h space-separated integers: y1,,yh.

The third line of input contains a strictly increasing sequence consisting of v space-separated integers: x1,,xv.

All horizontal and vertical coordinates are between 0 and 230, inclusive.

Output

Output a single line with a single integer: the total number of squares.

Sample Input
3 4 0 1 3 1 2 4 8

Sample Output
3

Explanation:
In the example there is one 1×1 square, one 2×2 square, and one 3×3 square.

Hint:
You can consider all the distances between horizontal lines or vertical lines are potential square sides.
for example, if the distance between 2 horizontal lines is 5, as long as you can find the distance between 2 vertical lines is also 5, then you can form a squre.

You can put all the distances between horizontal lines into a list.

No Comments

Sorry, the comment form is closed at this time.