[PYTHON] Codeforces Round # 671 (Div.2) Examen Bacha (9/22)

Les résultats de cette fois

Impressions de cette époque

C'était une perte de temps parce que j'étais impatient et mes pensées sont devenues désordonnées. J'ai trouvé le problème E dans le jeu d'idées, mais je n'ai pas pu gagner suffisamment de temps.

Après tout ** l'exactitude et l'intuition de la considération sont encore médiocres **, donc je pense qu'il n'y a pas d'autre choix que de résoudre plus de problèmes et de les affiner.

Problème A

(Ci-après, le premier Raze est R et le second Breach est B.)

** Faites attention au dernier numéro restant **. Si le nombre de ceux restants est impair, R gagne, et sinon, B gagne. A ce moment, s'il y a un nombre impair, le nombre impair restera à la fin, il suffit donc de laisser un nombre impair pour que le premier R gagne, et s'il y a au moins un nombre impair dans le nombre impair, R gagnera. Je vais. De plus, s'il y a un nombre pair, le nombre pair restera à la fin, il suffit donc de laisser un nombre pair pour que B dans la deuxième attaque gagne, et s'il y a au moins un nombre pair dans le nombre pair, B gagne. Je vais.

** J'ai fait une erreur dans le nombre de sorties et émis 1WA **.

A.py

for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

Problème B

Ce n'était pas trivial, donc je l'ai résolu à partir d'autres problèmes. Il est important de ** réaliser l'expérience avec précision ** pour de tels problèmes graphiques.

Un escalier à marche $ n $ fait en utilisant uniquement des carrés $ n $ est appelé gentil (au début, il était ** mal lu ** comme un rectangle). Nous allons mener une expérience en considérant le cas où ce bel escalier peut être réalisé.

À ce stade, si vous ne faites pas ** un carré aussi grand que possible ** comme le montre la figure ci-dessous, vous ne pouvez pas faire seulement $ n $ carrés ($ \ car $ plus petits carrés dépasseront certainement $ n $ Parce que ça finira). Autrement dit, il ressemble à la figure ci-dessous.

La figure ci-dessus montre l'heure à laquelle $ n $ = 1 ~ 7, mais elle ne tient que lorsque $ n $ = 1,3,7. Aussi, il est clair qu'il tient quand c'est un nombre impair, et si vous faites un grand rectangle quand $ n = 2k + 1 $, ** le reste sera un rectangle de deux tailles $ k $ **. J'ai remarqué. En d'autres termes, si la taille de l'escalier que l'on peut créer est $ a \ _i $, elle doit être $ a \ _ {i + 1} = 2a \ _i + 1 $ ($ a \ _0 = 1 $).

De plus, le nombre de tuiles donné est au plus de 10 $ ^ {18} $, et $ a \ _i $ croît plus vite que la séquence isobare, donc ** une belle taille d'escalier est $ a \ _0 $ Il suffit de trouver de à $ a \ _ {29} $ **.

Par conséquent, ce que vous voulez trouver est le nombre de ** différents beaux escaliers ** qui peuvent être faits pour un nombre donné de carreaux $ x $, et différentes tailles d'escaliers auront des escaliers différents, alors faites un petit escalier sympa. Vous pouvez les faire dans l'ordre jusqu'à ce qu'ils soient épuisés. Notez également que puisque vous recevez le nombre de tuiles, vous devez soustraire $ \ frac {a \ _i (a \ _ i + 1)} {2} $ de $ x $.

B.py

cand=[1]
for i in range(100):
    cand.append(cand[-1]*2+1)
    if cand[-1]>10**18:
        break
for i in range(int(input())):
    ans=0
    x=int(input())
    for i in cand:
        j=i*(i+1)//2
        if x-j<0:
            break
        else:
            x-=j
            ans+=1
    print(ans)

Problème C

Pendant le concours, je m'empressais de penser à une solution étrange, mais quand je suis calme, ce n'est pas si difficile.

Pendant le concours, j'ai d'abord considéré les cas suivants.

(1) Lorsque la note de tout le monde est de $ x $ Vous pouvez infecter sans organiser de concours, même une seule fois.

(2) Lorsque la note totale de toutes les personnes est de $ nx $ Vous ne devez ouvrir le concours qu'une seule fois, car vous pouvez rendre tout le monde égal à x $ en réglant le montant total de la monnaie à 0.

(3) Autre que (1) et (2) ** Vous pouvez faire autre chose qu'une personne ** $ x $, et vous pouvez infecter tout le monde avec deux opérations.

En fait, (1) et (2) sont corrects, mais ** (3) n'est pas toujours correct **. Pendant le concours, j'ai pris AC en pensant que si j'avais bien ajusté la personne déjà infectée, il suffirait de le faire une fois, mais logiquement parlant ** Si au moins une personne est déjà infectée, cette personne On peut dire que tout le monde peut être infecté à la fois ** par $ x $ autre que. Probablement, si je pouvais prêter attention à la partie de ** autre qu'une personne, je pourrais le résoudre correctement, donc j'ai senti que la précision était importante pour la classification des cas.

C.py

for _ in range(int(input())):
    n,x=map(int,input().split())
    a=list(map(int,input().split()))
    if a.count(x)==n:
        print(0)
    elif sum(a)==n*x:
        print(1)
    else:
        if a.count(x)>0:
            print(1)
        else:
            print(2)

Problème D1

Comme ils sont tous différents, il est possible d'utiliser une indexation 0 à partir du plus grand nombre pair dans l'ordre décroissant et du plus petit nombre impair dans l'ordre croissant. Je pense que c'est un problème très simple.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a)
l=n//2-1 if n%2==0 else n//2
ans=[]
while len(b)>=2:
    ans.append(b.pop())
    ans.append(b.popleft())
if len(b)==1:
    ans.append(b.pop())
print(l)
print(" ".join(map(str,ans)))

Problème D2

Il semble que la mise en œuvre du code de la politique qui était finalement AC était fausse, ** je ne pouvais pas déterminer si la politique ou la mise en œuvre était fausse **. À l'avenir, je voudrais améliorer ma capacité de réflexion afin de pouvoir la mettre en œuvre après avoir soigneusement défini la politique.

Le nombre maximum de boules de glace que vous pouvez acheter dans l'ordre suivant est (ABC178-F est un sujet similaire).

Si le nombre maximum de boules de glace du même prix est $ [\ frac {n} {2}] $, la valeur maximum à D1 peut être atteinte, et s'il y en a plus, le nombre maximum sera celui que vous arrangez. Je pensais que je ne pouvais pas y parvenir, alors je l'ai arrangé de cette façon. ** Je pensais qu'il n'y avait pas d'autre arrangement rationnel **, alors j'ai choisi cet arrangement.

En regardant la réponse, lorsque vous pouvez acheter des boules de glace de $ m $, il y a des combinaisons plus petites de $ m + 1 $ boules de glace, donc ** la méthode de recherche de $ m $ par dichotomie ** Je le prenais. S'il y a une hypothèse ** quand vous pouvez acheter ** $ m $ des boules de glace **, il ne devrait y avoir aucune raison de penser à une dichotomie de la combinaison de ** monotonie et valeur maximale **, vous devez donc apprendre le typique se sentait.

D.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import deque
b=deque(a[:n//2])
c=deque(a[n//2:])
ans=[]
while len(b) or len(c):
    ans.append(c.popleft())
    if len(b)>0:
        ans.append(b.popleft())
#print(ans)
l=0
for i in range(1,n-1):
    if ans[i-1]>ans[i] and ans[i]<ans[i+1]:
        l+=1
print(l)
print(" ".join(map(str,ans)))

E problème

En raison d'une erreur de montage, il a été résolu 10 minutes après la fin du concours. Je suis très déçu. Quand un tel problème devient stable, je pense que je peux surmonter le mur à la fois, donc je vais le supporter et faire un effort.

Quand j'ai expérimenté en regardant l'échantillon, j'ai pensé que ** dans de nombreux cas, il n'est pas nécessaire de prendre lcm une fois **. Par conséquent, nous allons organiser les nombres adjacents pour qu'ils ne deviennent pas des éléments les uns des autres, mais puisque nous voulons empêcher le pgcd des nombres adjacents de devenir 0, ** faites attention à quel nombre les nombres adjacents sont des multiples **. fait. En particulier, j'ai fait attention à ** quel nombre premier chaque nombre est un multiple de **. En d'autres termes, vous pouvez le construire comme le montre la figure ci-dessous (je pense qu'il existe plusieurs façons de le construire, mais vous pouvez facilement y penser en faisant attention à ** quel nombre premier est un multiple **).

Vous pouvez faire un pgcd différent de 1 entre n'importe quel élément en ** en supposant que la partie frontière indiquée par le cercle jaune comme ci-dessus est multipliée par un de chaque nombre premier **. ..

Par conséquent, $ O (\ sqrt {n}) $ énumère les fractions et les stocke dans des diviseurs, et $ O (\ sqrt {n}) $ effectue une factorisation première et les stocke dans prime. , Les éléments qui sont des multiples de chaque nombre premier sont extraits des «diviseurs» dans l'ordre du début de l'élément «premier» et stockés dans le tableau «an» qui est sorti comme réponse. De plus, comme je veux enregistrer dans l'ordre croissant et que la vitesse de retrait est stable, j'ai défini respectivement les diviseurs et les premiers.

De plus, vous pouvez stocker des multiples de chaque nombre premier restant dans les diviseurs de manière appropriée dans ʻans, mais sachez que ** la partie frontière doit être faite séparément **. Ceci peut être facilement réalisé en stockant plus tard le produit du premier que vous regardez et le prochain premier dans ʻans (voir Implémentation pour plus de détails).

De plus, comme dans le premier échantillon, il est nécessaire de prendre lcm ** lorsqu'il n'y a que deux facteurs premiers différents et que $ n $ est représenté par le produit des facteurs premiers **. Dans d'autres cas, vous pouvez toujours remplir les conditions avec votre propre méthode de construction.

E.cc

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

//n n'est pas inclus
set<ll> divisors;//Prêt à stocker sur(Je veux le supprimer)

void make_divisors(ll n){
    FOR(i,2,sqrt(n)){
        if(n%i==0){
            divisors.insert(i);
            if(i!=n/i){
                divisors.insert(n/i);
            }
        }
    }
}

set<ll> prime;//Carte pour enregistrer combien de chaque nombre premier est sorti par factorisation premier

//O(√n)
//Aligné(la carte est automatiquement organisée par clé)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Même si la clé n'existe pas dans la carte, elle sera créée automatiquement.
    prime.insert(n);return;
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n;cin>>n;
        vector<ll> ans;
        divisors.clear();
        prime.clear();
        make_divisors(n);
        prime_factorize(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            cout<<*prime.begin()<<" "<<*++prime.begin()<<" "<<n<<endl;
            cout<<1<<endl;
            continue;
        }
        for(auto i=prime.begin();i!=prime.end();i++){
            deque<ll> sub;
            ll l,r;l=*i;r=0;
            if(++i!=prime.end()){
                r=*i;
                sub.PB(l*r);
                divisors.erase(l*r);
            }
            --i;
            auto j=divisors.begin();
            while(j!=divisors.end()){
                if((*j)%(*i)==0){
                    sub.PB(*j);
                    j=divisors.erase(j);
                }else{
                    j++;
                }
            }
            while(SIZE(sub)){
                ll p=sub.back();
                sub.pop_back();
                ans.PB(p);
            }
        }
        ans.PB(n);
        if(SIZE(prime)==2 and (*prime.begin())*(*++prime.begin())==n){
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<1<<endl;
        }else{
            REP(i,SIZE(ans)){
                if(i!=SIZE(ans)-1)cout<<ans[i]<<" ";
                else cout<<ans[i]<<endl;
            }
            cout<<0<<endl;
        }
    }
}

Problème F

Je vais sauter cette fois