Longest Alphabetically Ordered Odd Word
National Olympiad — National round (2011 season)
Submission name: word.cpp
Problem summary
Replace each star with a space and remove other punctuation. Among the resulting letter words, find the first longest word of odd length whose letters are nondecreasing alphabetically, ignoring case.
Input
One string containing Latin letters and the listed punctuation symbols.
Output
The 1-based word number and length; print 0 0 if no word qualifies.
Constraints
1…255 input characters; the string does not begin or end with a star.
Worked example
Input and output for the worked example discussed below.
Input
L*bbC*abda***CCDb*%-dA**bdMvV
Output
6 5
Solution analysis
- Stars delimit words, while removed punctuation does not split a word. Scan once, appending only letters, and finalize the accumulated word at a star or at end of input. Consecutive stars create no additional words.
- A word qualifies when its length is odd and every lowercase-normalized letter is at least its predecessor. Count every nonempty word, including rejected ones. Replace the best only for a strictly greater length to keep the leftmost tie.
- The sample produces L, bbC, abda, CCDb, dA, bdMvV. The sixth word has normalized letters b,d,m,v,v and length 5, so the result is 6 5; the shorter qualifying words cannot beat it.
Why it works
The scan produces exactly the words after the specified transformation. The adjacent comparisons are equivalent to nondecreasing alphabetical order, and parity checks the other qualification. A strict best-length update retains the first longest qualifying word.
Watch out. Do not compare raw ASCII uppercase versus lowercase. Punctuation is removed, not turned into extra separators. Empty runs between stars are not words.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cctype>
#include<iostream>
#include<string>
using namespace std;
int main(){
string text;
getline(cin,text);
text+='*';
string word;
int number=0;
int bestNumber=0;
int bestLength=0;
for(unsigned char character:text){
if(isalpha(character)){
word+=char(tolower(character));
}
else if(character=='*'&&!word.empty()){
number++;
bool ordered=true;
for(size_t index=1;index<word.size();index++){
if(word[index]<word[index-1]){
ordered=false;
}
}
// Strict improvement preserves the first word in a length tie.
if(ordered&&word.size()%2==1&&int(word.size())>bestLength){
bestLength=word.size();
bestNumber=number;
}
word.clear();
}
}
cout<<bestNumber<<' '<<bestLength<<'\n';
}