1547. Kolye

 

Bir kabilenin üyeleri nadir bir çeşit kil kullanarak çembersel seramik aynı çapa sahip diskler üretmektedir. Her kolye bir ya da daha çok diski bir araya getirerek elde edilmektedir. Her bir diskin kalınlığı sabittir. Aşağıdaki şekilde 4 disk ile yapılan bir kolye görülmektedir. Bu kolyenin uzunluğu bir diskin çapının 4 katıdır.

Elinizde bulunan toplam kil hacmi Vtotal olsun. Disk çapı D ve kullanılan kil miktarı V arasında şu ilişki vardır:

D = ,

burada V0 fırınlama işlemi sırasında V birim kilden kaybolan kil miktarını göstermektedir. Eğer V ≤ V0, ise hiç disk yapılamaz.

Örnek olarak, Vtotal = 10, V0 = 1 olsun. Eğer bunu kullanarak 1 disk yaparsak, V = Vtotal = 10, D = 0.3 = 0.9. Eğer kili 2 parçaya bölersek, her bir parçanın hacmi V = Vtotal / 2 = 5, üretilen her bir diskin çapı D = 0.3 = 0.6, sonuç olarak da bu şekilde üretilen diskin boyu 0.6 * 2 = 1.2 olur.

Yukardaki örnekte açıklandığı şekilde, kolyelerin uzunluğu  üretilen disk sayısına göre değişmektedir. Olabilecek en uzun kolyeyi elde etmek için kullanılması gereken disk sayısını bulan programı yazınız.

 

Girdi. Her satırda yukarda tanımlandığı şekilde iki sayı bulunmaktadır, Vtotal (0 < Vtotal £ 60000) ve V0 (0 < V0 £ 600). Girdilerin en sonundaki saturda Vtotal = V0 = 0 bulunmakta olup bu satır işlenmemektedir.

 

Çıktı. Her çıktı satırında en uzun kolyeyi oluşturmak için yapılması gereken disk sayısı verilmektedir. Eğer bu sayı biricik değilse, ya da kolye yapılamıyorsa, bunun yerine 0 yazılmalıdır.

 

Örnek girdi

10 1

10 2

0 0

 

Örnek çıktı

5

0

 

 

ÇÖZÜM

matematik

 

Algoritma analizi

En uzun kolyenin n diskten oluştuğunu varsayalım. Her diskin çapı bulunur:

D = 0.3 = 0.3

Kolyenin uzunluğu, d, şuna eşittir:

d = D * n = 0.3 = 0.3

Maksimum d değerine f(n) = Vn – V0n2 fonksiyonunun maksimum değeri elde edildiğinde ulaşılacaktır. Bunun için fonksiyonun türevini alıp 0’a eşitleyelim: f’(n) = V – 2V0n = 0, buradan da n = V / 2V0 bulunur. n bir tamsayı olmak zorunda olduğu için, değeri  ya da  olabilir. Bu her iki n değeri için de kolye uzunluğunu hesaplayıp ve büyüğünü seçin. Eğer bu iki uzunluk aynı ise, 0 yazdırınız (disk sayısı biricik olarak tanımlı değildir). İstenen n diskin verilen V kilden üretilmesinin mümkün olup olmadığını test ediniz: Eğer Vtotal £ V0 * n, ise böyle bir kolyenin üretilmesi mümkün değildir.

 

Algoritma gerçekleştirmesi

f( ) fonksiyonu verilen Vtotal, V0 ve n değerleri için kolye uzunluğunu hesaplar.

 

double f(int v, int v0,int n)

{

  return 0.3 * sqrt(1.0 * v * n - v0 * n * n);

}

 

Programın ana yapısı şöyledir. Vtotal ve V0 değerlerini okuyun, n =  değerini hesaplayın. Bu n değeri için kolyenin fırınlanmasının olabilirliğini hesaplayın. Verilen n =  ve n =  + 1 değerleri için kolye uzunluğunu bularak karşılaştırın ve büyük olanı seçin. Eğer iki uzunluk eşit ise, 0 yazdırın.

 

while(scanf("%d %d",&v,&v0), v + v0 > 0)

{

  n = int(0.5 * v / v0);

  if (v <= v0 * n) {printf("0\n"); continue;}

  r1 = f(v,v0,n);

  r2 = f(v,v0,n+1);

  if (r2 > r1) n++;

  if (fabs(r1 - r2) < 1e-7) printf("0\n");

  else printf("%d\n",n);

}