Einführung

Dies ist ein Studienmemo der letzten Frage ABC115. Die verwendete Sprache ist Python.

A - Christmas Eve Eve Eve Difficulty : 0 Ich denke, dass das Schreiben eines Zweigs mit einer if-Anweisung am einfachsten und stabilsten ist.

d = int(input())
if d == 22:
    print('Christmas Eve Eve Eve')
if d == 23:
    print('Christmas Eve Eve')
if d == 24:
    print('Christmas Eve')
if d == 25:
    print('Christmas')

B - Christmas Eve Eve Difficulty : 24 Finden Sie zuerst den Gesamtpreis ohne Rabatt. Subtrahieren Sie die Hälfte des Preises des teuersten Artikels, um den Zahlungsbetrag zu erhalten.

n = int(input())
p = list(int(input()) for i in range(n))
print(sum(p) - (max(p)//2))

C - Christmas Eve Difficulty : 243 In Beispiel 1 werden der erste, dritte und fünfte Baum als die richtige Antwort ausgewählt, aber es ist schwierig, 1, 3 und 5 so auszuwählen, wie sie sind. Wenn Sie beispielsweise der Meinung sind, dass diese Bäume in aufsteigender Reihenfolge angeordnet sind, z. B. "10, 11, 12, 14, 15", sind die Antwortbäume Seriennummern mit dem ersten, zweiten und dritten Baum, was das Geben einer Antwort erleichtert. .. Sortieren Sie also $ h $ im Voraus. Verwenden Sie dann für, um $ h_ {max} --h_ {min} $ zu berechnen, um von vorne die minimale Differenz zu ermitteln.

n,k = map(int,input().split())
h = list(int(input()) for i in range(n))
h.sort()
ans = 10**16
for i in range(n-k+1):
    ans = min(ans,h[i+k-1]-h[i])
print(ans)

D - Christmas Difficulty : 1084 Der mehrdimensionale Burger für dieses Problem sieht folgendermaßen aus:

Stufe 0 P.
Level 1 BPPPB
Stufe 2 BBPPPBPBPPPBB
Stufe 3 BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
︙

Dieses Problem hat eine maximale Stufe von 50, die etwas über $ 10 ^ {15} $ aus Beispiel 3 liegt, und das einfache Herstellen und Zählen von Burgern wird das Ausführungszeitlimit nicht einhalten. Daher ist es notwendig, die Anzahl der Pastetchen zu bestimmen und zu finden. Ermitteln Sie zunächst die Dicke $ a $ pro Ebene und die Gesamtzahl der Pastetchen $ p $ pro Ebene. Stufe 0 ist von Anfang an als 1 bekannt, aber Stufe 1 und höher muss berechnet werden. $ a_i $ besteht aus "van, $ a_ {i-1} $, Pastetchen, $ a_ {i-1} $, van", also $ a_i = a_ {i-1} \ times 2 + 3 $ Wird sein. $ p_i $ muss einen Van von der obigen Konfiguration subtrahieren, also $ p_i = p_ {i-1} \ times 2 + 1 $.

a[i] = 2 × a[i-1] + 3 
p[i] = 2 × p[i-1] + 1

Dann sei $ f (N, X) $ die Anzahl der Schichten von Pastetchen, die in der X-Schicht vom unteren Ende der Ebene N enthalten sind. Darüber hinaus nutzen wir im Fall von Level 0 die Tatsache, dass es leicht zu finden ist, und nehmen an, dass "$ f (N-1, Y) $ für Level N-1 bekannt ist, unabhängig davon, welche ganze Zahl Y angegeben ist." Sie können auch wie folgt nach Level N Burger fragen:

1. X =Wenn 1
   N =Wenn 1, dann f(N,X) = 0
   N =Wenn 0, f(N,X) = 1
Mit Ausnahme von Level 0 ist der Boden ein Van auf jedem Level, also gibt es 0 Pastetchen.

2. 1 < X ≦ 1 + a[N-1]Wenn f(N,X) = f(N-1,X-1)
X ist Stufe N.-1 Dicke+Wenn es in 1 passt.
Der Grund für das Hinzufügen von 1 ist Stufe N.-Die Menge des unteren Lieferwagens, die beim Aufbau der Stufe N aus 1 hinzugefügt wurde.
Stufe N.-Da wir die Anzahl der X-Layer-Pastetchen in 1 finden müssen, f(N-1,X-1)Anruf.
Der Grund für das Subtrahieren von 1 ist der gleiche wie beim Addieren.

3. X = 2 + a[N-1]Wenn f(N,X) = p[N-1] + 1
X ist Stufe N.-Dies entspricht der Dicke von 1, einschließlich des unteren Lieferwagens und der mittleren Pastetchen, die beim Aufbau der Ebene N hinzugefügt wurden.
Stufe N in diesem Fall-Dies ist die Anzahl von 1 Pastetchen plus 1 mittleren Pastetchen, die bei der Konfiguration von Level N hinzugefügt wurden.

4. 2 + a[N-1] < X ≦ 2 + 2a[N-1]Wenn f(N,X) = p[N-1] + 1 + f(N-1,X-2-a[N-1])
Es sieht aus wie eine Mischung aus den Bedingungen 2 und 3.
Berechnen Sie die Anzahl der Blätter bis zur mittleren Pastete auf die gleiche Weise wie 3.
Außerdem möchte ich die Anzahl der Pastetchen von der Mitte bis zur Spitze ermitteln, also f(N-1,X-2-a[N-1])Anruf.
Der X-Teil ist nur X minus der Länge von 3.

5. X = 3 + 2a[N-1]Wenn f(N,X) = 2p[N-1] + 1
Wenn X das aktuelle Niveau ist, ist die Dicke N unverändert.
In diesem Fall 2 x p, wie ursprünglich berechnet[N-1] +Es kann durch 1 erhalten werden.

Der Durchfluss bis zu diesem Punkt ist in der Abbildung dargestellt. Betrachten Sie das gelbe B als Van und das braune P als Pastetchen.

スクリーンショット (2).png

Schreiben Sie diese Bedingung als rekursive Funktion und rufen Sie $ f (N, X) $ auf, um die Antwort zu finden.

n,x = map(int,input().split())
a,p = [1],[1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def pate(n,x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x <= 1 + a[n-1]:
        return pate(n-1,x-1)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif x <= 2 + 2 * a[n-1]:
        return p[n-1] + 1 + pate(n-1,x-2-a[n-1])
    else:
        return 2 * p[n-1] + 1

print(pate(n,x))

[PYTHON] Atcoder ABC115 Vergangene Frage Übung

Einführung