hit-the-lottery

Hit the Lottery

لدى ألن \(n\) دولار في البنك ويريد أن يسحبها كلها نقدًا. قيم الأوراق النقدية هي \(1\) و \(5\) و \(10\) و \(20\) و \(100\) دولار.

ما أقل عدد من الأوراق يمكن أن يستلمه ألن؟

القيود:

\(1 \le n \le 10^9\)

الإدخال:

سطر واحد: عدد صحيح \(n\).

المخرجات:

عدد صحيح واحد — أقل عدد من الأوراق.

أمثلة:

الإدخال:

المخرجات:

(\(125 = 100 + 20 + 5\).)

الإدخال:

المخرجات:

(\(43 = 20 + 20 + 1 + 1 + 1\).)

الحل

نستخدم القاعدة الجشعة: نأخذ أكبر عدد ممكن من الأوراق ذات القيمة الأكبر، ثم نتابع بالقيمة التالية على المبلغ المتبقي.

لماذا تعطي القاعدة الجشعة أقل عدد؟ لنأخذ أي طريقة دفع بأقل عدد من الأوراق. لا يمكن أن تحتوي على:

خمس أوراق من فئة \(1\)، لأن ورقة واحدة من فئة \(5\) تحل محلها؛
ورقتين من فئة \(5\)، لأن ورقة واحدة من فئة \(10\) تحل محلهما؛
ورقتين من فئة \(10\)، لأن ورقة واحدة من فئة \(20\) تحل محلهما؛
خمس أوراق من فئة \(20\)، لأن ورقة واحدة من فئة \(100\) تحل محلها.

إذن مجموع الأوراق الأصغر من \(100\) لا يزيد على \(4 \cdot 1 + 5 + 10 + 4 \cdot 20 = 99\). هذا يعني أن عدد أوراق فئة \(100\) يجب أن يكون \(\lfloor n / 100 \rfloor\) بالضبط، وهذا ما تأخذه القاعدة الجشعة. بالطريقة نفسها، مجموع الأوراق الأصغر من \(20\) لا يزيد على \(19\)، والأصغر من \(10\) لا يزيد على \(9\)، والأصغر من \(5\) لا يزيد على \(4\)، لذلك تأخذ القاعدة الجشعة العدد الصحيح من كل فئة أخرى أيضًا.

بالقسمة تحتاج كل قيمة إلى خطوة واحدة: نأخذ \(n / v\) ورقة من الفئة \(v\)، والمبلغ المتبقي هو \(n \bmod v\).

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int bills[5] = {100, 20, 10, 5, 1};
    int count = 0;

    for (int i = 0; i < 5; i++) {
        count += n / bills[i];  // take as many of the largest bill as possible
        n %= bills[i];
    }

    cout << count << "\n";
}