DMOPC '19 Contest 5 P3 - Captivating Construction Challenge

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 128M

Problem types

Andrew is a quirky child with an obsessive compulsion for drawing rectangles. In fact, he likes drawing rectangles so much that instead of paying attention in class, he spends his time drawing rectangles! The blank grid paper which Andrew draws rectangles on has H horizontal lines spaced one unit apart intersecting V vertical lines, also spaced one unit apart. Every second, Andrew connects four lattice points on the paper to draw a rectangle that he has not yet drawn. Until he has drawn all of the rectangles that he can possibly draw in this manner, he will continue to be distracted in class. Can you determine how many seconds Andrew will be drawing rectangles for?

Python users are recommended to use PYPY over CPython. There is a significant performance increase.

Input Specification

The first line contains two space-separated integers, H and V, as described in the problem statement.

Output Specification

On a single line, output the answer to Andrew's question.


In all subtasks,
2 \leq H, V \leq 2\,000

Subtask 1 [20%]

2 \leq H, V \leq 8

Subtask 2 [80%]

No additional constraints.

Sample Input 1

3 3

Sample Output 1


Explanation of Sample 1

Note that rectangles are not necessarily axis-aligned.

Sample Input 2

7 8

Sample Output 2



There are no comments at the moment.