Programozás‎ > ‎Feladatok‎ > ‎

Telitalálat

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:
  1. Elképezel egy 1 cm vastag fehér gyűrűt a legutolsó fekete köré.
  2. Majd rajzol egy új  fekete gyűrűt a fehér köré. 
A fehér gyűrű csak üres hely, ahhoz nem kell festék. Egy ml festék éppen π cm2 terület lefestéséhez elég.  

Feladat

Í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.

Bemenet

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.

Méretek a nagy bemenetre

1 <= N <= 6000
<= R <= 1018
<= T <= 2 × 1018

Kimenet

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

Példa

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


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2013 R1 (https://code.google.com/codejam/contest/2418487/dashboard)
Algoritmusok: bináris keresés

megoldás