### PROBLEM LINK:

Author: Devendra Agarwal

Tester: Anudeep Nekkanti

Editorialist: Amit Pandey

### DIFFICULTY:

Cakewalk.

### PREREQUISITES:

Basic geometry, recursion.

### PROBLEM:

Find the maximum number of squares of size 2 imes2 that can be fitted in a right angled isosceles triangle of base B. All sides of the square must be parallel to both base and height of the isosceles triangle.

### QUICK EXPLANATION:

As B<=1000, we can pre-compute the output for all the test cases, and report the answer in O(1) time for each of the query.

### EXPLANATION:

First consider the right angle triangle \Delta XYZ, where YZ is the base of triangle. Suppose length of the base is B. If we consider the position of first square with the vertex Y, we will have (B/2 - 1) squares in the base, and we will be left with another isosceles right angle triangle having base length (B-2).

Let f(B) = Number of squares which can be fitted in triangle having base length B.

f(B) = (\frac{B}{2} -1) + f(B-2)

The given time limit is sufficient even if we calculate f(B) using the given recursion, and use memoization. Later we can answer each query in O(1) time. We can do it for even and odd numbers separately with the base case f(1) = f(2) = f(3) = 0.

The given recursion can be solved in following manner.

With conditions, f(1) = f(2) = 0

f(B) = \frac{B}{2} + (\frac{B}{2} - 1) + (\frac{B}{2} -2) + \cdots + 1.

f(B) = Sum of first \frac{B}{2} natural numbers.

Lets call M = \frac{B}{2}

f(B) = \frac {M imes (M-1)}{2}

You can notice that answer for 2N and 2N+1 will be the same.

### Solution:

Setter’s solution can be found here

Tester’s solution can be found here