Mai sunt câteva săptămâni și vine Crăciunul. Ajuns într-un magazin de jucării, Robert îl roagă pe tatăl său să-i cumpere cea mai frumoasă mașină cu telecomandă. Tatăl său îi spune că nu a fost cuminte în timpul anului și nu merită această jucărie, însă după dispute intense acesta hotaraste să-i mai acorde o sansă, doar dacă va rezolva următoarea problema:
Având un string S, putem să obținem un palindrom din acest șir ștergând un singur caracter?
Robert nu se prea descurca la algoritmică așa că vă roagă foarte mult să-i rezolvați problema pentru a se putea juca cu mașina cu telecomandă. În schimbul acestei mașini el vă va recompensa cu 100 puncte.
Cerința
Find dat un string S, se poate obține un palindrom din șirul inițial ștergând doar un singur caracter ?
Date de intrare
Fişierul de intrare constructpalindrom.in conţine pe prima linie o valoare T reprezentând numărul de teste. Pe următoarele T linii vom avea cate un string reprezentând întrebarea adresata lui Robert de către tatăl sau.
Date de ieșire
Fişierul de ieşire constructpalindrom.out va conține T linii cu răspunsul YES daca se poate obține un palindrom ștergând un singur caracter și NO dacă nu se poate obține.
Restricții și precizări
1 <= T <= 100- Dimensiunea stringului
<= 100000 - Pentru 10% din punctaj dimensiunea stringului
<= 1000 - String-ul conține caractere de la
alaz. - Dimensiunea string-ului după ștergerea unui caracter va fi mai mică decât a fost înainte.
Exemplu
constructpalindrom.in
4 aaa abc abdbca abba
constructpalindrom.out
YES NO YES YES
Explicație
Pentru primul exemplu (aaa): Putem șterge orice a, string-ul rezultat este aa, care este palindrom.
Pentru al doilea exemplu (abc): Nu este posibil să eliminăm exact un caracter și să obtinem un palindrom.
Pentru al treilea exemplu (abdbca): ștergem caracterul c, string-ul rezultat este abdba care este palindrom.
Pentru exemplul al patrulea (abba): Ștergem b, obținem aba care este palindrom.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema ConstructPalindrom :
//Implementare solutie optima (cu string-uri)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ofstream out("constructpalindrom.out");
bool isPalindrom(string sir, int left, int right)
{
for(int i = left, j = right; i < j; ++i,--j)
if( sir[i] != sir[j])
return false;
return true;
}
int T;
int main()
{
ifstream in("constructpalindrom.in");
in >> T;
for(; T; --T)
{
string sir;
in >> sir;
int dimension = sir.length() - 1;
if(isPalindrom(sir,0,dimension))
out << "YES" << '\n';
else
{
int min_poz_i = -1;
int min_poz_j = -1;
for(int i = 0, j = dimension; i < j; i++,j--)
if(sir[i] != sir[j])
{
min_poz_i = i;
min_poz_j = j;
break;
}
string copieSir="";
copieSir += sir;
// cout << min_poz_i << " " << min_poz_j << " ";
sir.erase(min_poz_i,1);
// cout <<"Simplu " << sir << " ";
if(isPalindrom(sir,0,sir.length()-1))
{
out << "YES" << '\n';
continue;
}
copieSir.erase(min_poz_j,1);
// cout << "Compus " << copieSir << " ";
if(isPalindrom(copieSir,0,copieSir.length()-1))
{
out << "YES" << '\n';
continue;
}
out << "NO" << '\n';
}
}
return 0;
}Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1413 ConstructPalindrom
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1413 ConstructPalindrom de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!