[PYTHON] Atcoder ABC115 Exercice de questions passées

introduction

Ceci est un mémo d'étude de la question précédente ABC115. Le langage utilisé est Python.

A - Christmas Eve Eve Eve Difficulty : 0 Je pense qu'écrire une branche avec une instruction if est le plus simple et le plus stable.

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 Tout d'abord, trouvez le prix total sans réduction. À partir de là, soustrayez la moitié du prix de l'article le plus cher pour obtenir le montant du paiement.

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

C - Christmas Eve Difficulty : 243 Dans l'exemple 1, les premier, troisième et cinquième arbres sont sélectionnés comme la bonne réponse, mais il est difficile de sélectionner 1, 3 et 5 tels quels. Par exemple, si vous pensez que ces arbres sont disposés dans un ordre croissant tel que "10, 11, 12, 14, 15", les arbres de réponses seront des numéros de série avec les premier, deuxième et troisième arbres, ce qui facilitera la réponse. .. Alors, triez $ h $ à l'avance. Ensuite, utilisez for pour calculer $ h_ {max} --h_ {min} $ dans l'ordre à partir du front pour trouver la différence minimale.

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 Le hamburger multidimensionnel pour ce problème ressemble à ceci:

Niveau 0 P
BPPPB de niveau 1
Niveau 2 BBPPPBPBPPPBB
Niveau 3 BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
︙

Ce problème a un niveau maximum de 50, ce qui est légèrement supérieur à 10 $ ^ {15} $ de l'exemple 3 et le simple fait de préparer et de compter des hamburgers ne respectera pas la limite de temps d'exécution. Par conséquent, il est nécessaire de concevoir et de trouver le nombre de galettes. Tout d'abord, trouvez l'épaisseur $ a $ par niveau et le nombre total de galettes $ p $ par niveau. Le niveau 0 est connu comme 1 depuis le début, mais le niveau 1 et supérieur doit être calculé. $ a_i $ se compose de "van, $ a_ {i-1} $, patty, $ a_ {i-1} $, van", donc $ a_i = a_ {i-1} \ fois 2 + 3 $ Sera. $ p_i $ doit soustraire une camionnette de la configuration ci-dessus, donc $ p_i = p_ {i-1} \ times 2 + 1 $.

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

Ensuite, soit $ f (N, X) $ le nombre de couches de galettes contenues dans la couche X à partir du bas du niveau N. De plus, dans le cas du niveau 0, nous profitons du fait qu'il est facile à trouver et supposons que «$ f (N-1, Y) $ est connu pour le niveau N-1 quel que soit l'entier Y spécifié». Vous pouvez également demander le niveau N Burger comme suit:

1. X =Quand 1
   N =Si 1 alors f(N,X) = 0
   N =Si 0, f(N,X) = 1
Sauf pour le niveau 0, le fond est une camionnette à n'importe quel niveau, donc il y a 0 galettes.

2. 1 < X ≦ 1 + a[N-1]Quand f(N,X) = f(N-1,X-1)
X est le niveau N-1 épaisseur+S'il rentre dans 1.
La raison de l'ajout de 1 est le niveau N-Le montant de la fourgonnette inférieure qui a été ajouté lors de la construction du niveau N à partir de 1.
Niveau N-Puisque nous devons trouver le nombre de galettes de couche X en 1, f(N-1,X-1)appel.
La raison de la soustraction de 1 est la même que lors de l'ajout.

3. X = 2 + a[N-1]Quand f(N,X) = p[N-1] + 1
X est le niveau N-C'est la même que l'épaisseur de 1 incluant le fourgon inférieur et les galettes du milieu qui ont été ajoutées lors de la construction du niveau N.
Niveau N dans ce cas-Il s'agit du nombre de 1 galette plus les 1 galettes du milieu ajoutés lors de la configuration du niveau N.

4. 2 + a[N-1] < X ≦ 2 + 2a[N-1]Quand f(N,X) = p[N-1] + 1 + f(N-1,X-2-a[N-1])
Cela ressemble à un mélange des conditions 2 et 3.
Calculez le nombre de feuilles jusqu'à la galette du milieu de la même manière que 3.
De plus, je veux trouver le nombre de galettes du milieu vers le haut, donc f(N-1,X-2-a[N-1])appel.
La partie X est juste X moins la longueur de 3.

5. X = 3 + 2a[N-1]Quand f(N,X) = 2p[N-1] + 1
Si X est l'épaisseur actuelle du niveau N tel quel.
Dans ce cas, 2 x p, comme initialement calculé[N-1] +Il peut être obtenu par 1.

Le flux jusqu'à ce point est indiqué sur la figure. Regardez le jaune B comme une camionnette et le brun P comme une galette.

Écrivez cette condition comme une fonction récursive et appelez $ f (N, X) $ pour trouver la réponse.

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))