[PYTHON] Codeforces Round # 592 (Div.2) Examen Bacha (11/03)

Les résultats de cette fois

Impressions de cette époque

J'ai fait une erreur en mathématiques au lycée à cause du problème C. En partie parce que j'ai utilisé la bibliothèque pour la deuxième fois, je suis déçu de ne pas pouvoir la déboguer pendant le concours.

De plus, le problème D était si simple que j'ai été encore plus déçu ... J'aimerais me nourrir de mes regrets, mais c'est difficile de gérer les bugs.

Problème A

C'est facile. Tout ce que vous avez à faire est de préparer suffisamment de stylos et de crayons pour la conférence et les cours pratiques. En d'autres termes, vous n'avez besoin que de $ - (- a // c) et - (- b // d) $ livres, respectivement.

A.py

for _ in range(int(input())):
    a,b,c,d,k=map(int,input().split())
    x=-(-a//c)
    y=-(-b//d)
    if x+y>k:
        print(-1)
    else:
        print(x,y)

Problème B

Je pense que c'est un problème qui nécessite une puissance esper. ** Expérimentez avec des échantillons **, vous constaterez que ** toutes les pièces peuvent être tracées si les pièces d'extrémité sont connectées aux étages supérieurs et inférieurs **. Par conséquent, si cela s'applique à d'autres cas, il est préférable de ne suivre que la pièce de cet étage ou de passer à un autre étage dans la pièce la plus proche du bord ** tandis que les étages supérieur et inférieur sont connectés. est. Vous pouvez le voir en regardant la figure ci-dessous.

Par conséquent, vous pouvez écrire le code suivant en tenant compte des trois modèles de déplacement vers un autre étage en partant des extrémités gauche et droite et en ne traçant que la pièce sur un étage.

B.py

for _ in range(int(input())):
    n=int(input())
    s=list(map(int,input()))
    ans=n
    if 1 not in s:
        print(ans)
        continue
    for i in range(n):
        if s[i]==1:
            ans=max(ans,n*2-i*2)
            break
    for i in range(n-1,-1,-1):
        if s[i]==1:
            ans=max(ans,n*2-(n-1-i)*2)
            break
    print(ans)

Problème C

Il y avait un problème ** comme avoir à utiliser un entier de 128 bits **, donc j'étais impatient et ne pouvais pas déboguer. Dans ce problème, $ w, d, p, n $ est donné pour déterminer s'il existe un entier non négatif $ x, y, z $ qui satisfait ce qui suit, et si tel est le cas, l'ensemble approprié est sélectionné. Il suffit de demander.

wx+dy=p…① x+y+z=n…②

Premièrement, il n'y a que deux équations pour les trois variables $ x, y et z $, donc la réponse n'est pas déterminée de manière unique **. Ici, $ z $ n'apparaît que dans ②, alors envisagez de décider d'abord $ x, y $. En d'autres termes, si vous regardez l'équation (1), vous pouvez voir qu'il s'agit d'une équation quadratique linéaire indéfinie, donc résolvez ceci pour trouver un ensemble de $ x, y $ qui rend $ x + y $ aussi petit que possible, et que $ x, y $ est $. Si x + y \ leqq n $ est satisfait, $ z $ existe également.

Maintenant que $ d \ <w $, vous devriez viser à rendre $ x $ aussi grand que possible ($ \ leftrightarrow $ ** $ y $ aussi petit que possible **). De plus, si vous utilisez la Bibliothèque d'équations binaires linéaires indéfinies créée hier, $ x = x \ _ 0 + m * b, y = y \ _0- Vous pouvez trouver $ x \ _0, y \ _0, a, b $ qui est m * a $. Par conséquent, lorsque $ y \ _0 $ est positif, $ m = floor (y \ _ 0, a) $, et lorsque $ y \ _0 $ est négatif, $ m = ceil (-y \ _ 0, a) $. Alors, $ y $ devient le minimum, donc $ x, y $ obtenu pour ce $ m $ est un ensemble de $ x, y $ qui minimise $ x + y $, et cela satisfait la condition ci-dessus. Pensez-y.

C_overflow.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 sont incrémentées de 1 pour celles sans D et les variables de boucle sont décrémentées de 1 pour celles avec D.
//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

//Valeur de retour:Engagements maximums pour a et b
// ax + by = gcd(a, b)Rencontrer(x, y)Est stocké
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=extGCD(b,a%b,y,x);
    y-=a/b*x;
    return d;
}


signed main(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,p,w,d;cin>>n>>p>>w>>d;
    if(p%gcd(w,d)!=0){
        cout<<-1<<endl;
        return 0;
    }
    ll f=gcd(w,d);
    ll h=p/f;
    ll x,y;
    extGCD(w,d,x,y);
    //À ce stade, y doit être aussi petit que possible(x est grand)
    x*=h;y*=h;
    // /cout<<x<<" "<<y<<endl;
    w/=f;
    d/=f;
    if(y>=0){
        ll g=y/w;
        x+=g*d;
        y-=g*w;
    }else{
        ll g=(-y+(w-1))/w;
        x-=g*d;
        y+=g*w;
    }
    //cout<<x<<" "<<y<<endl;
    if(x<0 or x+y>n){
        cout<<-1<<endl;
    }else{
        //cout<<x<<endl;
        //cout<<(n-x-y)<<endl;
        cout<<x<<" "<<y<<" "<<(n-x-y)<<endl;
    }
}

C.py

from sys import setrecursionlimit
setrecursionlimit(10**8)
def extgcd(a,b,x,y):
    if b==0:
        x[0]=1
        y[0]=0
        return a
    e=extgcd(b,a%b,y,x)
    y[0]-=(a//b)*x[0]
    return e

n,p,w,d=map(int,input().split())
from math import gcd
if p%gcd(w,d)!=0:
    print(-1)
    exit()
f=gcd(w,d)
h=p//f
x,y=[0],[0]
extgcd(w,d,x,y)
x=x[0]*h
y=y[0]*h
w//=f
d//=f
if y>=0:
    g=y//w
    x+=g*d
    y-=g*w
else:
    g=-(y//w)
    x-=g*d
    y+=g*w
if x<0 or x+y>n:
    print(-1)
else:
    print(x,y,n-x-y)

Problème D

C'était 2000 fois plus facile que le problème C une fois résolu après le concours. Quelle?

Quand je l'ai lu pour la première fois, je pensais que c'était un arbre DP, mais je n'ai pas à faire grand chose. Premièrement, la condition que les sommets contenus dans le chemin représenté par trois sommets différents soient peints dans des couleurs différentes est que ** il ne doit y avoir aucun sommet de degré 3 ou supérieur **. Cela peut être démontré par la méthode de l'absurdité.

Pour le moment, il n'y a qu'un ** graphe de chemin ** en tant que graphe concaténé dans lequel l'ordre de tout sommet est égal ou inférieur à 2 et n'inclut pas de chemin fermé. Vous pouvez facilement le comprendre en étendant les côtés dans l'ordre à partir du haut de l'extrémité (d'ordre 1). Par conséquent, il détermine d'abord s'il s'agira d'un graphe de chemin, et s'il ne s'agit pas d'un graphe de chemin, il génère immédiatement -1. D'un autre côté, en ce qui concerne les graphiques de chemin, il est facile de montrer qu'il existe un moyen de peindre des couleurs qui satisfont toujours les conditions. En d'autres termes, lorsque vous peignez la couleur $ a, b, c $ à partir de l'arête, les sommets restants sont uniquement peints comme $ a, b, c, a, b, c,… $. Par conséquent, il suffit de trouver le coût de chacune des trois façons de peindre les couleurs des trois sommets à la fin du graphe de chemin (3! Façons) et de trouver la valeur minimale **. De plus, 3! Streets peut être écrit avec la fonction de permutation, et dans chaque cas, il est seulement nécessaire d'effectuer des calculs jusqu'à 10 $ ^ 5 $ fois, donc cela fonctionne suffisamment vite. La somme cumulée peut réduire le multiple constant, mais ce n'est pas nécessaire car il y a une marge dans le montant du calcul.

D.py

n=int(input())
c=[list(map(int,input().split())) for i in range(3)]
edges=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)
for i in range(n):
    if len(edges[i])>2:
        print(-1)
        exit()
path=[]
for i in range(n):
    if len(edges[i])==1:
        path.append(i)
        break
#print(path)
#print(edges)
seen=[False]*n
seen[path[-1]]=True
#exit()
while True:
    for i in edges[path[-1]]:
        if not seen[i]:
            path.append(i)
            seen[i]=True
            break
    else:
        break
#print(path)
d=[[0]*n for i in range(3)]
for i in range(3):
    now=0
    for j in path:
        d[i][now]=c[i][j]
        now+=1
#print(d)
from itertools import permutations
ans=10**30
now=[]
for i in permutations(range(3),3):
    ans_sub=0
    now_sub=[0]*n
    for j in range(n):
        now_sub[path[j]]=i[j%3]+1
        ans_sub+=d[i[j%3]][j]
    if ans_sub<ans:
        ans=ans_sub
        now=now_sub
print(ans)
print(" ".join(map(str,now)))

Après le problème E

Je ne résoudrai pas cette fois.