Cerința
Emil are un mouse special, cu două rotițe de scroll. Pe fiecare rotiță de scroll el poate fixa câte o bandă circulară de cauciuc pe care sunt printate în format 3D caracterele utilizate frecvent pentru editare.
Apăsând vertical rotița de scroll în punctul ei cel mai înalt, caracterul aflat în punctul de apăsare va fi generat de către mouse. Astfel se pot edita diferite texte doar cu ajutorul mouse-ului. Ordinea în care sunt printate caracterele influențează viteza de tastare și energia consumată în procesul de editare a textelor. Efortul de trecere de la un caracter la următorul sau la anteriorul consumă o cantitate de energie egală cu o unitate. Apăsarea pe rotiță nu consumă energie. Emil vrea să afle care este cantitatea minimă de energie pe care trebuie să o consume pentru construirea unui text dat.
Date de intrare
Fișierul de intrare birot.in conține pe prima linie șirul de caractere printat pe banda de cauciuc de pe prima rotiță de scroll. Pe a doua linie se află șirul de caractere printat pe banda de cauciuc de pe a doua rotiță de scroll, iar pe a treia linie se afla textul care trebuie construit cu ajutorul mouse-ului.
Date de ieșire
Fișierul de ieșire birot.out va conține pe prima linie numărul reprezentând cantitatea minimă de energie ce trebuie consumată pentru construirea textului dat.
Restricții și precizări
- lungimile primelor două șiruri sunt egale și
≤ 90; - în fiecare din primele două șiruri caracterele sunt distincte;
- primele două șiruri sunt formate din aceleași caractere, eventual așezate în altă ordine;
- lungimea șirului care trebuie construit este cel mult egală cu 10 000;
- orice caracter din șirul care trebuie construit se găsește în fiecare din primele două șiruri;
- caracterele care pot apărea în textul dat și pe benzile de cauciuc sunt caractere printabile, inclusiv caracterul spaţiu;
- inițial fiecare rotiță este așezată astfel încât primul caracter din șirul corespunzător ei să se afle deasupra, în poziția cea mai înaltă;
- benzile de cauciuc sunt astfel așezate pe rotițe încât împingând rotițele înspre înainte caracterele sunt parcurse, circular, în ordinea dată în șirurile citite.
Exemplu
birot.in
abo-r ao-br bar-ba-ra
birot.out
7
Explicație
| comandă | rotița 1 | rotița 2 | text creat | energie |
| la început | abo-r | ao-br | 0 | |
| înapoi rotița1 | bo-ra | ao-br | 1 | |
| apăs rotița1 | bo-ra | ao-br | b | |
| apăs rotița2 | bo-ra | ao-br | ba | |
| înainte rotița2 | bo-ra | rao-b | ba | 2 |
| apăs rotița2 | bo-ra | rao-b | bar | |
| înainte rotița2 | bo-ra | brao- | bar | 3 |
| înainte rotița2 | bo-ra | -brao | bar | 4 |
| apăs rotița2 | bo-ra | -brao | bar- | |
| apăs rotița1 | bo-ra | -brao | bar-b | |
| înainte rotița1 | abo_r | -brao | bar-b | 5 |
| apăs rotița1 | abo_r | -brao | bar-ba | |
| apăs rotița2 | abo_r | -brao | bar-ba- | |
| înainte rotița1 | rabo- | -brao | bar-ba- | 6 |
| apăs rotița1 | rabo- | -brao | bar-ba-r | |
| înapoi rotița1 | abo-r | -brao | bar-ba-r | 7 |
| apăs rotița1 | abo-r | -brao | bar-ba-ra |
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 Birot:
/* prof. Pit-Rada Ionel-Vasile
* O(n*m)
*/
#include<fstream>
using namespace std;
ifstream fin("birot.in");
ofstream fout("birot.out");
int best1[2][130],best2[2][130];
char s1[102], s2[102], t[100003];
int q1[130], q2[130];
int p1,p2,infinit=100000000;
int m, n;
int e(int i, int j){
int d1,d2;
if(i<j){
d1=j-i;
d2=m-d1;
}
else{
d1=i-j;
d2=m-d1;
}
return (d1<d2)?d1:d2;
}
int main(){
int i,p1,p2,x1,x2,y1,y2,valmin,k1,k2,k,r1,r2,v;
fin.get(s1+1,101,'\n');
fin.get();
fin.get(s2+1,101,'\n');
fin.get();
fin.get(t+1,100001,'\n');
fin.get();
m=1;while(s1[m]!=0){
q1[(int)s1[m]]=m;
q2[(int)s2[m]]=m;
m++;
}
m--;
n=1;while(t[n]!=0)n++;
n--;
//best1[k][i]=costul optim de a obtine t[k] cu rotita1 si cealalta rotita la pozitia i
//best2[k][i]=costul optim de a obtine t[k] cu rotita2 si cealalta rotita la pozitia i
for(i=1;i<=m;i++){
best1[1][i]=infinit;
best2[1][i]=infinit;
}
p1=1;
p2=1;
r1=q1[(int)t[1]];
r2=q2[(int)t[1]];
x1=e(p1,r1);
x2=e(p2,r2);
best1[1][p2]=x1;
best2[1][p1]=x2;
for(k=2;k<=n;k++){
//initializez bn cu zero
k2=k%2;
k1=1-k2;
for(i=1;i<=m;i++){
best1[k2][i]=infinit;
best2[k2][i]=infinit;
}
r1=q1[(int)t[k]];
r2=q2[(int)t[k]];
p1=q1[(int)t[k-1]];
p2=q2[(int)t[k-1]];
x1=e(p1,r1);
y2=e(p2,r2);
for(i=1;i<=m;i++){
v=best1[k1][i];
if(v<infinit){
//sunt cu rotita2 la pozitia i si cu rotita1 la pozitia p1
x2=e(i,r2);
if(v+x1<best1[k2][i]){
best1[k2][i]=v+x1;
}
if(v+x2<best2[k2][p1]){
best2[k2][p1]=v+x2;
}
}
v=best2[k1][i];
if(v<infinit){
//sunt cu rotita1 la pozitia i si cu rotita2 la pozitia p2
y1=e(i,r1);
if(v+y1<best1[k2][p2]){
best1[k2][p2]=v+y1;
}
if(v+y2<best2[k2][i]){
best2[k2][i]=v+y2;
}
}
}
}
k2=n%2;
valmin=infinit;
for(i=1;i<=m;i++){
if(best1[k2][i]<valmin){
valmin=best1[k2][i];
}
if(best2[k2][i]<valmin){
valmin=best2[k2][i];
}
}
fout<<valmin<<"\n";
fout.close();
fin.close();
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 #1245 Birot
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1245 Birot 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!