[URI Online Judge] – 1519 – Abbreviations

Blogs are bery popular nowadays, and there are tools that allows you to maintain your blog for free. Rafael then decided to create a blog, where he is going to post all his daily experiences of his life.

For these free tools, there are characters limits that you can write each day, and Rafael is worried that this limitation will prevent him of telling his best experiences. He decided then to use an word abbreviation system in his posts.

The word abbreviation system works as follows: for each letter, it is possible to choose one word that has such initial letter and that appears in the post. Once the word is chosen, every time it appears in the post, it will be replaced by its initial letter and a point, then decreasing the number of characters printed at the screen.

For example, in the phrase: “today i visited my parents”, we can choose the word “visited” to represent letter ‘v’, and the phrase will be like this: “today I v. my parents”, saving five letters. One word can appear more than once in the text, and will be abbreviated every time. Notice that, if after an abbreviation the number of characters does not decrease, then it should not be abbreviated, as with the word “my” above.

Rafael needs his post to have the less number of characters as possible, and because of that he asked your help. For each letter choose a word, in a way that after the abbrevations are applied, the post will have as less characters as possible.


There will be several test cases. Each test case is composed of one line, containing one phrase up to 10⁴ characters. The phrase is composed of words and white spaces, and each word is composed of lower case letters (‘a’-‘z’), and has between 1 and 30 characters each.

The last test case is indicated when the given line has only one “.”, which should not be processed.


For each test case, print one line containig the phrase with the abbreaviations chosen and applied.

Following, print one integer N, indicating the number of letters that was chosen words to abbreviate. In the next N lines, print the following pattern “C. = P”, where C is the initial letter and P is the chosen word for such letter. The lines should be printed in ascending order of the initial letter.

Sample Input Sample Output
hoje eu visitei meus pais
tive que lavar meu cachorro pois ele estava fedendo
h. eu v. m. p.
h. = hoje
m. = meus
p. = pais
v. = visitei
t. q. l. m. c. p. ele e. f.
c. = cachorro
e. = estava
f. = fedendo
l. = lavar
m. = meu
p. = pois
q. = que
t. = tive

My solution:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <string>
#include <vector>
#include <map>
using namespace std;

struct Word {
string w;
int c;

Word(string w, int c) : w(w), c(c) {}

inline bool operator <(const Word& o) const {
return c > o.c;

vector<string> W;
vector<Word> WW;
map<string, char> M;
map<char, string> RM;
map<string, int> C;

int main() {
string s;
while(getline(cin, s), s!=".") {

stringstream sin(s);
string word;
while(sin >> word) {
if (C.find(word) == C.end()) C[word] = 0;
C[word] += word.size()-2;


for(map<string, int>::iterator it = C.begin(); it != C.end(); it++) {
WW.push_back(Word(it->first, it->second));

sort(WW.begin(), WW.end());

for(int i=0; i<WW.size(); i++) {
char letter = WW[i].w[0];
if (WW[i].c <= 0 || RM.find(letter) != RM.end()) continue;

M[WW[i].w] = letter;
RM[letter] = WW[i].w;

for(int i=0; i<W.size(); i++) {
if (i>0) cout << " ";

if (M.find(W[i]) != M.end()) {
cout << M[W[i]] << ".";
} else {
cout << W[i];
cout << endl;

cout << M.size() << endl;
for(map<string, char>::iterator it = M.begin(); it != M.end(); it++) {
cout << it->second << ". = " << it->first << endl;


One thought on “[URI Online Judge] – 1519 – Abbreviations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s