[At Coder] ABC085C --Otoshidama's Python answer

ABC085C --Otoshidama was solved from AtCoder Beginners Selection. The problem is here.

solution

It's written in Python.

n, y = list(map(int, input().split()))

a = 0  # The num of 10000 yen
b = 0  # The num of 5000 yen
c = 0  # The num of 1000 yen

yen_a = 10000
yen_b = 5000
yen_c = 1000

target = y - yen_c * n
coef_a = yen_a - yen_c
coef_b = yen_b - yen_c
a = int(target / coef_a)
if a > n or target < 0:
    a = b = c = -1
else:
    while(a >= 0):
        if(coef_a * a + coef_b * b == target and n-a-b >= 0):
            c = n - a - b
            break
        elif(coef_a * a + coef_b * b > target):
            a -= 1
        else:
            b += 1
    if a == -1:
        b = c = -1

print('{} {} {}'.format(a, b, c))

I think the code isn't very beautiful, but unfortunately it looks like this when solved by myself.

Commentary

The upper one receives standard input and initializes variables. In the block before the if statement, a two-dimensional linear equation is derived from two three-dimensional linear equations. It is a process that deletes c from the following formulas.

\left\{
\begin{array}{l}
a + b + c &=& n \\
10000a + 5000b + 1000c &=& y
\end{array}
\right.

The result is this formula.

9000a + 4000b = y - 1000n

After that, look for a combination of (a, b) that satisfies this.

ʻA = int (target / coef_a) derives the maximum ʻa that satisfies the above formula. When ʻa> n, that is, when the number of bills is too small to reach the target amount and when target <0, this is because the number of bills is too large and the target amount is less than the minimum amount that can be expressed. In this case, the target amount cannot be expressed by the number of bills specified in these two cases, so ʻa = b = c = -1.

After that, in cases other than the above, we are looking for a combination that satisfies the above equation by raising and lowering the values of ʻaandb`.

Afterword

As a point of reflection, I thought that I should have investigated all the cases within the range of ʻa + b + c = n` from the beginning. My method is not good at all, so please refer to this solution.

In addition to solving the problem, I thought it would be good to be a brain teaser to explain the contents of the program in words.