Mária új munkahelye a Borzasztó  Darabok Gyára, ahol céltáblákat kell készítenie. A céltáblák koncentrikus körökből (körgyűrűkből) állnak, amelyek felváltva feketék és fehérek.

 

Mária kap T ml  fekete festéket, amiből 1 cm vastag gyűrűket fest. (Tehát egy fekete gyűrű külső és belső sugarának különbsége 1 cm.)

A legbelső fehér kör sugara R cm. Mária a következőt ismételgeti:

A fehér gyűrű csak üres hely, ahhoz nem kell festék. Egy ml festék éppen π cm² terület lefestéséhez elég.  

Írjunk programot, ami megadja, hogy Mária legfeljebb hány fekete gyűrűt tud festeni. (Mária csak teljes gyűrűket festhet, és minden tesztesetben legalább egy fekete gyűrűt meg tud festeni.

A bemenet első sora tesztesetek N számát tartalmazza, majd soronként két szám következik, R és T, szóközzel elválasztva.

Minden tesztesethez egyetlen számot kell kiírni, a lefesthető fekete gyűrűk maximális számát.

Bemenet	Kimenet
5 1 9 1 10 3 40 1 1000000000000000000 10000000000000000 1000000000000000000	Case #1: 1 Case #2: 2 Case #3: 3 Case #4: 707106780 Case #5: 49

A feladat forrása: Google Code Jam 2013 R1 (https://code.google.com/codejam/contest/2418487/dashboard)

Algoritmusok: bináris keresés

megoldás