Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

squares

What is the maximal number of squares with side lengths of K that can be packed - without overlaps - into a right triangle whose legs are of lengths A and B? For each square one of its side must be parallel with one of the triangles leg!

Example

In the figure above one can see the solution (M=6) in the case of K=2,A=7,B=12.

Input Specification


T
K1 A1 B1
...
KT AT BT

The first line is the number cases to be solved. Then T lines follow, each of which with three space separated numbers Ki,Ai,Bi.

 
  1 ≤ T ≤ 100 
  1 ≤ Ki ≤ 100
  1 ≤ Ai,Bi ≤ 104 (i=1...T)
 

Output Specification


M1
...
MT

T lines with the required values of Mi (i=1...T).

Sample Input 1

  1. 1
  2. 2 7 12
download as text file

Sample Output 1

  1. 6
download as text file

Sample Input 2

  1. 4
  2. 2 10 10
  3. 2 3 3
  4. 17 1717 17171
  5. 71 7171 71717
download as text file

Sample Output 2

  1. 10
  2. 0
  3. 50500
  4. 50500
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019