Gierige Methode

Die gierige Methode ist eine Methode, bei der ein bestimmter Standard festgelegt wird und die optimale Lösung kontinuierlich vor Ort ausgewählt wird, um die optimale Lösung zu finden. Ich denke, es ist effektiv, wenn man in kurzer Zeit zu einem gewissen Grad die optimale Lösung findet. Da die Giermethode selbst im weitesten Sinne angewendet wird, ist es in solchen Fällen schwierig, sie persönlich anzuwenden

Eine Lösung scheint erhalten zu werden, indem ein Wert A festgelegt und mit einem anderen Wert (B, C ...) verglichen wird.

Ich denke, es kann jederzeit verwendet werden.

Dieses Problem

AtCoders B - Magic 2 wird mit der gierigen Methode gelöst.

** Problemstellung ** Herr M hat die folgenden drei Karten.

Rote Karte mit darauf geschriebener Ganzzahl A.
Grüne Karte mit Ganzzahl B darauf geschrieben
Blaue Karte mit der Ganzzahl C darauf geschrieben

Da er ein genialer Magier ist, kann er die folgenden Operationen bis zu K-mal ausführen.

--Wählen Sie eine der drei Karten und verdoppeln Sie die geschriebene Ganzzahl.

Wenn nach dem Ausführen der Operation die folgenden Bedingungen gleichzeitig erfüllt sind, ist die Magie erfolgreich.

Die auf der grünen Karte geschriebene Ganzzahl ist wirklich größer als die auf der roten Karte geschriebene Ganzzahl.
Die auf der blauen Karte geschriebene Ganzzahl ist wirklich größer als die auf der grünen Karte geschriebene Ganzzahl.

Bestimmen Sie, ob Sie in der Magie erfolgreich sein können.

** Einschränkungen **

1≤A,B,C≤7
1≤K≤7
Alle Eingaben sind ganze Zahlen

Kurz gesagt, es wird davon ausgegangen, dass Sie innerhalb von K-mal "Rot <Grün" und "Grün <Blau" erreichen sollten. In diesem Problem kann die Bedingung erfüllt sein, wenn "die Häufigkeit, mit der Grün auf Rot verdoppelt wird" + "die Häufigkeit, mit der Blau auf Grün verdoppelt wird" kleiner oder gleich K ist.

Wenn Sie früher "einen Wert reparieren" sagen, ist dieses Problem

--Fixieren Sie den roten Wert zum Vergleich

Ich denke, es wird einfacher zu lösen sein.

Deine Antwort

`B-Magic2.py`


nums = input().split() #A,B,Geben Sie C ein

A = int(nums[0])
B = int(nums[1])
C = int(nums[2])

K = input() #Geben Sie K ein
k = int(K)

cnt = 0 #Wenn die Anzahl kleiner als k ist, ist Magie erfolgreich. Definieren Sie daher zum Vergleich eine Ganzzahl cnt

while A >= B: #Notieren Sie, wie oft B verdoppelt wird und zu A oder mehr wird
    cnt += 1
    B *= 2

while B >= C:  #Notieren Sie, wie oft C verdoppelt wird und zu B oder mehr wird
    cnt += 1
    C *= 2


if cnt <= k:
    print("Yes")
else:
    print("No")

7 4 2    #A,B,C Eingang
3        #K Eingang
No       #Ausgabe

Am Ende (Notizen schreiben)

Wenn es mit AtCoder zu einem schwierigen Problem wird, kann ich die Antwort nicht erreichen, selbst wenn ich die Bedingungen des Problems so übertrage, wie es ist. Daher dachte ich, dass sowohl die Lesefähigkeit als auch die mathematische Denkfähigkeit des Problems notwendig sind. Es fühlt sich an, als hätte ich Japanisch bis zur High School ignoriert. Oh, ich möchte Lesefähigkeit ...

Referenzartikel

https://studyhacker.net/reading-comprehension

https://www.naganomathblog.com/entry/2018/08/21/071918

Schreiben Sie eine einfache Giermethode in Python