[At Coder] ABC085C - La réponse Python d'Otoshidama

ABC085C --Otoshidama a été résolu à partir de AtCoder Beginners Selection. Le problème est ici.

Solution

É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.

Commentaire

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».

Épilogue

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

[At Coder] ABC085C - La réponse Python d'Otoshidama
[Python] Modèle Pro compétitif [Chez Coder]
Chez Coder (08/09/2020)
python chez docker
Remplir au codeur
Au Coder # 1 à minuit
[At Coder] Débutant Contest 175 Présentation de la solution ABCD python
[Python] ABC133B (problème du triangle supérieur droit) [At Coder]
[Python] ABC159D (Mathématiques au lycée nCr) [At Coder]
[Python] AGC043A (problème de lecture et de DP) [At Coder]
[At Coder] Méthode de sortie
Résolvez ABC146-C avec Python
[Python] Recherche (itertools) ABC167C
[Python] Recherche (NumPy) ABC165C
Résoudre ABC098-C en Python
[At Coder] ABC128B --Guidebook
[Python] [BFS] Au concours de codeur pour débutants 168-D [.. Double Dots]
[At Coder] Triplés Acing C-XYZ
[AtCoder] Note personnelle ABC165C [Python]