시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 142 | 68 | 63 | 53.846% |
You have recently acquired a new job at the Bank for Acquiring Peculiar Currencies. Here people can make payments, and deposit or withdraw money in all kinds of strange currencies. At your first day on the job you help a customer from Nijmegia, a small insignificant country famous for its enormous coins with values equal to powers of 10, that is, 1, 10, 100, 1000, etc. This customer wants to make a rather large payment, and you are not looking forward to the prospect of carrying all those coins to and from the vault.
You therefore decide to think things over first. You have an enormous supply of Nijmegian coins in reserve, as does the customer (most citizens from Nijmegia are extremely strong). You now want to minimize the total number of coins that are exchanged, in either direction, to make the exact payment the customer has to make.
For example, if the customer wants to pay 83 coins there are many ways to make the exchange. Here are three possibilities:
It turns out the last way of doing it requires the least coins possible.
83
6
13
4
0
0
12345678987654321
42
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2019 E번