ريزوتو نيرو والمنشئ المغناطيسي
Problem
يحب Risotto Nero جمع المنازل من مُنشئ مغناطيسي.
يحتوي على عدد n من الأجزاء ، وحجم الجزء الأول هو s
i . & nbsp ؛
من أجل بناء منزل ، تحتاج بالضبط إلى
أجزاء من نفس الحجم و بالضبط أجزاء من حجم مماثل آخر ، وهو أكبر بمقدار k مرة.
حدد الحد الأقصى لعدد المنازل التي يمكن أن يبنيها ريزوتو نيرو.
الإدخال:
يحتوي السطر الأول على أعداد صحيحة n و a و b و k (1 & le؛ n، a، b & le؛ 300000، 2 & le؛ k & le؛ 1000).
يحتوي السطر الثاني على تسلسل أحجام الأجزاء و [مدش] ؛ أعداد صحيحة s 1 ، s 2 ، & hellip ؛، s n (1 & le؛ s i & le؛ 10 < sup> 6 ).
الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ الحد الأقصى لعدد المنازل التي يمكن بناؤها من n أجزاء معينة.
أمثلة:
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
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 |
الشرح:
في المثال الأول ، الخيار الأفضل هو بناء منزلين من أجزاء ذات أبعاد [1 ، 2 ، 2] ومنزل واحد من أجزاء ذات أبعاد [3 ، 6 ، 6].
نبسب ؛