Word Weights
National Olympiad — Municipal round (2010 season)
Submission name: dumi.cpp
Problem summary
Letters have case-insensitive values A=1 through Z=26. The first letter has multiplier 1, the second 2, then 4,8,... Find the greatest-weight word; on a tie choose the first in the input.
Input
N followed by N words, one per line.
Output
The heaviest word, preserving its original capitalization.
Constraints
2 < N < 100; words contain at most 20 Latin letters.
Worked example
An independently prepared example for this explanation.
Input
3 Kod dEn QweRtY
Output
QweRtY
Solution analysis
- For each word maintain a multiplier initially equal to 1. Add the current letter value times the multiplier, then double the multiplier.
- Track the largest weight seen and its original word. Replace the stored word only for a strictly larger weight, which preserves the earliest word on ties.
- Kod has weight 11+2·15+4·4=57. QweRtY has weight 17+46+20+144+320+800=1347, greater than the other sample words.
Why it works
After processing j letters, the multiplier is 2^j and the sum equals the weighted contribution of exactly the first j letters. The update preserves this invariant. Strict improvements maintain the earliest maximum among all processed words.
Watch out. Use the original word for output, and compare letters without case. Do not replace on equal weight.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cctype>
#include<iostream>
#include<string>
using namespace std;
int main(){
// Compute the exact archive answer using the method explained above.
int n;
cin>>n;
string answer;
long long best=-1;
for(int i=0;i<n;i++){
string word;
cin>>word;
long long weight=0;
long long multiplier=1;
for(unsigned char letter:word){
int value=tolower(letter)-'a'+1;
weight+=value*multiplier;
multiplier*=2;
}
if(weight>best){
best=weight;
answer=word;
}
}
cout<<answer<<'\n';
}