885 - Telephone Directory Alphabetization

[brianfry713]

Try input:

Code: Select all

12345671000

[mathgirl]

Now I m getting WA. Can you tell me if ur AC code matches my I/O ?

Sample Input:

Code: Select all

1234567KAT shop
1234567K-B enterprises
1234567K W clop
1234567K Warehouse
123456759 steps
1234567fifty nine steps and alll
1234567K W street
1234567Do u know me?
1234567????
1234567Excuse me 1000
12345671000 words
12345671000 books
12345679 steps
123456710 steps
123456719 steps
123456725 steps
1234567511 steps
1234567511511 steps
1234567611511511 steps
1234567743521578 steps
1234567abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzSSSSSS
8936251KAT Shop
7362812Penny Saver, Inc.
7251887Kate's Company
8372974Fine Foods
9273664Five Star Vending
3523984K-B Enterprises
723621899 Cents Only Store
3523984Pennypinching Company
3523984Penny-Wise Corporation

Sample Output:

Code: Select all

????                                                   123 4567
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz   123 4567
Do u know me?                                          123 4567
Excuse me 1000                                         123 4567
59 steps                                               123 4567
fifty nine steps and alll                              123 4567
Fine Foods                                             837 2974
511 steps                                              123 4567
511511 steps                                           123 4567
Five Star Vending                                      927 3664
KAT shop                                               123 4567
KAT Shop                                               893 6251
K-B enterprises                                        123 4567
K-B Enterprises                                        352 3984
K W clop                                               123 4567
K W street                                             123 4567
K Warehouse                                            123 4567
Kate's Company                                         725 1887
9 steps                                                123 4567
19 steps                                               123 4567
99 Cents Only Store                                    723 6218
1000 books                                             123 4567
1000 words                                             123 4567
Penny Saver, Inc.                                      736 2812
Penny-Wise Corporation                                 352 3984
Pennypinching Company                                  352 3984
743521578 steps                                        123 4567
611511511 steps                                        123 4567
10 steps                                               123 4567
25 steps                                               123 4567

[mathgirl]

Can you also tell me what is the output for

1234567000
12345670001
12345670000

Code: Select all

#include<string>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

const char *ones[] = {"ZERO","ONE","TWO","THREE","FOUR","FIVE","SIX","SEVEN","EIGHT","NINE"};
const char *tens[] = {"ZERO","TEN","TWENTY","THIRTY","FORTY","FIFTY","SIXTY","SEVENTY","EIGHTY","NINETY"};
const char *ten[] = {"TEN","ELEVEN","TWELVE","THIRTEEN","FOURTEEN","FIFTEEN","SIXTEEN","SEVENTEEN","EIGHTEEN","NINETEEN"};

class listing
{

public:
	string name;
	string transform;
	string number;
	listing();
	listing(string,string,string);
};

listing::listing(string n,string nm,string t)
{
	number = n;
	name = nm;
	transform = t;
}

vector<string> convert(string num)
{
	int len = num.length();
	vector<string> parts;
	while(len > 3)
	{
		string part1 = num.substr(len-3,3);
		parts.push_back(part1);
		num = num.substr(0,len-3);
		len = num.length();
	}

	if(!num.empty())
		parts.push_back(num);

	return parts;
}

string alphabetise(string a)
{
	string ans("");
	int len = a.length();
	if(len == 3)
	{	
		if(a[0] - '0')
		{
			if(!ans.empty())
				ans.append(" ");

			ans.append(ones[a[0]-'0']);
			ans.append(" HUNDRED");
		}

		if(a[1] == '1')
		{
			if(!ans.empty())
				ans.append(" ");

			ans.append(ten[a[2]-'0']);
			a[2] = '0';
		}
		else if(a[1] - '0')
		{
			if(!ans.empty())
				ans.append(" ");

			ans.append(tens[a[1]-'0']);
		}


		if(a[2] - '0')
		{
			if(!ans.empty())
				ans.append(" ");
			ans.append(ones[a[2]-'0']);
		}
	}
	else if(len == 2)
	{
		if(a[0] == '1')
		{
			if(!ans.empty())
				ans.append(" ");

			ans.append(ten[a[1]-'0']);
			a[1] = '0';
		}
		else if(a[0] - '0')
		{
			if(!ans.empty())
				ans.append(" ");

			ans.append(tens[a[0]-'0']);
		}

		if(a[1] - '0')
		{
			if(!ans.empty())
				ans.append(" ");
			ans.append(ones[a[1]-'0']);
		}
	}
	else if(a[0] - '0')
	{
		if(!ans.empty())
			ans.append(" ");
		ans.append(ones[a[0]-'0']);
	}

	return ans;
}

string transform(string input)
{
	string t(""),word;
	int i=0,len = input.length();

	while(i < len)
	{
		if(isalpha(input[i]))
		{	
			bool allcaps = true;
			while(i< len && isalpha(input[i]))
			{
				if(islower(input[i]))
					allcaps = false;
				word.push_back(input[i]);
				i++;
			}

			// process the word
			if(allcaps)
			{
				int j = 0;
				t.push_back(toupper(word[j++]));

				while(j < word.length())
				{
					t.push_back(' ');
					t.push_back(toupper(word[j++]));
				}
			}
			else
			{
				int j = 0;
				while(j < word.length())
					t.push_back(toupper(word[j++]));
			}

			word.clear();

		}
		else if(isdigit(input[i]))
		{
			while(i< len && isdigit(input[i]))
			{
				word.push_back(input[i]);
				i++;
			}

			int j=0;
			while(j < word.length() && word[j] == '0')
				j++;

			if(j == word.length())
			{
				// append "ZERO" j times;
				if(!t.empty() && t[t.length()-1] != ' ')
					t.append(" ");
				while(j--)
				{
					t.append("ZERO");
					if(j)
						t.append(" ");
				}
			}
			else
			{
				word = word.substr(j);
				vector<string> parts = convert(word);
				string al;
				int j = parts.size() - 1;
				for(j;j>=0;j--)
				{
					al = alphabetise(parts[j]);
					if(!al.empty())
					{
						if(!t.empty() && t[t.length()-1] != ' ')
							t.append(" ");
						t.append(al);
						if(j==1) t.append(" THOUSAND");
						if(j==2) t.append(" MILLION");
					}
				}
			}
			word.clear();
		}
		else
		{
			while(i<len && !isdigit(input[i]) && !isalpha(input[i]))
				i++;
			t.push_back(' ');
		}
	}

	return t;
}

bool compare(listing a,listing b)
{
	if(a.transform < b.transform)
		return true;
	else
		return false;
}

int main()
{
	string number,name,line;
	vector<listing> output;

	while(getline(cin,line))
	{
		number = line.substr(0,7);
		number.insert(3,1,' ');
		name = line.substr(7);
		listing obj(number,name,transform(name));
		output.push_back(obj);
	}

	sort(output.begin(),output.end(),compare);
	vector<listing>::const_iterator iter = output.begin();
	while(iter != output.end())
	{
		cout.width(52);
		cout.setf(ios::left,cout.adjustfield);
		cout.fill(' ');
		cout << iter->name.substr(0,52);
		cout << "   ";
		cout << iter->number << "\n";
		iter++;
	}

	return 0;
}

[brianfry713]

For your input, my AC output is:

Code: Select all

????                                                   123 4567
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz   123 4567
Do u know me?                                          123 4567
Excuse me 1000                                         123 4567
59 steps                                               123 4567
fifty nine steps and alll                              123 4567
Fine Foods                                             837 2974
511 steps                                              123 4567
511511 steps                                           123 4567
Five Star Vending                                      927 3664
KAT Shop                                               893 6251
KAT shop                                               123 4567
K-B Enterprises                                        352 3984
K-B enterprises                                        123 4567
K W clop                                               123 4567
K W street                                             123 4567
K Warehouse                                            123 4567
Kate's Company                                         725 1887
9 steps                                                123 4567
19 steps                                               123 4567
99 Cents Only Store                                    723 6218
1000 books                                             123 4567
1000 words                                             123 4567
Penny Saver, Inc.                                      736 2812
Penny-Wise Corporation                                 352 3984
Pennypinching Company                                  352 3984
743521578 steps                                        123 4567
611511511 steps                                        123 4567
10 steps                                               123 4567
25 steps                                               123 4567

The only difference is in the ties, which I just checked for and they do not appear in the judge's input. I don't do any special handling for ties, and I use the c++ STL sort() on a vector.

Your other input also fails my tie check, as both 000 and 0000 are converted by my code to ZERO, but here is my AC output if I remove my assert() for ties:

Code: Select all

0001                                                   123 4567
000                                                    123 4567
0000                                                   123 4567

[brianfry713]

Try this input:

Code: Select all

123456700 A
12345670 B

My AC output:

Code: Select all

123456700 A
12345670 B

[mathgirl]

Thanks Brian. My problem was handling the "0" inputs. Got AC now.

[anacharsis]

I was certain that the test data was improperly formatted on this one.
SURPRISE, it's not!

When you expand the numbers to text, don't use any 'ands' between the numbers.
So, 101 is ONE HUNDRED ONE, and NOT ONE HUNDRED AND ONE

And even though the number to text expansion seems easy, I had to write a bunch of unit tests.
I had a set of tests for numbers of each length from 1 to 9 digits.
I caught 5 or 6 bugs that way.

And now...it's miller time