IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> "Гангстеры", олимпиадная задача
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


Помогите пожалуйста с задачкой, нужно для курсовика.

N гангстеров собираются в ресторан, i-й гангстер приходит в момент времени Ti, богатство этого гангстера Pi. Дверь ресторана имеет К+1 степень открытости, они обозначаются целыми числами из интервала [0,К]. Степень открытости двери может изменяться на единицу за единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же положении в котором и была. В начальный момент времени дверь закрыта (положение 0). i-й заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0,Т]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.
Ограничения: 1<=N<=100, 1<=T<=30 000, 0<=Ti<=T, 1<=Pi<=300, 1<=Si<=K, все числа целые, время 2 с.
Ввод из файла gangster.out. Вывести 1 число- максимальное суммарное богатство гангстеров, попавших в ресторан. Если зайти не удалось никому, вывести 0.

Примеры
Ввод1_____ Ввод2
4_ 10_ 20 _____ 2 _ 17 _ 100
10_16_ 8_16 _____ 5 _ 0
10_11_15_1______ 50 _ 33
10_ 7_1_8 ______ 6 _ 1

Ввод1_____Ввод2
26 _____ 0

________________________________________________


в интернете смогла найти примерное решение одной из процедур, но так как в Паскале я тю тю, очень прошу помочь сделать полностью smile.gif

Данные
Исходный код
Const MaxN=500;
MaxK=100;
Var N,K,Tend:Integer;
S,P,T:Array[0..MaxN] Of Integer;
Основная программа
Begin
Init;
Solve;
Done;
End.
Приведем только процедуру Solve, остальные достаточно очевидны.
Procedure Solve;
Var i,j:Integer;
SOld,SNew:Array[0..MaxK] Of LongInt;
{массивы для формирования оценок вершин решетки}
Begin
SOld[0]:=0;
For i:=1 To K Do SOld[i]:=-MaxLongInt;
SNew:=SOld;
For i:=1 To Tend Do Begin
{цикл по моментам времени}
SNew[0]:=SOld[0];
For j:=1 To i Do
{цикл по достижимым состояниям решетки}
SNew[j]:=Max(SOld[j-1],SOld[j]);
{реализация функции Max очевидна}
{формирование оценок вершин решетки}
For j:=1 To N Do {цикл по посетителям}
If (T[j]=i) And (SNew[S[j]]<>-MaxLongInt)
{если время прихода посетителя совпадает
с рассматриваемым моментом времени
и состояние достижимо, то изменяем
оценку вершины, соответствующей полноте
посетителя}
Then Inc(SNew[S[j]],P[j]);
SOld:=SNew;{запоминаем массив оценок}
End;
Res:=-MaxLongInt;
For i:=1 To K Do Res:=Max(Res,SNew[i]);
{находим максимальное значение
в окончательном массиве оценок}
End;


Сообщение отредактировано: Altair -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






To: Рыженькая
Вот тут есть решение твоей задачи полностью, правда на Сях... Разберешься, или перевести на Паскаль?
http://oasis.secna.ru/russian/olymp/acm98/...angster.cpp.htm
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 4
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


на Си я тоже это нашла, но я что в Си, что в Паскале norespect.gif . Я была бы очень признательна, если бы вы помогли перевести smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Рыженькая, держи wink.gif
{
N - "GANGSTERS"
}

Const
MaxN = 100;

Var
f_in, f_out: Text;
N, K, TT: Integer;
matr: Array[0 .. Succ(MaxN), 0 .. Succ(MaxN)] of integer;

Procedure GetData;
Var
i, j: integer;
T, P, S: Array[0 .. MaxN] Of Integer;
Flag: Boolean;
a: integer;
begin
ReadLn(f_in, N, K, TT);

T[0] := 0; P[0] := 0; S[0] := 0;
For i := 1 To N Do Read(f_in, T[i]);
For i := 1 To N Do Read(f_in, P[i]);
For i := 1 To N Do Read(f_in, S[i]);

For i := 1 To Pred(N) Do
For j := Succ(i) To N Do
If (T[i] = T[j]) and (S[i] = S[j]) Then Begin
Inc(P[i], P[j]); P[j] := 0; T[j] := TT+2;
End;

Flag := True;
While Flag Do Begin
Flag := False;
for i := 1 To Pred(N) Do
If T[i] > T[Succ(i)] Then Begin
a:=T[i]; T[i]:=T[i+1]; T[i+1]:=a;
a:=P[i]; P[i]:=P[i+1]; P[i+1]:=a;
a:=S[i]; S[i]:=S[i+1]; S[i+1]:=a;
Flag := False;
End;
End;

For i := N DownTo 1 Do
If T[i] > TT Then Dec(N);

For i := 0 To N Do
For j := 0 To N Do Matr[j, i] := 0;
For i := 1 To N Do
For j := 0 To Pred(i) Do
If (T[i]-T[j]) >= Abs(S[i]-S[j]) Then Matr[j, i] := P[i];

End;


Procedure Solve;
Var
MaxRes: LongInt;
i, j: integer;
res: Array[0 .. succ(MaxN)] Of LongInt;
Begin

For i := 0 To N Do res[i] := -1;
res[0] := 0;
For i := 1 To N Do Begin

For j := 0 To N Do
If (res[j] <> -1) and (i <> j) and
(Matr[j, i] <> 0) and (res[i] < res[j]+Matr[j, i]) Then
res[i] := res[j]+Matr[j, i];
End;

MaxRes := 0;
For i := 1 To N Do
If MaxRes < res[i] Then MaxRes := res[i];
WriteLn(f_out, MaxRes, ' ');
End;


begin
Assign(f_in, 'gangster.in'); Reset(f_in);
Assign(f_out, 'gangster.out'); Rewrite(f_out);

GetData;
Solve;

Close(f_out);
Close(f_in);
end.

Все комментарии я убрал, их смотри по моей ссылке, программа получилась практически 1 в 1, так что это будет просто сделать smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 4
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


Спасибо ооогромное blum.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 4
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


Если заходить по твоей ссылки, то коментарии к задаче в виде иероглифов, жалко...Может у кого нибудь нормально видно, напишите пожалуйста smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Рыженькая, кодировку поменяй на Cyrillic (KOI8-R)
smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






аха, всё получилось, большое спасибо smile.gif
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 16:37
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name