Почему оно падает?

[ivank]

Совсем себя криворуким что-то считать себя начал... Для решения этой простой задачи ( 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;
}

[chOOk]

Уважаемы ivank, вы часом не гений по части алгоритмизации? Сложность этой задачи на Timus'е = 84%, процент принятых задач - 6%
"легкая..." :)

Вероятнее всего причина в том, что в проверяющей системе стоит компилятор MSVC 6.0 и там замечено много глюков с STL

Еще одна прична - возможность наличия во входных данных букв в верхнем регистре.

[ivank]

chOOk
Я не гений. Совсем не гений. Но по-моему эта задача без проблем решается полным перебором.