Düşən Buz
Təsəvvür edin ki, buz diskləri bir-bir qutuya düşür və hər biri əvvəlki disklərlə üst-üstə düşmədən və ya hərəkət etmədən çata biləcəyi ən aşağı nöqtədə dayanır. Hər bir disk yerində donur, belə ki, sonrakı disklər tərəfindən hərəkət etdirilə bilməz. Sizin vəzifəniz disklərin son kombinasiyasının ümumi hündürlüyünü tapmaqdır.
Cavabın unikal olması üçün, qutunun dibinə çatan hər hansı bir disk mümkün qədər sola yuvarlanır. Həmçinin, məlumatlar elə seçilib ki, dibə çatmayan hər hansı bir disk üçün unikal ən aşağı mövqe olacaq. Məlumatlar həmçinin "mükəmməl uyğunluqlar" olmadığı şəkildədir: enən hər bir disk yalnız əvvəlki dairələrin və ya qutunun yanlarının iki digər nöqtəsi ilə təmasda olacaq. Yuxarıdakı illüstrasiyalar qutularına düşmə sırası ilə etiketlənmiş ağ doldurulmuş diskləri göstərir. Dördüncü illüstrasiyadakı boz dairə düşən bir disk kimi nəzərdə tutulmayıb. Boz disk bir nöqtəni göstərmək üçün daxil edilib: boz disk disk 2 ilə eyni ölçüdədir, beləliklə, disk 2 üçün qutunun dibində yer var, lakin disk 2 yuxarıdan düşərək o mövqeyə çata bilmir. O, disk 1 və qutunun yanına ilişir.
İki kəsişən dairənin yuxarı kəsişmə nöqtəsini tapmağın bir yolu aşağıdakı kimidir. Fərz edək ki, dairə 1 mərkəzi (x_1,y_1) və radiusu r_1 olan dairədir və dairə 2 mərkəzi (x_2, y_2) və radiusu r_2 olan dairədir. Həmçinin fərz edək ki, dairə 1 dairə 2-nin solundadır, yəni x_1 < x_2. Qoy
dx = x_2 - x_1,dy = y_2 - y_1,D = sqrt(dx*dx + dy*dy),E = (r_1*r_1 - r_2*r_2 + D*D)/(2*D),F = sqrt(r_1*r_1 - E*E);
onda yuxarı kəsişmə nöqtəsi (x_1 + (E*dx - F*dy)/D, y_1 + (F*dx + E*dy)/D) olacaq.
Giriş verilənləri
Giriş bir və ya daha çox məlumat dəstindən ibarətdir, ardınca yalnız 0 olan bir sətir gəlir ki, bu da girişin sonunu göstərir. Hər bir məlumat dəsti öz sətirində yerləşir və w, n, d_1, d_2, d_3, ..., d_n formatında boşluqla ayrılmış üç və ya daha çox müsbət tam ədəddən ibarətdir, burada w qutunun eni, n disklərin sayıdır və qalan ədədlər disklərin diametrləridir, qutuya düşmə sırasına görə. Siz w < 100, n < 10 və hər bir diametrin w-dən kiçik olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Hər bir məlumat dəsti üçün disklərin yığınının hündürlüyünü iki ondalık yerə qədər yuvarlaqlaşdırılmış şəkildə bir sətirdə çıxarın.
Misal məlumatlar yuxarıdakı illüstrasiyalara uyğundur.