Egy F emeletes épületben vagyunk (a legalsó emelet sorszáma 1) és van nálunk egy csomó egyforma tojás, mindegyik külön védőcsomagolásban. Az épület minden emeletéről tudni szeretnénk, hogy ha onnan kidobunk egy tojást, eltörik-e. Tudjuk, hogy ha egy tojás az i. emeltről kidobva eltörik, akkor minden tojás eltörik minden j >= i sorszámú emeletről kidobva. Hasonlóan: ha az i. emeltről dobva nem törik el egy tojás, akkor semelyik j <= i sorszámú emeltről dobva sem törik el egyik tojás sem.
Legyen Megoldható(F, D, B) akkor és csak akkor igaz, ha létezik olyan algoritmus, ami egy F emeletes épület minden emeletére eldönti, hogy onnan kidobva eltörik-e a tojás, ha
- legfeljebb D-szer dobhatunk;
- és legfeljebb B tojást törhetünk el.
Feltehetjük, hogy legalább D tojás van nálunk.
Feladat
Írjunk programot, ami kiszámolja, hogy ha Megoldható(F,D,B) igaz, akkor
- legfeljebb mekkora F'-re igaz
Megoldható(F',D,B);
Ha ez az érték legalább
232
(=4294967296) lenne, akkor F'-t -1-re kell állítani.
( Máshogy: F' = -1 akkor és csak akkor, ha Megoldható(232, D, B). ) - melyik az a legkisebb D', amire
Megoldható(F,D',B); - melyik az a legkisebb B', amire
Megoldható(F,D,B').
Bemenet
A bemenet első sora a tesztesetek N számát adja meg. Ezután N sor következik, mindegyikben három szám: F D és B, amelyekről
tudjuk, hogy Megoldható(F,D,B) igaz.
Kimenet
Minden tesztesethez egy sort kell kiírni, ami F', D' és B' értékét tartalmazza.
Méretek
1 <= N <= 100
Kis bemenet
1 <= F <= 100
1 <= D <= 100
1 <= B <= 100
Nagy bemenet
1 <= F <= 2000000000
1 <= D <= 2000000000
1 <= B <= 2000000000
Példa
| Bemenet |
Kimenet |
2
3 3 3
7 5 3 | Case #1: 7 2 1
Case #2: 25 3 2
|
Tesztadatok
Címkék
A feladat forrása: Google Code Jam, gyakorló feladat
Algoritmusok:
megoldás
2004-2016 BDG algoritmus szakkör