[Problem Description]
Problem
On the game show The Last Word, the host begins a round by showing the contestant a string S of uppercase English letters. The contestant has a whiteboard which is initially blank. The host will then present the contestant with the letters of S, one by one, in the order in which they appear in S. When the host presents the first letter, the contestant writes it on the whiteboard; this counts as the first word in the game (even though it is only one letter long). After that, each time the host presents a letter, the contestant must write it at the beginning or the end of the word on the whiteboard before the host moves on to the next letter (or to the end of the game, if there are no more letters).
For example, for S = CAB
, after writing the word C
on the whiteboard, the contestant could make one of the following four sets of choices:
- put the
A
beforeC
to formAC
, then put theB
beforeAC
to formBAC
- put the
A
beforeC
to formAC
, then put theB
afterAC
to formACB
- put the
A
afterC
to formCA
, then put theB
beforeCA
to formBCA
- put the
A
afterC
to formCA
, then put theB
afterCA
to formCAB
The word is called the last word when the contestant finishes writing all of the letters from S, under the given rules. The contestant wins the game if their last word is the last of an alphabetically sorted list of all of the possible last words that could have been produced. For the example above, the winning last word is CAB
(which happens to be the same as the original word). For a game with S = JAM
, the winning last word is MJA
.
You are the next contestant on this show, and the host has just showed you the string S. What's the winning last word that you should produce?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S.
Output
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is the winning last word, as described in the statement.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ length of S ≤ 15.
Large dataset
1 ≤ length of S ≤ 1000.
Sample
Input |
Output |
7 |
Case #1: CAB |
今天是google的codejam contest的roundB,之前练习一下,就做了这道题,很简单,但是真正比赛的题目还是没有做出来。真正的算法大神是真的牛啊。
这道题就比较简单了。有点像二叉树嘛,由一个字符,每次插入到前面或后面就会生成两个字符串,由于最后需要字典序最大的,因此每次生成这两个字符串,我就保存最大的。
void LastWord(ifstream& fin) { int num;
fin >> num;
ofstream fout("output.txt");
for(int j=;j<num;j++){
string s1="";
string s2="";
string smax="";
string s;
fin >> s;
for (int i = ; i < s.length(); i++) {
s1 = smax + s[i];
s2 = s[i] + smax;
smax = s1 > s2 ? s1 : s2;
}
fout << "Case #" << j+ << ":" <<" "<<smax << endl;
}
return;
}