Smallest Word Code
National Olympiad — National round (2012 season)
Submission name: kod.cpp
Problem summary
A word’s code is the sum of its letters’ alphabet positions, with a=1 and z=26. Find the word with the smallest code; retain the first on a tie.
Input
n, followed by n lowercase Latin words, one per line.
Output
The selected word and its code separated by a space.
Constraints
2 < n < 50; each word has at most 20 letters.
Worked example
An independently prepared example for this explanation.
Input
4 oko banan liniq more
Output
banan 32
Solution analysis
- Compute a word’s code by adding letter−a+1 for each letter. Reset this sum for every new word.
- Keep the smallest code and its word. Replace only for a strict improvement to preserve the earliest word on a tie.
- banan has code 2+1+14+1+14=32, smaller than the codes of oko, liniq and more, so output banan 32.
Why it works
Each word’s computed sum is its definition of code. The running minimum stores the earliest word attaining the smallest code among all processed words, and this invariant gives the required final choice.
Watch out. Alphabet positions begin at 1, not 0. Do not resolve equal codes alphabetically.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
int bestCode = 1000000;
string bestWord;
for (int i = 0; i < n; i++) {
string word;
cin >> word;
int code = 0;
for (char letter : word) {
code += letter - 'a' + 1;
}
// Strict improvement preserves the first word on equal codes.
if (code < bestCode) {
bestCode = code;
bestWord = word;
}
}
cout << bestWord << ' ' << bestCode << '\n';
}