ABC085C - Otoshidama wurde aus AtCoder Beginners Selection gelöst. Das Problem ist hier.
Geschrieben 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))
Ich denke, es ist kein sehr schöner Code, aber leider sieht es so aus, wenn ich ihn selbst löse.
Der obere empfängt die Standardeingabe und initialisiert Variablen. Im Block vor der if-Anweisung wird die binäre lineare Gleichung aus den beiden kubischen linearen Gleichungen abgeleitet. Es ist ein Prozess, der "c" aus der folgenden Formel löscht.
\left\{
\begin{array}{l}
a + b + c &=& n \\
10000a + 5000b + 1000c &=& y
\end{array}
\right.
Das Ergebnis ist diese Formel.
9000a + 4000b = y - 1000n
Suchen Sie danach nach einer Kombination von "(a, b)", die dies erfüllt.
a = int (target / coef_a) leitet das Maximum a ab, das die obige Formel erfüllt. Wenn "a> n", dh wenn die Anzahl der Scheine zu klein ist, um den Zielbetrag zu erreichen, und wenn "Ziel <0", liegt dies daran, dass die Anzahl der Scheine zu groß ist und der Zielbetrag geringer ist als der Mindestbetrag, der ausgedrückt werden kann. In diesem Fall kann der Zielbetrag nicht durch die in diesen beiden Fällen angegebene Anzahl von Rechnungen ausgedrückt werden, daher wird "a = b = c = -1" festgelegt.
Danach suchen wir in anderen als den oben genannten Fällen nach einer Kombination, die die obige Gleichung erfüllt, indem wir die Werte von "a" und "b" erhöhen oder verringern.
Zum Nachdenken dachte ich, ich hätte von Anfang an alle Fälle im Bereich von "a + b + c = n" untersuchen sollen. Meine Methode ist überhaupt nicht gut. Weitere Informationen finden Sie unter Diese Lösung.
Zusätzlich zur Lösung des Problems hielt ich es für gut, eine mentale Übung zu verwenden, um den Inhalt des Programms in Worten zu erklären.
Recommended Posts