[PYTHON] Code de l'éducation forces Round 90 Bacha Review (8/19)

Les résultats de cette fois

Impressions de cette époque

J'ai renoncé à penser que ce serait impossible même si je connaissais le sens de l'idée. Je ne sais pas si j'abandonne et laisse tomber, donc dans ce cas, j'aimerais prendre une profonde inspiration et ensuite procéder avec considération **. Même lorsque je suis pressé, je veux me calmer et comprendre ** ce qui est difficile et ce que je veux améliorer **.

Problème A

Si vous souhaitez rendre le premier beignet moins cher que le deuxième, il est préférable de n'acheter qu'un seul premier beignet et un ensemble du deuxième beignet. À ce stade, si $ a <c $, cela peut être moins cher, donc 1 est la réponse. De plus, quand c'est $ a \ geqq c $, il ne peut pas être moins cher pour aucun achat, donc -1 est la réponse.

Si vous souhaitez rendre le deuxième beignet moins cher que le premier, il est préférable de n'acheter que $ b $ pour le premier beignet et un seul ensemble pour le deuxième beignet. À ce stade, si $ c <a \ fois b $, cela peut être moins cher, donc $ b $ est la réponse. De plus, $ c \ geqq a \ times b $ time ne peut être meilleur marché pour aucun achat, donc -1 est la réponse.

A.py

for _ in range(int(input())):
    a,b,c=map(int,input().split())
    ans=[]
    if a<c:
        ans.append(1)
    else:
        ans.append(-1)
    if a*b>c:
        ans.append(b)
    else:
        ans.append(-1)
    print(" ".join(map(str,ans)))

Problème B

Je pense que c'est un problème courant. Sélectionnez et supprimez ceux adjacents avec 0 et 1, et le joueur perd quand il n'est pas utilisable. ** Si 0 et 1 sont tous les deux inclus dans la chaîne, il y a des 0 et des 1 qui sont adjacents l'un à l'autre **, donc la dernière chaîne restante (qui peut être une chaîne vide) est 0 ou 1. Reste seulement. Par conséquent, le nombre de fois où des 0 et des 1 adjacents peuvent être sélectionnés est le plus petit des 0 et 1 inclus. Par conséquent, si ce nombre est impair, ce sera la première victoire, et s'il est pair, ce sera la deuxième victoire.

B.py

for _ in range(int(input())):
    s=input()
    print(["NET","DA"][min(s.count("1"),s.count("0"))%2])

Problème C

C'était difficile à lire car l'énoncé du problème était un pseudo-code. La personne Writer l'a-t-elle sautée?

Lorsque vous regardez la chaîne de caractères, la variable cur change comme -1 pour "-" et +1 pour "+". La valeur initiale de cur lors de l'analyse d'une chaîne de caractères est init, et elle augmente dans l'ordre à partir de 0.

Pour de tels problèmes, ** expérimenter et saisir le comportement ** améliorera les perspectives. Par conséquent, si vous expérimentez avec le premier échantillon «- + -», ce sera comme suit.

Lorsque l'expérience ci-dessus est verbalisée, en considérant la somme cumulée dans l'ordre à partir de la gauche, elle scanne jusqu'à ** où la mise à jour de la valeur minimale se produit ** (initialement définie sur 0), et si elle est mise à jour, retourne au début. En répétant ce qui précède, si vous cochez tous les endroits où la mise à jour a lieu, ** scannez tous les éléments en dernier ** et l'analyse se terminera.

En d'autres termes, la réponse est de trouver la somme des index mis à jour (indexés en 1) tout en sauvegardant la valeur minimale tout en regardant la somme cumulée dans l'ordre de l'avant, et d'ajouter la longueur de la chaîne de caractères comme balayage final.

C.py

from itertools import accumulate
for _ in range(int(input())):
    s=input()
    l=len(s)
    t=[1 if s[i]=="+" else -1 for i in range(l)]
    t=list(accumulate(t))
    now=0
    ans=0
    for i in range(l):
        if t[i]<now:
            ans+=(i+1)
            now=t[i]
        if i==l-1:
            ans+=(i+1)
    print(ans)

Problème D

J'étais sur le point d'atteindre la bonne réponse, mais j'ai perdu ma concentration. Après tout, je pense que ce ** maintenir la mentalité lorsque je suis sur le point de perdre ma concentration ** est le plus grand défi pour moi.

Prenons le cas où la somme des nombres correspondant aux indices pairs lorsqu'une certaine sous-colonne continue est sélectionnée et inversée est le maximum. Tout d'abord, comme vous pouvez facilement le voir, si la longueur de la sous-chaîne continue sélectionnée est impaire, la somme ne change pas avant et après l'inversion de la sous-chaîne continue sélectionnée, alors considérez ** pair **.

Par conséquent, pour les éléments contenus dans la colonne contiguë de longueur paire sélectionnée, les éléments avec l'index impair sont sélectionnés à la place des éléments avec l'index pair. Aussi, à ce moment, j'ai essayé de penser à une sous-chaîne continue qui maximise la différence de changement lors du passage de pair à impair, mais ** Comme il est difficile de faire avec la méthode gourmande, DP est défini comme la somme partielle maximale. Je pense que c'est une idée naturelle de penser en utilisant ** (je n'ai pas pu organiser mes pensées pendant le concours ...).

Ici, lorsqu'une sous-colonne continue est sélectionnée (** considérer avec des hypothèses ), il est possible de sélectionner un index pair avant et après la sous-colonne continue, et un index impair dans la sous-colonne continue. Oui ( 3 types d'états !! **), DP peut être défini comme suit.

$ dp [i] [j]: = $ (somme maximale dans chaque état $ j $ lorsque $ i $ index sont sélectionnés)

Cependant, lorsque $ j = 0 $, la sous-colonne continue n'a pas encore été sélectionnée, lorsque $ j = 1 $, la sous-colonne continue n'a pas été sélectionnée, et lorsque $ j = 2 $, la sous-colonne continue n'a pas encore été sélectionnée. C'est dit. (Les sous-colonnes continues sont susceptibles d'avoir deux modèles, ** un modèle qui gère la fin de la sous-colonne continue et prend l'accumulation à la fin, et un ** modèle qui gère si la sous-colonne continue est sélectionnée, alors gardez-le vers le bas Je veux.)

Notez également que vous voulez trouver la somme des éléments de l'index sélectionné, donc ce devrait être le $ i $ th, pas le ** $ i $ th **.

De plus, il existe des ** modèles commençant par un index pair et des modèles ** commençant par un index impair ** pour les sous-colonnes continues de longueur paire, et le premier correspondant à $ i $ est $ a_ {2i-1} $. $ a_ {2i} $, ce dernier correspondant à $ i $ est $ a_ {2i} $ et $ a_ {2i + 1} $.

D'après ce qui précède, compte tenu de la transition de DP qui peut être obtenue en effectuant DP pour chacun des deux motifs, c'est comme suit. De plus, dans ce qui suit, nous considérons un modèle qui commence par un indice impair.

(1) Lorsque $ j = 0 $ Il n'y a pas d'autre choix que de sélectionner des éléments avec des index pairs, comme indiqué ci-dessous. dp[i][0]=dp[i-1][0]+a[2i]

(2) Lorsque $ j = 1 $ Il n'y a pas d'autre choix que de sélectionner un élément avec un index impair, et il peut y avoir deux sources de transition, $ dp [i-1] [0] et dp [i-1] [1] $, donc c'est comme suit. dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[2*i-1]

(3) Lorsque $ j = 2 $ Il n'y a pas d'autre choix que de sélectionner un élément avec un index pair, et il peut y avoir deux sources de transition, $ dp [i-1] [1] et dp [i-1] [2] $, donc c'est comme suit. dp[i][2]=max(dp[i-1][1],dp[i-1][2])+a[2*i]

De plus, si vous l'implémentez en faisant attention à $ i = 0 $ ~ $ [\ frac {n-1} {2}] $, ce sera comme suit.

D.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    dp0=[[0,0,0] for i in range((n-1)//2+1)]
    for i in range((n-1)//2+1):
        if i==0:
            dp0[i][0]=a[2*i]
            continue
        dp0[i][0]=dp0[i-1][0]+a[2*i]
        dp0[i][1]=max(dp0[i-1][0],dp0[i-1][1])+a[2*i-1]
        dp0[i][2]=max(dp0[i-1][1],dp0[i-1][2])+a[2*i]
    dp1=[[0,0,0] for i in range((n-1)//2+1)]
    for i in range((n-1)//2+1):
        if i==0:
            dp1[i][0]=a[2*i]
            if 2*i+1<n:dp1[i][1]=a[2*i+1]
            continue
        dp1[i][0]=dp1[i-1][0]+a[2*i]
        if 2*i+1<n:dp1[i][1]=max(dp1[i-1][0],dp1[i-1][1])+a[2*i+1]
        if 2*i<n:dp1[i][2]=max(dp1[i-1][1],dp1[i-1][2])+a[2*i]
    #print(dp0)
    #print(dp1)
    print(max(dp0[(n-1)//2]+dp1[(n-1)//2]))

Problème E

Par exemple, quand $ x = 108, k = 3 $, cela devient $ 108.109.110.111 $, mais quand il n'y a pas de report, $ f (x + 1) = f (x) + 1 $ tient. Par conséquent, nous classerons les cas avec ** no carry et avec **, et chercherons les cas avec $ n $ donné. S'il y a plusieurs candidats $ x $, le plus petit doit être affiché. (Ici, évidemment ** j'ai abandonné l'implémentation car c'était gênant de la porter **, mais j'ai pu le résoudre après le concours, je le regrette ...)

(1) Lorsqu'il n'y a pas de report

En regardant le dernier chiffre, c'est $ i, i + 1,…, i + k $. A ce moment, quand $ i, i + 1,…, i + k $ et $ i + l, i + l + 1,…, i + l + k $ sont comparés à $ l> 0 $, ce dernier est au dessus. La somme de chaque chiffre est $ (k + 1) \ fois l $ de moins que le premier. Par conséquent, ** le chiffre le moins significatif doit être aussi grand que possible **, et $ 9-k, 9-k + 1,…, 9-k + k $ est optimal (✳︎). À ce stade, la somme des chiffres les moins significatifs est $ \ frac {(18-k) (k + 1)} {2} $, donc les chiffres au-dessus sont $ n- \ frac {(18-k). Envisagez de construire avec (k + 1)} {2} $. Ici, ** car il n'y a pas de report, les chiffres supérieurs sont tous les mêmes **, et si la somme des chiffres est $ X $, alors $ n- \ frac {(18-k) (k + 1)} {2} = X \ fois (k + 1) $ doit tenir. Lorsque cela est vrai, $ X = \ frac {n- \ frac {(18-k) (k + 1)} {2}} {k + 1} $. De plus, afin de rendre le chiffre supérieur aussi petit que possible, si 9 est placé dans l'ordre à partir du chiffre inférieur, le nombre excédentaire doit être placé dans le chiffre le plus significatif. De plus, à propos de (✳︎), $ n \ leqq \ frac {(18-k) (k + 1)} {2} $ n'est pas optimal, donc ** $ x = 0 $ ~ $ 9-k $ à ce moment. Vous pouvez essayer toutes les rues **.

(2) Lorsqu'il y a un report

À ce stade, il est nécessaire de vérifier à la fois les informations sur (1) ** combien de 9 sont consécutifs à l'exclusion du chiffre le plus bas ** et (2) ** quel numéro le chiffre 9 le plus bas apparaît dans **. .. En ce qui concerne (1), nous avons étudié jusqu'à 19 $ cette fois en raison de la restriction selon laquelle $ n $ est d'environ 150. De plus, pour (2), vous pouvez essayer le nombre (indexé à 0) où le chiffre le moins significatif est 9 de 0 $ à $ k-1 $. Par conséquent, considérons le premier comme $ num9 $ et le second comme $ j $. De plus, comme il est compliqué d'écrire en lettres, la situation actuelle est représentée dans un diagramme. (Si vous ne comprenez pas le cas de (1), vous pouvez dessiner un diagramme.)

Comme le montre la figure ci-dessus, +1 dans le report est $ 1 \ times (kj) $, les 9 consécutifs à l'exclusion du chiffre le moins significatif sont $ num9 \ times 9 \ times (j + 1) $, et le chiffre le moins significatif est $ \ frac. {(18-j) (j + 1)} {2} + \ frac {(kj) (kj-1)} {2} $, qui est soustrait de $ n $ et reste (1) ) Et la même considération. Les bases sont les mêmes, mais notez seulement que ** le dernier chiffre du chiffre supérieur ne peut pas être 9 et est 8 ** pour éviter le report.

Ce qui précède est mis en œuvre et devient comme suit. Quand je l'ai résolu, j'ai senti que l'implémentation était lourde, mais j'ai senti que c'était un problème que ** je pouvais améliorer la perspective d'implémentation en utilisant non seulement la verbalisation mais aussi des diagrammes **.

E.py

for _ in range(int(input())):
    n,k=map(int,input().split())
    ans=[]
    #Ne pas porter
    if n<=(18-k)*(k+1)//2:
        for i in range(10):
            check=n
            for j in range(k+1):
                if i+j>9:
                    break
                else:
                    check-=(i+j)
            else:
                if check==0:
                    ans.append(i)
    else:
        check=n-(18-k)*(k+1)//2
        if check%(k+1)==0:
            check//=(k+1)
            i,j=check%9,check//9
            if i==0:
                ans.append(int("9"*j+f"{9-k}"))
            else:
                ans.append(int(f"{i}"+"9"*j+f"{9-k}"))
    #Il y a un report
    for num9 in range(20):
        for j in range(k):
            check=n-(18-j)*(j+1)//2-(k-j)*(k-j-1)//2
            check-=(num9*9*(j+1))
            check-=(1*(k-j))
            #print(check)
            if check>=0:
                if check%(k+1)==0:
                    check//=(k+1)
                    h,i=check%9,check//9
                    #Vous n'êtes pas obligé de diviser par 9
                    if i==0:
                        if h==0:
                            ans.append(int("9"*num9+f"{9-j}"))
                        else:
                            ans.append(int(f"{h}"+"9"*num9+f"{9-j}"))
                    else:
                        check-=8
                        h,i=check%9,check//9
                        if h==0:
                            ans.append(int("9"*i+"8"+"9"*num9+f"{9-j}"))
                        else:
                            ans.append(int(f"{h}"+"9"*i+"8"+"9"*num9+f"{9-j}"))
    #print(ans)
    if len(ans):
        print(min(ans))
    else:
        print(-1)

Après problème F

Je vais sauter cette fois