Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[44.220.255.141] |
|
Сообщ.
#1
,
|
|
|
Что-то никак не пойму, как это решается? Поэтому приведу текст задачи полностью.
Цитата Пример:Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "I", "N", "W". Некто строит незамкнутый забор длиной N досок. Имеются доски, на каждой из которых написана одна из букв "I", "N" или "W". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе. Например, если запрещенными словами являются IN - штраф 1 рубль и WIWI - штраф 100 рублей, то за построение забора WIWIWINI будет назначен штраф 201 рубль. Требуется написать программу определения такой последовательности досок в заборе, для которой штраф минимален. Ограничения Штрафы выражаются в рублях Речуйска и представляются целыми числами от 1 до 100. Количество запрещенных слов <= 50. Длины запрещенных слов <= 6 символов. Входные данные Первая строка файла входных данных INPUT.TXT содержит длину забора N, вторая - количество слов в списке мэра M. В каждой из последующих M строк записано нежелательное слово и через пробел - соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "I", "N" или "W". Входные данные корректны. Выходные данные Результат работы программы выводится в файл OUTPUT.TXT. Первая строка выходного файла должна содержать значение минимального штрафа, а вторая - последовательность из N букв, задающую один из возможных способов построения забора с минимальным штрафом. Цитата Честно, кроме полного перебора ничего не придумал [Входные данные] 8 8 W 10 I 10 N 30 WI 1 WW 10 II 11 WIW 2 IWI 3 [Результат] 98 IWIWIWIW |
Сообщ.
#2
,
|
|
|
Первое, что заметил, это неправильная постановка задачи.
Необходимо указать количества досок с каждой буквой. А то ответ напрашивается сам собой - взять буквы из слова за которое дается наименьший штраф!!! |
Сообщ.
#3
,
|
|
|
Не совсем! Более дорогое слово может состоять из нескольких "самых дешевых".
Алгоритм решения очень прост, поэтому подсказывать не буду: думайте сами. ;D |
Сообщ.
#4
,
|
|
|
Найти наименьшее общее кратное длинн слов, расширить все слова путем их повторения, посчитать штрафы новых слов, и взять из слова, с наименьшим штрафом, нужное кол-во букв? Больше ничего не придумал.
Блин, ну я и тупой. |
Сообщ.
#5
,
|
|
|
насколько я помню задача динамического програмирования
|
Сообщ.
#6
,
|
|
|
После полного перебора самое простое решение:
инициализируем одной буквой весь забор, считаем полную стоимость, принимаем ее за минимальную. Ставим указатель на последнюю доску и входим в цикл. 1) Проверяем последня ли доска, если последняя, то сравнение штрафов и в случае успеха сохранение нового рекорда. 2) Текущая цена больше минимальной? Да, то пункт (4) 3) Доставляем доску после указателя, если забор не кончился, добавляем цену с учетом штрафов порожденных ей и перемещаем указатель. В случае добавления прыгаем в пункт (2) 4) Меняем доску под указаетлем если можем, сначала отнимаем штрафы порожденные предыдущей и ставим новую заместо нее и штрафы опять прибавляем. В случае смены прыгаем в пункт (2) 5) Убираем доску под указаетлем, снимаем штрафы, перемещаем указатель к началу на одну позицию. Если убрали первую доску в заборе, то конец, иначе прыгаем в пункт (4) Задача похожа на задачу с коробкой, в которую надо положить предметы разного объема и веса, при этом добиться максимального веса при условии, что все предметы не помещаются в объем коробки. Более элегантного решения не знаю. |
Сообщ.
#7
,
|
|
|
Что-то в голову пришло, написал такую программу. Интересно, она работает?
uses crt; var n,m:byte; sl:array[1..100]of string[6]; sl2:array[1..100]of string; sh,sh2:array[1..100]of word; res,res2:string; i:word; c:char; k:set of char; nk:word; minn,min,sht:word; function nod(a,b:longint):longint; var p1,p2,p3:longint; begin if a>b then begin p1:=a;p2:=b end else begin p1:=b;p2:=a end; while p2<>0 do begin p3:=p1 mod p2; p1:=p2;p2:=p3; end; nod:=p1; end; function nok(a,b:longint):longint; begin nok:=a*b div nod(a,b); end; function get(const s:string):word; var a,z,r:word; begin r:=0; for a:=1 to m do for z:=1 to length(s)-length(sl[a])+1 do begin if copy(s,z,length(sl[a]))=sl[a] then inc(r,sh[a]); end; get:=r; end; procedure buildres(num:byte); var m:byte; begin res:=''; m:=1; while length(res)<n do begin res:=res+sl2[num][m]; m:=1+(m mod length(sl2[num])); end; end; begin clrscr; fillchar(sl,sizeof(sl),0); writeln('‚ўҐ¤ЁвҐ ¤«Ёг § Ў®а '); readln(n); writeln('‚ўҐ¤ЁвҐ зЁб«® б«®ў'); readln(m); writeln('‚ўҐ¤ЁвҐ б«®ў Ё ива дл'); k:=[]; for i:=1 to m do begin read(c); while c<>' ' do begin sl[i]:=sl[i]+upcase(c); read(c); end; readln(sh[i]); if length(sl[i])=1 then include(k,sl[i][1]); end; if not('I' in k) then begin inc(m);sl[m]:='I';sh[m]:=0;end; if not('N' in k) then begin inc(m);sl[m]:='N';sh[m]:=0;end; if not('W' in k) then begin inc(m);sl[m]:='W';sh[m]:=0;end; nk:=nok(length(sl[1]),length(sl[2])); for i:=3 to m do nk:=nok(length(sl[i]),nk); for i:=1 to m do begin sl2[i]:=''; while length(sl2[i])<nk do sl2[i]:=sl2[i]+sl[i]; sh2[i]:=get(sl2[i]); end; minn:=1;buildres(1);min:=get(res); for i:=2 to m do begin buildres(i); sht:=get(res); if sht<min then begin minn:=i; min:=sht; end; end; buildres(minn); res2:=res+res; min:=get(copy(res2,1,n));sht:=1; for i:=2 to length(res2)-n+1 do if get(copy(res2,i,n))<min then begin sht:=i;min:=get(copy(res2,i,n))end; writeln('ЊЁЁ¬ «мл© ива д: ',get(copy(res2,sht,n))); writeln('ЏаЁ¬Ґа: ',copy(res2,sht,n)); readkey; end. |
Сообщ.
#8
,
|
|
|
2albom
работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D |
Сообщ.
#9
,
|
|
|
Цитата wormball, 21.03.03, 18:30:18 2albom работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D тут даже и не кусок... |
Сообщ.
#10
,
|
|
|
Да ну вас, грустно мне сегодня....
А пришло в голову то, что последовательность с наименьшим штрафом есть повторение некоторого слова, которое можно получить из исходных и некоторых других (если их нет в исходных). Потом мы расширяем все слова до нужной длинны (см вызов функции nok)и сравниваем их штрафы (их уже нужно считать самим). Ну и выбрав слово с наименьшим штрафом повторяем его n раз, и исчем в нем подстроку с минимальным штрафом. Она и есть ответ. |