Harry se află într-un duel de vrăjitori și vrea să folosească cea mai puternică vrajă pe care și-o amintește în acest moment. Deoarece mai devreme a fost lovit de o vrajă a uitării, are nevoie de ajutorul vostru pentru a calcula rapid cea mai puternică vrajă dintr-un set de vrăji. Vrăjile sunt șiruri de caractere, litere mici ale alfabetului englez, fară spații între ele.
Exemple: stupefy, accio, expelliarmus, depulso, levicorpus, reductuu, coooptuus etc.
Puterea unei vrăji se calculează în funcție de numărul de vocale și de consoane pe care le are vraja, după formula: [(nrv*V+nrc*C)/nrd]+1, unde:
V– puterea unei vocale;C– puterea unei consoane;nrv– numărul de vocale din vrajă;nrc– numărul de consoane din vrajă;nrd– numărul de litere distincte din vrajă;[a]– reprezintă partea întreagă a numărului a.
Se vor considera vocale: a, e, i, o, u, q, w, y.
Se numeşte grup o secvenţă de cel puţin două litere identice. Un grup se numeşte maximal, dacă este delimitat de litere diferite de conţinutul său, respectiv de începutul sau sfârşitul vrăjii.
Spre exemplu: în vraja coooptuus, ooo și uu sunt grupuri maximale, însă oo nu este grup maximal.
Deoarece Harry este un vrăjitor special, acesta are abilitatea de a calcula puterea fiecărui grup maximal dintr-o vrajă, și apoi să o adune la puterea acesteia. Puterea unui grup se obține înmulțind puterea literei respective cu ea însăși de același număr de ori câte litere identice are grupul.
Exemple: pentru V=5 și C=2, stupefy are puterea [(3*5+4*2)/7)]+1=3+1=4;
accio are puterea [(3*5+2*2)/4]+1+2*2=4+1+4=9;
reductuu are puterea [(4*5+4*2)/6]+1+5*5=4+1+25=30.
După lovitura primită, Harry mai știe doar N vrăji.
Se numește vrajă specială o vrajă pe care Harry își poate folosi abilitatea specială.
Exemple: accio și reductuu sunt vrăji speciale, deoarece au fiecare cel puțin un grup maximal de două litere identice;
stupefy nu este o vrajă specială deoarece nu are are niciun grup de litere identice.
Cerința
Cunoscând N, V, C și vrăjile pe care le mai știe Harry, se cere:
a)numărul total de vrăji speciale;
b)prima vrajă de putere maximă pe care Harry şi-o aminteşte, și câte astfel de vrăji poate folosi eroul nostru.
Date de intrare
Fişierul de intrare vraji.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Următoarea linie conţine 3 numere întregi separate prin spațiu: N, V și C în această ordine. Pe următoarele N linii se vor găsi vrăjile pe care Harry le mai știe, fiecare vrajă pe câte o linie (în ordinea în care el și le aduce aminte).
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință.
În acest caz, în fişierul de ieşire vraji.out se va scrie un singur număr natural reprezentând numărul total de vrăji speciale.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință.
În acest caz, fişierul de ieşire vraji.out va conține numărul de vrăji de putere maximă urmat de prima vrajă de putere maximă pe care și-o mai amintește Harry, separate printr-un spațiu.
Restricții și precizări
-50 ≤ V, C ≤ 501 ≤ N ≤ 50 000- Lungimea unei vrăji ≤
50 - Se garantează că valoarea puterii unei vrăji pentru toate testele este ≤
2 147 483 647. - Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
Exemplul 1:
vraji.in
1 6 5 2 stupefy accio expelliarmus depulso levicorpus reductuu
vraji.out
3
Explicație
p = 1
Sunt 3 vrăji speciale: accio, expelliarmus, reductuu, deoarece acestea au grupuri de litere vecine identice.
Atenție! Pentru acest test se rezolvă doar cerința a).
Exemplul 2:
vraji.in
2 6 5 2 stupefy accio expelliarmus depulso levicorpus reductuu
vraji.out
1 reductuu
Explicație
p = 2
Atenție! Pentru acest test se rezolvă doar cerința b).
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 vraji:
#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>
using namespace std;
ifstream fin("vraji.in");//fisier de intrare
ofstream fout("vraji.out");//fisier de iesire
int p;//variabila pentru stabilirea cerintei
int N,V,C;// nr vraji; puterea unei vocale; puterea unei consoane
int nrVS;//numar vraji speciale
int pMax=-2000000000,nrMax;//puterea maxima, numarul de vraji de putere maxima
char spellMax[105];//vraja de putere maxima
int fl[30];//vector de frecvente al literelor
int main()
{
int i,j;//variabile contor
int pc;//puterea vrajii curente
int nrv,nrc,nrd;// numar vocale; numar consoane; numar litere diferite
int n,k;//lungimea vrajii curente; nr de litere vecine identice
int aux,auxp;//variabile auxiliara pentru calculul puterii
int vrajaspeciala;//1-vraja curenta e special sau 0 in caz contrar
char c;//variabila caracter
char spell[105];//vraja curenta
fin>>p;
fin>>N>>V>>C;
fin.get();
for(i=1;i<=N;i++){//parcurgere vraji
fin.get(spell,100,'\n');//citire vraja
fin.get();//citire newline
n=strlen(spell);//n<-lungimea stringului citit
//reinitializare variabile pentru calculul puterii vrajii
pc=1;
nrv=nrc=nrd=0;
k=1;
c=0;
vrajaspeciala=0;
for(j=0;j<n;j++){//parcugere caractere
if(c==spell[j]){//verificare daca este vraja speciala
k++;//ultimele k litere sunt identice
vrajaspeciala=1;
}
else{
if(k>1){//calculeaza puterea grupului de k litere vecine identice
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='q'||c=='w'||c=='y')//identifica daca litera este vocala sau consoana
auxp=V;
else
auxp=C;
aux=auxp;
while(k>1){//calculeaza auxp^k
aux*=auxp;
k--;
}//k=1 la iesire din bucla
pc+=aux;//aux=puterea grupului de k litere vecine identice
}
}
c=spell[j];//c<- caracterul curent
fl[c-'a']++;//aduna frecventa pentru a calcula mai tarziu nrd
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='q'||c=='w'||c=='y'){//verifica daca litera curenta este vocala sau consoana
nrv++;//daca este vocala incrementeaza nrv
}
else{
nrc++;//daca este consoana incrementeaza nrc
}
}
if(k>1){//verifica daca stringul se termina cu un grup de k litere identice
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='q'||c=='w'||c=='y')
auxp=V;
else
auxp=C;
aux=auxp;
while(k>1){
aux*=auxp;
k--;
}
pc+=aux;
}
for(j=0;j<26;j++){//calculeaza nrd si reintializeaza vectorul cu 0
if(fl[j]>0)//daca frecventa unei litere este pozitiva
nrd++;//atunci incrementeaza nrd
fl[j]=0;
}
pc+=(int)((nrv*V+nrc*C)/nrd);//calculeaza puterea vrajii curente
nrVS+=vrajaspeciala;//nrVS va fi incrementat daca vraja curenta este speciala
if(pc>pMax){//verifica daca puterea vrajii actuale este mai mare decat cea mai mare putere de pana acum
pMax=pc;//actualizeaza puterea maxima
nrMax=1;//numarul de vraji de putere maxima este 1 in acest moment
strcpy(spellMax,spell);//actualizeaza vraja de putere maxima
}
else if(pc==pMax){//daca s-a gasit o vraja de putere maxima
nrMax++;//atunci se incrementeaza nrMax
}
// k=(int)((nrv*V+nrc*C)/nrd);
// cout<<spell<<" "<<nrc<<" "<<nrv<<" "<<nrd<<" -> "<<k<<" "<<pc<<" "<<vrajaspeciala<<"\n";
// fout<<spell<<" "<<pc<<" "<<vrajaspeciala<<"\n";
}
fin.close();
if(p==1)
fout<<nrVS<<"\n";
else
fout<<nrMax<<" "<<spellMax<<"\n";
fout.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 #625 vraji
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #625 vraji 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!