Problem
Risotto Nero, manyetik bir yapıcıdan evler toplamaya bayılıyor.
n parçalıdır, i'incisinin boyutu s
i'dir.
Bir ev inşa etmek için, tam olarak aynı boyutta
a parçaya ve k kez daha büyük olan başka bir aynı boyutta tam olarak
b parçaya ihtiyacınız var.
Risotto Nero'nun yapabileceği maksimum ev sayısını belirleyin.
Giriş:
İlk satır n, a, b ve k tamsayılarını içerir (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
İkinci satır, parça boyutlarının sırasını içerir — tamsayılar s
1, s
2, …, s
n (1 ≤ s
i ≤ 10 < sup>6).
Çıktı:
Tek bir tamsayı yazdır — verilen n parçadan inşa edilebilecek maksimum ev sayısı.
Örnekler:
| Giriş |
Çıktı |
12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6
| 3 |
14 1 1 3
3 3 1 1 9 9 2 3 6 6 3 18 3 18
| 6 |
1 2 3 10
1000000 |
0 |
Açıklama:
İlk örnekte, en iyi seçenek [1, 2, 2] boyutlarındaki parçalardan iki ev ve [3, 6, 6] boyutlarındaki parçalardan bir ev inşa etmektir.