Совсем себя криворуким что-то считать себя начал... Для решения этой простой задачи ( http://acm.timus.ru/problem.asp?id=1002 ) на скору руку была сваяна следующая программа (см. ниже), как ни странно сразу великолепно откомпилилась (bcc55) и даже заработала, однако когда я её отсылаю на проверку робот мне шлёт мыло мол она завалилась с Access violation'ом. Вот мне интересно стало из-за чего же. Даже explicit memory managment'а не было.
Собственно код:
Код:
#include <iostream>
#include <string>
#include <list>
// It's a bit dirty way... Classes shoud have been used instead :)
typedef std::list< std::string > Solution;
typedef std::string DigitsSequence;
struct Word
{
std::string word, prepared_word;
Word( const std::string & _word, const std::string & _prepared_word ):
word ( _word ),
prepared_word( _prepared_word )
{}
};
struct Task
{
std::list< Solution > solutions;
std::list< Word > words;
std::string number; // it's simplier to use number as a
// sequence of digits (characters)
// Next data is used during solving.
Solution cur;
std::string::const_iterator pos_in_number;
};
struct LetterToDigit
{
char digit;
char * letters;
};
LetterToDigit letter_to_digit[[]] =
{
{ '0', "oqz" },
{ '1', "ij" },
{ '2', "abc" },
{ '3', "def" },
{ '4', "gh" },
{ '5', "kl" },
{ '6', "mn" },
{ '7', "prs" },
{ '8', "tuv" },
{ '9', "wxy" }
};
std::string prepare_word( const std::string & word )
{
std::string ret = word;
for( std::string::iterator it = ret.begin();
it != ret.end();
++it )
{
for( int i = 0; i < sizeof( letter_to_digit ); ++i )
for( char * c = letter_to_digit[[i]].letters; *c; ++c )
if( *it == *c )
{
*it = letter_to_digit[[i]].digit;
i = sizeof( letter_to_digit );
break;
}
}
return ret;
}
bool starts_of( std::string::const_iterator word,
std::string::const_iterator subword )
{
while( *subword )
{
if( *subword != *word )
return false;
++subword;
++word;
}
return true;
}
void find_solutions( Task & task )
{
for( std::list< Word >::const_iterator it = task.words.begin();
it != task.words.end();
++it )
{
if( starts_of( task.pos_in_number, it->prepared_word.begin() ) )
{
task.cur.push_back( it->word );
task.pos_in_number += it->word.size();
if( task.pos_in_number == task.number.end() )
task.solutions.push_back( task.cur );
else
find_solutions( task );
task.pos_in_number -= it->word.size();
task.cur.pop_back();
}
}
};
std::string find_best_solution( Task & task )
{
task.pos_in_number = task.number.begin();
find_solutions( task );
if( task.solutions.size() == 0 )
return "No solution.";
else
{
std::list< Solution >::const_iterator it
= task.solutions.begin();
std::list< Solution >::const_iterator shortest_solution = it;
for( ; it != task.solutions.end(); ++it )
if( it->size() < shortest_solution->size() )
shortest_solution = it;
Solution::const_iterator word = shortest_solution->begin();
std::string ret = *word;
if( ++word != shortest_solution->end() )
for( ; word != shortest_solution->end(); ++word )
ret += " " + *word;
return ret;
}
}
int main()
{
std::string tmp;
for( ;; )
{
std::cin >> tmp;
if( tmp == "-1" )
break;
Task task;
task.number = tmp;
int num;
std::cin >> num;
for( ; num > 0; --num )
{
std::cin >> tmp;
task.words.push_back( Word( tmp,
prepare_word( tmp ) ) );
}
std::cout << find_best_solution( task ) << "\n";
}
return 0;
}
|
