Форум на Исходниках.RU

Текст на заборе.

albom — Fri, 21 Mar 2003 19:57:17 +0000

albom: Да ну вас, грустно мне сегодня....

А пришло в голову то, что последовательность с наименьшим штрафом есть повторение некоторого слова, которое можно получить из исходных и некоторых других (если их нет в исходных). Потом мы расширяем все слова до нужной длинны (см вызов функции nok)и сравниваем их штрафы (их уже нужно считать самим). Ну и выбрав слово с наименьшим штрафом повторяем его n раз, и исчем в нем подстроку с минимальным штрафом. Она и есть ответ.

Текст на заборе.

dark0ut — Fri, 21 Mar 2003 19:40:24 +0000

dark0ut:

Цитата wormball, 21.03.03, 18:30:18

2albom

работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D

тут даже и не кусок...

Текст на заборе.

wormball — Fri, 21 Mar 2003 15:30:18 +0000

wormball: 2albom

работает она или нет, надо спрашивать у паскаля. ты бы написал, в чём заключается алгоритм и в чём его отличие от перебора, а то прислал здоровый кусок кода и радуется 8D

Текст на заборе.

albom — Thu, 20 Mar 2003 19:42:27 +0000

albom: Что-то в голову пришло, написал такую программу. Интересно, она работает?

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;

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;

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('ЏаЁ¬Ґа: ',copy(res2,sht,n));

readkey;

end.

Текст на заборе.

Cubloid — Thu, 20 Mar 2003 19:23:26 +0000

Cubloid: После полного перебора самое простое решение:
инициализируем одной буквой весь забор, считаем полную стоимость, принимаем ее за минимальную.
Ставим указатель на последнюю доску и входим в цикл.
1) Проверяем последня ли доска, если последняя, то сравнение штрафов и в случае успеха сохранение нового рекорда.
2) Текущая цена больше минимальной? Да, то пункт (4)
3) Доставляем доску после указателя, если забор не кончился, добавляем цену с учетом штрафов порожденных ей и перемещаем указатель. В случае добавления прыгаем в пункт (2)
4) Меняем доску под указаетлем если можем, сначала отнимаем штрафы порожденные предыдущей и ставим новую заместо нее и штрафы опять прибавляем. В случае смены прыгаем в пункт (2)
5) Убираем доску под указаетлем, снимаем штрафы, перемещаем указатель к началу на одну позицию. Если убрали первую доску в заборе, то конец, иначе прыгаем в пункт (4)

Задача похожа на задачу с коробкой, в которую надо положить предметы разного объема и веса, при этом добиться максимального веса при условии, что все предметы не помещаются в объем коробки.

Более элегантного решения не знаю.

Текст на заборе.

esperanto — Tue, 18 Mar 2003 21:22:35 +0000

esperanto: насколько я помню задача динамического програмирования

Текст на заборе.

albom — Sun, 16 Mar 2003 19:13:35 +0000

albom: Найти наименьшее общее кратное длинн слов, расширить все слова путем их повторения, посчитать штрафы новых слов, и взять из слова, с наименьшим штрафом, нужное кол-во букв? Больше ничего не придумал.
Блин, ну я и тупой.

Текст на заборе.

Testudo — Sun, 16 Mar 2003 06:40:00 +0000

Testudo: Не совсем! Более дорогое слово может состоять из нескольких "самых дешевых".
Алгоритм решения очень прост, поэтому подсказывать не буду: думайте сами. ;D

Текст на заборе.

kardinal — Sun, 16 Mar 2003 04:03:21 +0000

kardinal: Первое, что заметил, это неправильная постановка задачи.
Необходимо указать количества досок с каждой буквой. А то ответ напрашивается сам собой - взять буквы из слова за которое дается наименьший штраф!!!

Текст на заборе.

albom — Sat, 15 Mar 2003 19:35:47 +0000

albom: Что-то никак не пойму, как это решается? Поэтому приведу текст задачи полностью.

Цитата

Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "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

Честно, кроме полного перебора ничего не придумал :(