{"problem":{"name":"A. Hit the Lottery","description":{"content":"Allen has a LOT of money. He has $n$ dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are $1$, $5$","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF996A"},"statements":[{"statement_type":"Markdown","content":"Allen has a LOT of money. He has $n$ dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are $1$, $5$, $10$, $20$, $100$. What is the minimum number of bills Allen could receive after withdrawing his entire balance?\n\n## Input\n\nThe first and only line of input contains a single integer $n$ ($1 \\le n \\le 10^9$).\n\n## Output\n\nOutput the minimum number of bills that Allen could receive.\n\n[samples]\n\n## Note\n\nIn the first sample case, Allen can withdraw this with a $100$ dollar bill, a $20$ dollar bill, and a $5$ dollar bill. There is no way for Allen to receive $125$ dollars in one or two bills.\n\nIn the second sample case, Allen can withdraw two $20$ dollar bills and three $1$ dollar bills.\n\nIn the third sample case, Allen can withdraw $100000000$ (ten million!) $100$ dollar bills.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Allen 有大量金钱。他在银行中有 $n$ 美元。出于安全原因，他希望以现金形式取出（此处不披露具体原因）。美元纸币的面额为 $1$、$5$、$10$、$20$、$100$。Allen 在取出全部余额后，最少能收到多少张纸币？\n\n输入仅有一行，包含一个整数 $n$（$1 lt.eq n lt.eq 10^9$）。\n\n请输出 Allen 能收到的最少纸币数量。\n\n在第一个测试用例中，Allen 可以用一张 $100$ 美元、一张 $20$ 美元和一张 $5$ 美元的纸币取出这笔钱。不存在用一张或两张纸币取出 $125$ 美元的方法。\n\n在第二个测试用例中，Allen 可以用两张 $20$ 美元纸币和三张 $1$ 美元纸币取出这笔钱。\n\n在第三个测试用例中，Allen 可以取出 $100000000$（一千万！）张 $100$ 美元纸币。\n\n## Input\n\n输入仅有一行，包含一个整数 $n$（$1 lt.eq n lt.eq 10^9$）。\n\n## Output\n\n请输出 Allen 能收到的最少纸币数量。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，Allen 可以用一张 $100$ 美元、一张 $20$ 美元和一张 $5$ 美元的纸币取出这笔钱。不存在用一张或两张纸币取出 $125$ 美元的方法。在第二个测试用例中，Allen 可以用两张 $20$ 美元纸币和三张 $1$ 美元纸币取出这笔钱。在第三个测试用例中，Allen 可以取出 $100000000$（一千万！）张 $100$ 美元纸币。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the amount of money to withdraw, with $ 1 \\leq n \\leq 10^9 $.  \nLet $ D = \\{100, 20, 10, 5, 1\\} $ be the set of available bill denominations, sorted in descending order.\n\n**Constraints**  \n$ n \\in \\mathbb{Z}^+ $, $ n \\leq 10^9 $\n\n**Objective**  \nFind the minimum number of bills $ k \\in \\mathbb{Z}^+ $ such that:  \n$$\nn = \\sum_{d \\in D} c_d \\cdot d, \\quad \\text{where } c_d \\in \\mathbb{Z}_{\\geq 0}\n$$  \nand $ k = \\sum_{d \\in D} c_d $ is minimized.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF996A","tags":["dp","greedy"],"sample_group":[["125","3"],["43","5"],["1000000000","10000000"]],"created_at":"2026-03-03 11:00:39"}}