ABC085C --Otoshidama a été résolu à partir de AtCoder Beginners Selection. Le problème est ici.
Écrit en 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))
Je pense que ce n'est pas très beau code, mais malheureusement, il ressemble à ça quand je le résous moi-même.
Le supérieur reçoit l'entrée standard et initialise les variables. Dans le bloc précédant l'instruction if, l'équation linéaire binaire est dérivée des deux équations linéaires cubiques. C'est un processus qui supprime «c» de la formule suivante.
\left\{
\begin{array}{l}
a + b + c &=& n \\
10000a + 5000b + 1000c &=& y
\end{array}
\right.
Le résultat est cette formule.
9000a + 4000b = y - 1000n
Après cela, cherchez une combinaison de «(a, b)» qui satisfait ceci.
ʻA = int (target / coef_a) dérive le maximum ʻa qui satisfait la formule ci-dessus. Lorsque «a> n», c'est-à-dire lorsque le nombre de factures est trop petit pour atteindre le montant cible et lorsque «cible <0», c'est parce que le nombre de factures est trop grand et que le montant cible est inférieur au montant minimum qui peut être exprimé. Dans ce cas, le montant cible ne peut pas être exprimé par le nombre de factures spécifié dans ces deux cas, donc ʻa = b = c = -1`.
Après cela, dans les cas autres que ceux ci-dessus, nous recherchons une combinaison qui satisfait l'équation ci-dessus en augmentant ou en abaissant les valeurs de «a» et «b».
En guise de réflexion, j'ai pensé que j'aurais dû enquêter sur tous les cas dans l'intervalle «a + b + c = n» depuis le début. Ma méthode n'est pas du tout bonne, veuillez donc vous référer à Cette solution.
En plus de résoudre le problème, j'ai pensé qu'il serait bon d'utiliser un exercice mental pour expliquer le contenu du programme avec des mots.
Recommended Posts