Programozás‎ > ‎Feladatok‎ > ‎

Tojás dobálás


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