négyzetek
Legfeljebb hány darab K
oldalhosszúságú négyzetet pakolhatunk be - átfedés nélkül - egy derékszögű háromszög belsejébe,
melynek befogói A
és B
hosszúak? Minden négyzet valamely oldalának párhuzamosnak
kell lenni valamelyik befogóval!
Példa
A fenti ábra a K=2,A=7,B=12
eset megoldása (M=6
).
A bemenet specifikációja
T
K1 A1 B1
...
KT AT BT
Az első sor a megoldandó esetek T
száma, majd T
sor következik, a szóközzel elválasztott
Ki,Ai,Bi
értékekkel.
1 ≤ T ≤ 100
1 ≤ Ki ≤ 100
1 ≤ Ai,Bi ≤ 104 (i=1...T)
A kimenet specifikációja
M1
...
MT
T
sor a keresett Mi (i=1...T)
értékekkel.
1. példa bemenet
1
2 7 12
letöltés szöveges állományként
1. példa kimenet
6
letöltés szöveges állományként
2. példa bemenet
4
2 10 10
2 3 3
17 1717 17171
71 7171 71717
letöltés szöveges állományként
2. példa kimenet
10
0
50500
50500
letöltés szöveges állományként