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.
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).
#include <bits/stdc++.h>
using namespace std;
ifstream cin("vraji.in");
ofstream cout("vraji.out");
int n , v , c , cer , cnt , cate , maxi;
char vmax[51];
int put(int x , int y)
{
int p = 1;
for(int i = 1 ; i <= y ; i++)
p *= x;
return p;
}
int vocala(char a)
{
return a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u' || a == 'q' || a == 'w' || a == 'y';
}
int consoana(char a)
{
if(a >= 'a' && a <= 'z' && !vocala(a)) return 1;
else return 0;
}
int calcul(char s[])
{
int i = 0;
int catevoc = 0 , catecons = 0 , f[30] = {0} , suma = 0 , dist = 0;
while(s[i] != '\0')
{
if(vocala(s[i])) catevoc++;
if(consoana(s[i])) catecons++;
f[s[i] - 'a']++;
i++;
}
for(int j = 0 ; j <= 25 ; j++)
{
if(f[j]) dist++;
}
//cout << dist <<'\n';
suma = (catevoc * v + catecons * c) / dist + 1;
i = 0;
int l = 0;
while(s[i] != '\0')
{
if(s[i] == s[i+1])
{
l = 1;
int j = i;
while(s[i] == s[j])
{
j++ , l++;
}
if(l > 1 && vocala(s[i])) suma += put(v , l - 1);
else if(l > 1 && consoana(s[i])) suma += put(c , l - 1);
i = j - 1;
}
i++;
//cout << s[i] << " ";
}
return suma;
}
int main()
{
char s[51];
cin >> cer;
cin >> n >> v >> c;
for(int i = 1 ; i <= n ; i++)
{
cin >> s;
int j = 0 , ok = 0;
while(s[j] != '\0')
{
if(s[j] == s[j-1]) ok = 1;
j++;
}
if(ok == 1) cnt++;
if(calcul(s) > maxi)
{
maxi = calcul(s);
cate = 1;
strcpy(vmax , s);
}
else if(calcul(s) == maxi)
cate++;
}
if(cer == 1) cout << cnt;
else
{
cout << cate << " " << vmax;
}
}
