[PYTHON] Codeforces Round # 654 (Div.2) Critique Bacha (8/18)

Les résultats de cette fois

Impressions de cette époque

Cette fois, j'ai pu le résoudre avec un très bon feeling. Cependant, j'ai manqué Gokan parce que j'ai déjeuné en chemin. Je suis très déçu. Je sens que mes sens sont progressivement aiguisés, alors j'aimerais continuer à faire de mon mieux. Je ferai de mon mieux pour viser AtCoder Blue et Codeforces Purple, qui sont mes objectifs pendant les vacances d'été.

Problème A

S'il y a un nombre pair de bâtons, fabriquez un bâton d'une longueur de $ n + 1 $, et s'il y a un nombre impair de bâtons, fabriquez un bâton d'une longueur de $ n $. Le nombre de bâtons sera de $ [\ frac {n} {2}] $.

Cela peut être prouvé en considérant les bâtons de la longueur qui peut être faite dans l'ordre croissant, mais je vais l'omettre ici.

A.py

for _ in range(int(input())):
    n=int(input())
    print(-(-n//2))

Problème B

C'est un problème qui semble être un piège, mais vous pouvez trouver la bonne réponse en classant soigneusement chaque cas.

Tout d'abord, pensez à choisir $ n $ jours consécutifs pour vous connecter, mais ** une semaine ** se connecte toujours si $ n $ jours est inclus, alors que ** plusieurs semaines ** Si vous chevauchez, $ n $ jours peuvent ne pas être connectés. Par conséquent, si une semaine est $ i (1 \ leqq i \ leqq r) $ jours, considérons le cas de $ i \ geqq n $ et le cas de $ i <n $.

(1) Dans le cas de $ i \ geqq n $ Lors de la sélection de $ n $ jours consécutifs pour se connecter, ce sera comme indiqué dans la figure ci-dessous, et pour tout $ i $, la forme correspondra à $ 1 $ lors d'un déplacement en parallèle, donc lorsque $ r \ geqq n $, 1 Lorsque $ r <n $ dans la rue, il y a 0 rue.

(2) Lorsque $ i <n $ Lorsque vous choisissez $ n $ jours consécutifs pour vous connecter, assurez-vous de couvrir plusieurs semaines comme suit: Par conséquent, les formes qui ne sont pas les mêmes lorsqu'elles sont déplacées en parallèle peuvent être ** distinguées le premier jour ** de $ n $ jours consécutifs, ce qui donne des rues $ i $.

De plus, puisqu'il s'agit de $ 1 \ leqq i \ leqq min (n-1, r) $, $ \ sum \ _ {i = 1} ^ {min (n-1, r)} i = \ _ {min (n, r) +1)} C \ _2 $ est la réponse. De plus, j'ai fait une erreur de l'ordre de ** $ i $ ** Je ne correspondais pas à l'échantillon.

B.py

for _ in range(int(input())):
    n,r=map(int,input().split())
    if r<n:
        print(r*(r+1)//2)
    else:
        print(1+(n-1)*n//2)

Problème C

Le premier type d'invité est sélectionné parmi le plus grand nombre de cookies et le deuxième type d'invité est sélectionné parmi le moins de cookies. À ce stade, déterminez si la commande de l'invité peut être décidée de sorte que chaque invité n'ait plus de cookie lors du choix d'un cookie.

Tout d'abord, le deuxième type d'invité ** semble avoir peu de choix car ils choisissent le cookie le plus petit **, je souhaite donc conserver autant de cookies que possible. Par conséquent, j'ai pensé qu'il serait préférable de ** sélectionner d'abord le deuxième type d'invité **, et de penser que le nombre de cookies pouvant être sélectionnés par le deuxième type d'invité est au plus de $ min (a, b) $. C'était. De plus, lorsque le deuxième type d'invité choisit un cookie, ** le nombre restant du cookie le plus petit ne peut pas être choisi deux fois **, donc $ min (a, b) $ est le cookie maximum à choisir. Ce sera le nombre de feuilles. Par conséquent, s'il s'agit de $ m \ leqq min (a, b) $, le deuxième type d'invité peut toujours choisir le plus petit cookie et laisser le cookie. De plus, $ (min (a, b) -m) + max (a, b) = a + bm $ cookie reste dans ** après que le deuxième invité a été sélectionné, mais le reste Tous les cookies du premier type peuvent être sélectionnés par le premier type d'invité, donc s'il s'agit de $ a + bm \ leqq n $, le premier type d'invité peut également sélectionner le cookie. À partir de ce qui précède, "Non" doit être affiché lorsque $ m> min (a, b) $ ou $ a + b <n + m $, et "Oui" doit être affiché à d'autres moments.

C.py

for _ in range(int(input())):
    a,b,n,m=map(int,input().split())
    if m>min(a,b):
        print("No")
    elif n+m>a+b:
        print("No")
    else:
        print("Yes")

Problème D

J'aime personnellement ** utiliser la symétrie ** car cela donne une meilleure visibilité (même si mes goûts sont susceptibles d'être différents).

Le problème est de rendre $ f (A) = (max (R) -min (R)) ^ 2 + (max (C) -min (C)) ^ 2 $ aussi petit que possible. Tout d'abord, il est facile de comprendre si vous considérez le cas unidimensionnel, mais en ** divisant le nombre de 1 aussi régulièrement que possible **, $ f (A) $ deviendra plus petit.

Maintenant, pensez à organiser les $ k $ 1 dans l'ordre aussi régulièrement que possible dans chaque ligne et colonne. De plus, en répartissant uniformément, j'y ai pensé en observant ** être conscient de la symétrie ** et ** décider de certaines règles **. De plus, $ max (R) -min (R) $ et $ max (C) -min (C) $ ne deviennent pas 0 lorsque $ k % n! = 0 $, alors ** les met à 1 respectivement. Considérez l'emplacement souhaité **. Ensuite, vous pouvez voir qu'il peut être arrangé selon cette règle en distribuant dans l'ordre de ① → ② → ③ →… dans la figure ci-dessous.

Tout d'abord, dans le cas de (1), j'ai eu l'idée car il s'agit d'une composante diagonale et a une symétrie élevée. Aussi, j'ai pensé que je devrais placer 1 dans le ** composant diagonal ** (partie verte) à côté, mais à ce moment aussi $ max (R) -min (R) $ Et $ max (C) -min (C) $ change toujours en gardant 0 ou 1. En effet, les ** lignes et colonnes contenues dans les composants bleu, vert et jaune sont $ n $ chacune et sont toutes différentes **, donc la somme ne sera pas plus de 2 plus grande que les autres lignes et colonnes. est. Par conséquent, il peut être généralisé qu'ils doivent être agencés de sorte qu'ils soient tous différents les uns des autres, et ils doivent être disposés dans l'ordre dans les composantes diagonales comme sur la figure ci-dessus. De plus, ce composant peut être exprimé comme $ (i, (i + j) % n) $ dans $ 0 \ leqq i, j \ leqq n-1 $, et $ i, j $ est déplacé vers $ k $. Tout ce que vous avez à faire est de sortir celui dans lequel 1 est placé.

D.py

for _ in range(int(input())):
    n,k=map(int,input().split())
    ans=[[0]*n for i in range(n)]
    f=False
    for j in range(n):
        for i in range(n):
            if k==0:
                f=True
                break
            k-=1
            ans[i][(i+j)%n]=1
        if f:
            break
    r=[sum(ans[i]) for i in range(n)]
    mar,mir=max(r),min(r)
    c=[sum([ans[i][j] for i in range(n)]) for j in range(n)]
    mac,mic=max(c),min(c)
    print((mar-mir)**2+(mac-mic)**2)
    for i in range(n):
        print("".join(map(str,ans[i])))

Problème E1

J'ai déjeuné et je n'ai pas pu l'appliquer, je suis désolé! !!

** Je suppose que vous battrez tous les ennemis **, donc si vous avez $ x $ candy au début, combattez l'ennemi $ i (0 \ leqq i \ leqq n-1) $ ème Parfois, j'ai $ x + i $ bonbons. De plus, comme il suffit d'avoir plus de bonbons que l'ennemi, la $ i $ ème personne peut gagner ** si l'ennemi a ** $ x + i $ ou moins de bonbons. Aussi, comment sélectionner un tel ennemi peut être trouvé par bisect_right si vous ** triez le nombre de bonbons ennemis ** (j'ai émis 1WA sans trier ...). De plus, comme la personne avant la ** $ i $ ème personne a déjà sélectionné les ennemis de la $ i $ personne **, le nombre réel d'ennemis pouvant être sélectionnés est "($ x + i $ ou moins de bonbons). Nombre d'ennemis) - $ i $ "personnes. De plus, s'il y a une personne dont la valeur est inférieure à $ 0 $, il y a 0 façons de sélectionner un ennemi et il est divisible par $ p $, donc cela ne satisfait pas le thème. Aussi, quand $ x \ geqq max (a) $, ** n'importe quel ennemi peut être sélectionné, donc $ n! $ Street **, et quand $ x <min (a) $, ** il n'y a pas de méthode de sélection. À partir de $ 0 $ street **, les deux sont divisibles par $ p $, vous devriez donc en rechercher un qui n'est pas divisible par $ p $ dans la plage $ min (a) \ leqq x <max (a) $. ..

E.py

n,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=[]
from bisect import bisect_right
for i in range(min(a),max(a)):
    for j in range(n):
        b=bisect_right(a,i+j)-j
        if b<=0:
            break
        elif b%p==0:
            break
    else:
        ans.append(i)
print(len(ans))
print(" ".join(map(str,ans)))

Après le problème E2

Je vais sauter cette fois