First of all, I am not sure if this is the right way to ask, but in case it is, I am stuck on a problem and don't have a clue how to solve it. I would like to get some hints :).
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 3 | cry | 159 |
| 5 | atcoder_official | 158 |
| 5 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 149 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/25/2024 12:22:17 (f1).
Desktop version, switch to mobile version.
Supported by
Try breaking the problem down into two parts: figuring out if a number can be created to be divisible by 10, and seeing if the number can be divisible by 9. If both of these are true, then the number is also divisible by 90.
$$$90 = 9 \times 10$$$. So a number will be divisible by $$$90$$$ if and only if it's divisible by $$$9$$$ and $$$10$$$.
A number will be divisible by $$$10$$$ if it has a trailing $$$0$$$. A number will be divisible by $$$9$$$, if the sum of it's digits are divisible by $$$9$$$.
After taking input, count the number of $$$5$$$'s (we denote it by $$$f$$$). The number of $$$0$$$'s will be then $$$z = n - f$$$.
Remember we need the number to be divisible by both $$$9$$$ and $$$10$$$. So if $$$f = n$$$ (or $$$z = n - f = 0$$$), then there is no solution. Print $$$-1$$$.
At this point we know, there is at least one $$$0$$$. So we can construct a number that is divisible by $$$10$$$. The other condition was that the number has to divisible by $$$9$$$. Although the $$$0$$$'s sum up to $$$0$$$ and $$$0$$$ is divisible by $$$9$$$, we can't place leading $$$0$$$'s. So in order to satisfy the divisibility by $$$9$$$ constraint, we have to place a number of $$$5$$$'s to the left of $$$0$$$(or $$$0$$$'s) such that the number of $$$5$$$'s sum up to a number that's divisible by $$$9$$$.
How many $$$5$$$'s are needed to make the sum of $$$5$$$'s divisible by $$$9$$$? Notice that $$$\text{lcm}(5, 9) = 45$$$. So we need at least $$$9$$$ $$$5$$$'s to make the sum of digits divisible by $$$9$$$. In other words, let $$$f^\prime$$$ be the number of $$$5$$$'s that sum up to a number that's divisible by $$$9$$$. Then $$$f^\prime$$$ has to be a multiple of $$$9$$$. We have already counter the number of $$$5$$$'s (denoted by $$$f$$$). So we have to find the multiple of $$$9$$$ that is closest to $$$f$$$. We can find it by, $$$f^\prime = \lfloor \frac{f}{9} \rfloor \times 9 $$$. Think about as to why it's true.
We place $$$f^\prime$$$ number of $$$5$$$'s at the start. Now are we done? Almost. We already have a trailing $$$0$$$ and a bunch of $$$5$$$'s to its left. To make the number as large as possible, we place the remaining $$$0$$$'s (if there are any), between the $$$5$$$'s and the trailing $$$0$$$.
Submission: 90701750