Weighted Letter Value
National Olympiad — Municipal round (2009 season)
Submission name: word.cpp
Problem summary
Give a lowercase word the value Σ(position from 1 in alphabet) × 2^index, with word indices starting at zero. Print whether that value is even, and print the value only when it is even.
Input
One word of lowercase Latin letters.
Output
yes followed by its value if even; otherwise no.
Constraints
1–40 lowercase Latin letters.
Worked example
Input and output for the worked example discussed below.
Input
dba
Output
yes 12
Solution analysis
- Convert a letter into its alphabet rank using letter−'a'+1. The first letter has weight 1, the second 2, the third 4, and so on. Keep a weight variable and double it after processing each letter.
- Add the weighted ranks in long long. Even though each rank is at most 26, position weights make a 32-bit sum unsafe. The maximum possible value is 26(2^40−1), safely below the signed 64-bit limit.
- For dba, ranks are 4,2,1 and weights are 1,2,4, giving 4+4+4=12. Since 12 is even, output yes 12. A one-letter a has value 1, so output only no. Parity is decided by the first rank, but the full sum is still required in the even case.
Why it works
After each processed prefix, weight equals the next power of two and value is exactly the requested sum for that prefix. Adding the next weighted rank preserves this invariant. Testing the final sum modulo two therefore gives the required result.
Watch out. Word indices start at zero, while alphabet ranks start at one. Avoid floating-point pow and int accumulation. Do not print the numeric value in the no case.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
string word;
cin>>word;
long long value=0;
long long weight=1;
for(char letter:word){
// Each next letter has twice the positional weight.
value+=(letter-'a'+1)*weight;
weight*=2;
}
if(value%2==0){
cout<<"yes "<<value<<'\n';
}
else{
cout<<"no\n";
}
}