Ciao a tutti, ho bisogno di aiuto per risolvere il problema Foglietto illustrativo.
Pensavo di iterare la stringa di pieghe S più volte, individuando ogni volta la piega migliore da effettuare (cont_char_migliore) e poi eliminando i caratteri che vengono sovrapposti da S assieme alla piega che diventa il nuovo lato fisico.
I subtask 1 e 2 sono tutti corretti, ma già dal terzo compaiono due errori, mentre il settimo fallisce interamente perché impiega troppo tempo, a differenza dell’ottavo. Capisco che il programma sia lento, ma non capisco perché ci sono risultati sbagliati. Qual è il problema che non ho considerato?
Ecco il mio codice:
#include <iostream>
#include <string>
using namespace std;
/*
string rimuoviSinistra(int num, string s, int N){
string nuova_s="";
for(int i=num+1;i<N;++i){//da sinistra deve togliere num caratteri pi� la piegha su cui verr� fatto ruotare parte del foglietto
nuova_s+=s[i];
}
return nuova_s;
}
string rimuoviDestra(int num, string s, int N){
string nuova_s="";
for(int i=0;i<N-num-1;++i){//da destra deve togliere num caratteri pi� la piegha su cui verr� fatto ruotare parte del foglietto
nuova_s+=s[i];
}
return nuova_s;
}
*/
int piega(int N, string S) {
int cont=0;//contatore di pieghe
while(S.size()>1){
//cout<<endl<<"stringa: " << S << endl;
//cout<<endl<<"pieghe: " << cont << endl;
int cont_char_migliore=0;
bool sinistra=true;
N=S.size();
for(int i=1;i<N-1;++i){
if(S[i-1]==S[i+1])// se sono uguali, certamente non potr� piegare
continue;
int cont_char=0;
int j,k;
if(i<N/2){
//prima met� del foglietto
int fine=2*i;//indice finale per k
for(j=i-1,k=i+1; j>=0 && k<=fine; --j,++k){//doppio ciclo for: j e k scorrono parte di S con i come centro
//se le due sottostringhe saranno effettivamente compatibili, devo salvarmi il numero di caratteri della sottostringa a sinistra
if(S[j] != S[k])
++cont_char;
else
break;
}
if(k < fine+1)//se sono uscito dal ciclo non perch� ho controllato tutti i caratteri
continue;
if(cont_char_migliore>=cont_char)//se non serve sovrascrivere
continue;
cont_char_migliore=cont_char;
sinistra=true;
}
else{
//seconda met� del foglietto
int inizio=2*i-N+1;//indice di partenza per j: N-2*(N-i-1)-1 = 2*i-N+1
for(j=i-1,k=i+1; j>=inizio && k<N && cont_char_migliore < N-1-i; --j,++k){//doppio ciclo for: j e k scorrono parte di S con i come centro. Se i caratteri rimanenti sono minori della soluzione migliore, le eventuali soluzioni saranno peggiori
//se le due sottostringhe saranno effettivamente compatibili, devo salvarmi il numero di caratteri della sottostringa a sinistra
if(S[j] != S[k])
++cont_char;
else
break;
}
if(k < N)//se sono uscito dal ciclo non perch� ho controllato tutti i caratteri
continue;
if(cont_char_migliore>=cont_char){//se non serve sovrascrivere
continue;
}
cont_char_migliore=cont_char;
sinistra=false;
}
}
if(sinistra){
//S=rimuoviSinistra(cont_char_migliore,S,N);
S.erase(S.begin(),S.begin()+cont_char_migliore+1);
}
else{
//S=rimuoviDestra(cont_char_migliore,S,N);
S.erase(N-cont_char_migliore-1);
}
++cont;
}
++cont;//� rimasta una sola piegha su cui piegare
return cont;
}
/*
int main()
{
cout << "Inserire numero di pieghe: " << endl;
int N;
cin >> N;
cout << "Inserire stringa di 0 e 1: ";
string s;
cin >> s;
cout << endl << piega(N,s) << endl;
return 0;
}
*/
Grazie mille in anticipo!