|
|
|
|
Почему оно падает?
|
|
редкий гость Сообщения: 1696 |
Совсем себя криворуким что-то считать себя начал... Для решения этой простой задачи ( 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;
}
|
|
|
------- Отправлено: 13:55, 13-12-2002 |
|
chOOk
Сообщения: n/a |
Уважаемы ivank, вы часом не гений по части алгоритмизации? Сложность этой задачи на Timus'е = 84%, процент принятых задач - 6%
"легкая..."  Вероятнее всего причина в том, что в проверяющей системе стоит компилятор MSVC 6.0 и там замечено много глюков с STL Еще одна прична - возможность наличия во входных данных букв в верхнем регистре. |
|
Отправлено: 03:43, 19-01-2003 | #2 |
|
редкий гость Сообщения: 1696
|
Профиль | Сайт | Отправить PM | Цитировать chOOk
Я не гений. Совсем не гений. Но по-моему эта задача без проблем решается полным перебором. |
|
------- Отправлено: 04:31, 19-01-2003 | #3 |
|
Участник сейчас на форуме |
 |
Участник вне форума |
 |
Автор темы |
 |
Сообщение прикреплено |
| |||||
| Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
| падает VPN падает! не работает роутинг по статике | flexman | Microsoft Windows NT/2000/2003 | 0 | 01-06-2009 10:01 | |
| Разное - VISTA а оно вобще нужно? | ospa | Microsoft Windows Vista | 51 | 05-08-2007 13:05 | |
| truns cleaner зачем оно мне??? | Alyaa | Защита компьютерных систем | 9 | 26-08-2006 15:45 | |
| Что такое Msout32 и почему оно висит? | Daiz13 | Microsoft Windows 95/98/Me (архив) | 3 | 06-12-2002 03:31 | |
|
|
Время: 16:50. | © OSzone.net 2001-
|
|
Powered by: vBulletin Copyright ©2000 - 2025, Jelsoft Enterprises Ltd. |
