VPF::Не укладывается во время - Форум программистов

megabist

Дата 25.1.2009, 14:08 (ссылка)

(нет голосов)

Загрузка ...

Mart Slaaf

Профиль
Группа: Участник
Сообщений: 455
Регистрация: 3.4.2006
Где: Мск

Репутация: нет
Всего: 31

Вот условия:

Цитата

Вопль

Time limit = 4
Вожди племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите M букв).

После долгих исследований было выяснено, что если в вопле встречается слово si, то страшность слова увеличивается на fi, причем учитывается каждое вхождение слова.

Требуется по заданным M, N и списку страшных слов составить максимально страшный вопль.

Вход Первая строчка содержит три числа — N, M и K. ( 1 ≤ N ≤ 100, 1 ≤ M ≤ 25, 1 < K ≤ 100 ), где K — количество различных страшных слов. В следующей строчке записан алфавит — строка из M маленьких латинских букв. Далее в K строчках следует информация о страшных словах — в каждой строчке страшное слово si и через пробел его страшность fi (точнее не страшность, а величина страшности, которую данная комбинация букв вносит в страшность вопля, страшность слова si может быть страшнее fi).

Страшность — это натуральное число меньше 10000. Эталонные страшные слова во входе не повторяются.

Выход Необходимо вывести максимальную страшность и один из максимально страшных воплей на следующей строчке.

я написал следующую програмку:

Код


//---------------------------------------------------------------------------

#include <vcl.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#pragma hdrstop

//---------------------------------------------------------------------------


 struct baseword{
  AnsiString slovo;
  int hatecount;
 };
 struct data{
  int lengthwor,lengthalph,wordcount;
  AnsiString alphabet;
  struct baseword words[100];
 } maindata;

 struct answer{
  int hatecount;
  AnsiString slovo;
 } mainanswer,auxanswer;

#pragma argsused
void ask_info ()
{
 int i;
 char dvaccatpjat[25];
 char sto[100];
 scanf("%d %d %d", &maindata.lengthwor, &maindata.lengthalph, &maindata.wordcount);
 scanf("%s", &dvaccatpjat);
 maindata.alphabet = AnsiString (dvaccatpjat);
 for (i=0;i<maindata.wordcount;i++)
 {
  scanf("%100s %d", &sto, &maindata.words[i].hatecount);
  maindata.words[i].slovo = AnsiString(sto);
 }
}

void hateme()
{
 int i;
 AnsiString auxory;
 auxanswer.hatecount=0;
 for (i=0;i<maindata.wordcount;i++)
  {
   auxory=auxanswer.slovo;
   while (auxory.Pos(maindata.words[i].slovo)!=0)
   {
    auxory.Delete(auxory.Pos(maindata.words[i].slovo),maindata.words[i].slovo.Length());
    auxanswer.hatecount = auxanswer.hatecount + maindata.words[i].hatecount;
   }
  }
 if (mainanswer.hatecount<auxanswer.hatecount)
 {
  mainanswer.hatecount=auxanswer.hatecount;
  mainanswer.slovo=auxanswer.slovo;
 }
}

void test_all ( int pointer)
{
     char sto[100];
 int i;
 if (pointer<maindata.lengthwor)
  for (i=0;i<maindata.lengthalph;i++)
   {
    char *sto;
    sto= new  char[auxanswer.slovo.Length()+1];
    sto=auxanswer.slovo.c_str();
    sto[pointer]=maindata.alphabet.c_str()[i];
    auxanswer.slovo=AnsiString(sto);
    test_all(pointer+1);
   }
 else
  hateme();
}

 int main()
{
 int ptr=0;
 ask_info();
 test_all(ptr);
 printf(mainanswer.slovo.c_str());
 printf(IntToStr( mainanswer.hatecount).c_str());
 getch();

        return 0;

}

//---------------------------------------------------------------------------

На маленьких значениях, когда выходная строка порядка 4 символов, работает почти правильно. А вот символов на 7 строка уже совсем зависает. подскажите пожалуйста, что может быть не так. Моё подозрение было в том, что я как-то неправильно с нахождением базовых слов работаю.

Присоединённый файл ( Кол-во скачиваний: 2 )

Unit1.cpp 2,06 Kb

--------------------

Don't panic!

Жди, и Фатум тебя приведёт...

xvr

Дата 26.1.2009, 17:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 48
Всего: 223

Задача должна решаться с другого конца - надо из списка страшных слов составлять возможные комбинации длинны N (добивая то, что короче N любыми буквами из алфавита).
Кроме того, считать слова путем поиска их в строке и удаления - крайне неэффективно, лучше считать с позиции (от 1й и каждой следующей, после найденной)
Так же, можно считать вхождение СРАЗУ всех слов в сроке за один проход - ключевые слова для поиска: regexp, NFA, DFA

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C++ Builder \| Следующая тема »