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.

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

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

Recommended Posts

Atcoder ABC115 Exercice de questions passées
AtCoder ABC176
AtCoder ABC177
AtCoder ABC 174 Python
AtCoder ABC 175 Python
Examen des questions passées d'AtCoder (12 / 6,7)
AtCoder ABC 177 Python (A ~ E)
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C en Python
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D en Python
Atcoder ABC165 A-D en Python
Atcoder ABC166 A-E en Python
AtCoder ABC 182 Python (A ~ D)
J'ai participé à AtCoder (ABC158)
Atcoder ABC169 A-E en Python
AtCoder ABC177 A-D avec python
Concours AtCoder pour débutants Défi des questions passées 6
Concours AtCoder pour débutants Défi des questions passées 4
ABC168
ABC164
AtCoder Grand Contest Past Question Challenge 2
Concours AtCoder pour débutants Défi des questions passées 9
Résoudre Atcoder ABC169 A-D avec Python
Atcoder ABC125 C --GCD sur tableau noir
ABC174
Concours AtCoder pour débutants Défi des questions passées 7
AtCoder Grand Contest Défi des questions passées 1
Concours AtCoder pour débutants Défi des questions passées 10
Résolu AtCoder ABC 114 C-755 avec Python3
Modèle AtCoder ABC 179 Python (A ~ E)
ABC175
AtCoder Beginner Contest 066 Revoir les questions précédentes
ABC170
Concours AtCoder Débutants Défi des questions passées 5
J'ai participé à AtCoder (édition ABC169)
ABC182
ABC153
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
Atcoder ABC60 D - Solution séparée de sac à dos simple
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
Atcoder ABC099 C - Solution séparée de Strange Bank
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes