Analiz ve Çözüm Yolu

Elimizde parçacıkların kümesi olduğunda bu parçacıklarla oluşturulabilecek maksimum eleman sayısını kolaylıkla bulabiliriz. Toplam eleman sayısına T ve maksimum eleman sayısına M diyelim. Eğer bir X parçacığının sayısı \(\frac{T}{2}\) den büyükse \(M = T -X\) olur, aksi takdirde ise \(M = \left \lfloor \frac{T}{2} \right \rfloor\) olur.

Şimdi olabildiğince çok HP elementi üretmeye çalışalım. HP elementini ürettikten önce ve sonraki M değerlerini karşılaştırın. Eğer aralarındaki fark birse devam edebiliriz, değilse toplam element sayısı azalacağı için HP elementi üretemeyiz. HP elementi üretilebiliyorsa, bir sonraki üretilemeyinceye kadar işlemi tekrar ederiz. Daha sonra aynı süreci sırasıyla HR, HS, PR, PS ve son olarak da RS için de uygularız.

Bahsedilen algoritma doğru ama maalesef çok yavaş. Bu yaklaşımı her element için üretebileceğimiz maksimum sayıyı ararken ikili arama kullanarak hızlandırabiliriz.

Analysis and Guide for Solution

Having a set of particles it's easy to find the maximal number of elements that can be made out of them. Let's denote the total number of particles in the set with T and the maximal number of elements with M. Then if the number of some particle X is greater than \(\frac{T}{2}\) then \(M = T - X\), otherwise \(M = \left \lfloor \frac{T}{2} \right \rfloor\).

Now let's try to make as much HP elements as possible. If we can make one HP element consider values of M before and after we made it. If they differ by one we can proceed otherwise we can't make HP element since it would lead to smaller total number of elements. Assume it's okay to make one HP element, then we try to make another one and so on until we can't make the next element. Then we switch to HR, then to HS, then to PR, then to PS and finally to RS.

The described algorithm is correct but unfortunately too slow. We can speed up the approach by using a binary search for every element while looking for the maximal number we can make.