Problem statement
Contest source
Author, Editorialist : Dhananjay Raghuwanshi
Tester : Miten Shah
DIFFICULTY:
Simple
PREREQUISITES:
Sorting
PROBLEM:
Given a string S of lowercase english alphabets, we need to find maximum value of the string.
The value of a string S, is defined as ∑ i * (position of i_{th} letter of S in alphabets), for i = 1,2 … length of S. We can transform S in any of the possible rearrangements of this string S.
EXPLANATION:
- For some index i of the string S it’s contribution in the value of the array is proportional to i * (position of i_{th} letter of S in alphabets) . So to maximise the value of the array we need to maximise the above multiplication. The above product will be maximum if for a lager i, the character at i_{th} position in S comes later in alphabets. So from the above explanation, the rearrangement of string S that will have maximum is the one sorted in non decreasing order.
SOLUTION :
c++ Solution
#include <bits/stdc++.h>
using namespace std;
signed main()
{
int t;
cin >> t;
while (t--)
{
int ans = 0, n;
string s;
cin >> s;
n = s.size();
sort(s.begin(), s.end());
for (int i = 0; i < n; i++)
ans += (i + 1) * (s[i] - 'a' + 1);
cout << ans << endl;
}
}
C++ Tester's Solution
// created by mtnshh
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define err() cout<<"--------------------------"<<endl;
#define errA(A) for(auto i:A) cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define ft first
#define sd second
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
#define endl "\n"
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cerr << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int max_q = 1e2;
const ll N = 100005;
const ll INF = 1e12;
void solve(){
string s = readStringLn(1, max_q);
sort(all(s));
ll ans = 0, n = s.length();
rep(i,0,n){
ans += (s[i] - 'a' + 1) * (i + 1);
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q = readIntLn(1, max_q);
while(q--){
solve();
}
assert(getchar()==-1);
}