Tərəvəzlərin bişirilməsi#6250
Tərəvəz bişirməyin sirri, bütün parçaların təxminən eyni ölçüdə olmasındadır. Əks halda, kiçik parçalar çox bişər, böyük parçalar isə az bişər. Xoşbəxtlikdən, mətbəx bıçağından istifadə etməyi bilirsiniz, amma valideynlərinizin iti alətlərdən istifadə ilə bağlı xəbərdarlıqları hələ də yadınızdadır. Buna görə də, bıçağı mümkün qədər az istifadə etmək istəyirsiniz. Siz ağırlığında bir tərəvəz parçasını istənilən şəkildə w_{left} və w_{right} ağırlıqlarına malik iki hissəyə bölə bilərsiniz, burada w_{left} + w_{right} = w. Bu əməliyyatı "kəsmə" adlandıraq.
Mövcud tərəvəz parçalarının ölçülərini bilmək şərti ilə, ən kiçik və ən böyük parça arasındakı nisbətin verilmiş həddən böyük olacağı qədər kəsiklərin minimal sayını müəyyən edin.
Əvvəlcə t~(0.5 < t < 1) ondalık sayı və təbii n~(n \le 1000) sayı verilir. Sonra müsbət tam ədədlər w_1, w_2, ..., w_n gəlir. Bütün ağırlıqlar 10^6-dan kiçikdir.
Ən kiçik və ən böyük parça arasındakı nisbətin -dən böyük olacağı qədər kəsiklərin minimal sayını çıxarın. Lazımi kəsiklərin sayının -dən az olduğunu düşünün. Ondalık ədədlərlə bağlı problemlərdən qaçmaq üçün, nisbəti üçün optimal cavabın t + 0.0001 nisbəti üçün də eyni olacağını fərz edin.
Nümunə 1
Nümunə 2