Editorial ufficiale ed assolutamente serio per il problema vasi2
Viste le numerose richieste, ho deciso di pubblicare una spiegazione dettagliata e rigorosa per la risoluzione del problema vasi2.
Riassunto del testo
Mattia non ha niente di meglio da fare che spostare dei vasi.
Inizialmente tutti i suoi N vasi sono ordinati e numerati da 0 a N-1 e vuole fare le seguenti Q operazioni:
- spostare il vaso in posizione i in posizione j (s)
- leggere il numero del vaso in posizione i (c)
Idea risolutiva
La prima cosa da notare è che il testo del problema è in italiano e di conseguenza sarà necessario scrivere codice in italiano. In caso contrario la nostra soluzione non verrà valutata da training.olinfo e l’esito della sottoposizione sarà WL cioè “Wrong Language”.
Scelto il linguaggio più appropriato, ci serve trovare una struttura che supporti tutte le operazioni che Mattia desidera insistentemente eseguire. In questo caso fa al caso nostro il mucchialbero: una struttura che combina la proprietà di un albero con quelle di un mucchio. All’interno di questa struttura i vasi sono ammucchiati in due modi contemporaneamente:
- i vasi più grandi stanno sotto nel mucchialbero (secondo la proprietà di mucchio)
- preso un vaso, quelli con numero più piccolo stanno a sinistra, mentre quelli con un numero più grande stanno a destra di questo (secondo le proprità degli alberi)
Grazie a queste proprietà, possiamo dividere un mucchialbero in due e unirne due mucchialberi in uno in O(\log(N)) e di conseguenza, utilizzando propriamente queste operazioni, fare velocemente quello che ci viene chiesto.
Mattia non ha tempo da perdere è non si accontenta della velocità del mucchialbero: creare un mucchialbero richiede troppo tempo se viene aggiunto un vaso alla volta. Per questo dobbiamo impegnarci e costruire la struttura in tempo lineare. Bisogna stare attenti che la grandezza aleatoria assegnata a ciascun vaso rispetti le proprietà del mucchio: facciamo questo attravero la funzione ammucchia.
A seguito l’implementazione:
Codice
#include "olita.h"
struttura nodo {
intero valore;
intero_molto_lungo priorita;
intero dimensione_sottoalbero;
nodo punta_a sinistrorso, punta_a destrorso;
nodo () {}
};
nodo magazzino[10000069];
intero indice_allocazione diventa 0;
nodo punta_a alloca_nodo () {
restituisci magazzino+(indice_allocazione aumenta_di_uno);
}
nodo punta_a alloca_nodo (intero valore) {
nodo punta_a nuovo_nodo diventa magazzino+
(indice_allocazione aumenta_di_uno);
nuovo_nodo->valore diventa valore;
nuovo_nodo->priorita diventa numero_casuale;
nuovo_nodo->dimensione_sottoalbero diventa 1;
nuovo_nodo->destrorso diventa NULLO;
nuovo_nodo->sinistrorso diventa NULLO;
restituisci nuovo_nodo;
}
struttura mucchialbero {
nodo punta_a radice_vera diventa NULLO;
intero dimensione_sottoalbero (nodo punta_a nodo_a_caso) {
se (non nodo_a_caso) restituisci 0;
restituisci nodo_a_caso->dimensione_sottoalbero;
}
vuoto aggiorna_nodo (nodo punta_a nodo_a_caso) {
se (non nodo_a_caso) restituisci;
nodo_a_caso->dimensione_sottoalbero diventa 1+
dimensione_sottoalbero(nodo_a_caso->sinistrorso)+
dimensione_sottoalbero(nodo_a_caso->destrorso);
}
vuoto dividi_mucchialbero (
nodo punta_a radice,
nodo punta_a riferito_a sinistro,
nodo punta_a riferito_a destro,
intero cappa,
intero saltati diventa 0 ) {
se (non radice) {
destro diventa sinistro diventa NULLO;
restituisci;
}
intero indice diventa saltati+
dimensione_sottoalbero(radice->sinistrorso);
se (indice minore_o_uguale_di cappa) {
sinistro diventa radice;
dividi_mucchialbero(
sinistro->destrorso,
sinistro->destrorso,
destro,cappa,indice+1 );
} altrimenti {
destro diventa radice;
dividi_mucchialbero(
destro->sinistrorso,
sinistro,destro->sinistrorso,
cappa,saltati );
}
aggiorna_nodo(sinistro);
aggiorna_nodo(destro);
}
void unifica_mucchialberi (
nodo punta_a riferito_a radice,
nodo punta_a sinistro,
nodo punta_a destro ) {
se (non sinistro) {
restituisci vuoto ( radice diventa destro );
}
se (non destro) {
restituisci vuoto ( radice diventa sinistro );
}
se (sinistro->priorita minore_di destro->priorita) {
radice diventa sinistro;
unifica_mucchialberi (
radice->destrorso,
radice->destrorso,destro);
} altrimenti {
radice diventa destro;
unifica_mucchialberi (
radice->sinistrorso,
sinistro,radice->sinistrorso);
}
aggiorna_nodo (radice);
}
intero ennesimo_elemento (
nodo punta_a radice,
intero enne,
intero saltati diventa 0) {
intero indice diventa saltati+
dimensione_sottoalbero(radice->sinistrorso);
se (indice uguale_a enne) {
restituisci radice->valore;
}
se (indice minore_di enne) {
restituisci ennesimo_elemento (
radice->destrorso,
enne, indice+1);
} altrimenti {
restituisci ennesimo_elemento (
radice->sinistrorso,
enne, saltati);
}
}
intero ennesimo_elemento (intero enne) {
restituisci ennesimo_elemento (radice_vera,enne);
}
vuoto sposta (intero da,intero a) {
nodo punta_a sinistro,punta_a destro,punta_a elemento;
dividi_mucchialbero (
radice_vera,sinistro,destro,da
);
dividi_mucchialbero (
sinistro,sinistro,elemento,da-1
);
unifica_mucchialberi (
radice_vera,sinistro,destro
);
dividi_mucchialbero (
radice_vera,sinistro,destro,a-1
);
unifica_mucchialberi (
radice_vera,sinistro,elemento
);
unifica_mucchialberi (
radice_vera,radice_vera,destro
);
}
vuoto ammucchia (nodo punta_a radice) {
nodo punta_a massimo diventa radice;
se (
radice->sinistrorso e
radice->sinistrorso->priorita
minore_di radice->priorita
) {
massimo diventa radice->sinistrorso;
}
se (
radice->destrorso e
radice->destrorso->priorita
minore_di massimo->priorita
) {
massimo diventa radice->destrorso;
}
se (massimo uguale_a radice) restituisci;
scambia(radice->priorita,massimo->priorita);
ammucchia (massimo);
}
vuoto costruisci_linearmente (
nodo punta_a riferito_a radice,
intero sinistra,intero destra ) {
se (destra-sinistra minore_di 1) restituisci;
intero meta diventa (sinistra + destra) / 2;
radice diventa alloca_nodo(meta);
costruisci_linearmente (
radice->sinistrorso,
sinistra,meta
);
costruisci_linearmente (
radice->destrorso,
meta+1,destra
);
aggiorna_nodo (radice);
ammucchia (radice);
}
mucchialbero (intero dimensione) {
costruisci_linearmente(radice_vera,0,dimensione);
}
};
intero principale () {
scrivi.annoda(0);
leggi.annoda(0);
velocizza_input;
leggi_documento leggi ("input.txt");
scrivi_documento scrivi ("output.txt");
intero dimensione,richieste;
leggi in dimensione;
leggi in richieste;
mucchialbero dante (dimensione);
finche (richieste diminuisci_di_uno) {
carattere tipo;
leggi in tipo;
se (tipo uguale_a 'c') {
intero posizione;
leggi in posizione;
intero valore;
valore diventa dante.ennesimo_elemento(posizione);
scrivi questo valore e_questo spazio;
} altrimenti {
intero da,a;
leggi in da;
leggi in a;
dante.sposta(da,a);
}
}
scrivi questo finelinea;
restituisci 0;
}
(giuro che con olita.h, oltre a complilare, questo codice prende AC)
→ grazie a @TheScrasse per aver trovato il bug alle 02:20 del mattino
In caso ci fossero dubbi non esitate a fare domande.
