Модератор: xdsl
Gemini писал(а):... В прошедшую пятницу господин Слинкин высказался весьма негодующе по поводу столь малого участия студентов информатики в олимпиадах (2е студентов ШГПИ из 11 участников заочной олимпиады по программированию) ...
Сие есть тайна великая. Могу только предполагать. Навскидку варианты:LMP писал(а):... но почему так мало?
LMP писал(а):PS: Архив задач - http://acm.timus.ru/.
4
A 30 50
B 50 0
C 70 0
D 10 20
B D A C
3
A 30 50
B 10 0
C 15 0
Error
xdsl писал(а):... Найти такую последовательность запуска задач, чтобы среднее время исполнения задачи было минимальным. ...
LMP писал(а):Что значит "среднее время исполнения задачи было минимальным". Насколько я понимаю среднее время всегда будет одинаковым и равно сумме всего "времени исполнения" делить на количество задач(кроме случаев простоя системы, но эта ситуация считается ошибкой).
xdsl писал(а):... А на лекции кто ходить будет? Ко всему прочему еще и экзаменационный вопрос будет, куда этот алгоритм включен. ...
xdsl писал(а):... P.S. Вас пока можно поздравить с 1 местом на заочной олимпиаде (до завершения периода аппеляций) ...
int rec(int h)
{
int i,k,g;
a1[max1]=a[h]; b1[max1]=b[h]; max1++;
if(max1>max)
{
max=max1;
for(g=0; g<max1; g++)
{
a2[g]=a1[g]; b2[g]=b1[g];
}
}
for(i=h+1; i<m; i++)
{
for(k=0; k<max1; k++)
{
if(a[i]==a1[k]||a[i]==b1[k]||b[i]==a1[k]||b[i]==b1[k])break;
}
if(k==max1) rec(i);
}
max1--;
}
max=0;
for(j=0; j<m; j++)
{
max1=0; rec(j);
}
912
101
111
141
121
210800
131008
111410
101101
101111
000101
310181
131417
111110
121910
121715
1 1
3 4
7 1
7 3
function test(i,j:integer):boolean; // возращает истину, если по координатам i,j области находится левый верхний угол образа
var k: integer;
begin
result:=false; // предполагаем, что образа в области нет
for k:=1 to obri do begin
if obraz[k]<>copy(data[i+k-1],j,obrj) then exit; // если действительно есть несовпадения в очередной строке образа и области - выходим
end;
result:=true; // вышли из цикла запланировано, значит образ полностью соответствует рассматриваемому участку области
end;
// начинаем основную программу
var found:boolean; i,j:integer;
begin
assign(input,'input.txt'); reset(input); // сопоставили стандартный поток ввода с файлом 'input.txt'
assign(output,'output.txt'); rewrite(output); // сопоставили стандартный поток вывода с файлом 'output.txt'
// две предыдущих операции проделали, чтобы перенаправить ввод и вывод на требуемые файлы
reada; // считали образ и область
found:=false; // считаем, что образ нигде с областью не совпадает
for i:=1 to datai-obri+1 do
for j:=1 to dataj-obrj+1 do // перебираем все точки области
if test(i,j) then begin
writeln(i,' ',j); // образ совпал с участком области, выводим координаты левого верхнего угла совпадения
found:=true;
end;
if not found then writeln('empty'); // совпадений не было, сигнализируем об этом
end.
7
001000000100
001000000101
000101000101
013101001100
010001010101
011111110101
001000010101
100010001111
000011011011
001000210011
uses Classes, SysUtils
var a:array[1..1000,1..1000,1..2] of integer;
// каждая ячейка матрицы содержит массив из двух элементов. В первом - сложность прохода по данной точке лабиринта, во втором в дальнейшем будем хранить
// минимальное кол-во шагов от данной точки до начальной.
ci:integer; cj:integer; // размеры матрицы
endi,endj:integer; // координаты конечной точки
begi,begj:integer; // координаты начальной точки (для данной задачи - необязательно, но на всякий случай)
difficulty:integer; // сложность прохода
current,i,j:integer; filled:boolean; // используются позднее
var ts:TStringList; // используется позднее для хранения списка найденных путей и выполнения их сортировки.
procedure reada;
var s:string;
begin
readln(difficulty);
ci:=0;
while not eof do begin
readln(s); s:=trim(s); if s='' then continue;
inc(ci);
for cj:=1 to length(s) do begin
case s[cj] of
'0': begin a[ci,cj,1]:=1; a[ci,cj,2]:=0; end;
'1': begin a[ci,cj,1]:=difficulty; a[ci,cj,2]:=0; end;
'2': begin a[ci,cj,1]:=1; a[ci,cj,2]:=1; begi:=ci; begj:=cj; end;
'3': begin a[ci,cj,1]:=1; a[ci,cj,2]:=0; endi:=ci; endj:=cj; end;
end;
end;
end;
end;
procedure spf;
begin
current:=0; // отвечает за текущую длину кратчайшего пути
filled:=false;
while not filled do begin // выходим из цикла, если не осталось необработанных точек матрицы
inc(current); // увеличиваем текущую длину кратчайшего пути
filled:=true; // предположим, что не осталось необработанных точек матрицы
for i:=1 to ci do begin
for j:=1 to cj do begin
if a[i,j,2]=0 then filled:=false; // предположение неверно, необработанные точки остались
if a[i,j,2]=current then begin
// если точка содержит текущий кратчайший путь, обрабатываем все ранее необработанное вокруг нее,
// с учетом сложности прохождения
if (i>1) and (a[i-1,j,2]=0) then inc(a[i-1,j,2],a[i-1,j,1]+current);
if (i<ci)and (a[i+1,j,2]=0) then inc(a[i+1,j,2],a[i+1,j,1]+current);
if (j>1) and (a[i,j-1,2]=0) then inc(a[i,j-1,2],a[i,j-1,1]+current);
if (j<cj)and (a[i,j+1,2]=0) then inc(a[i,j+1,2],a[i,j+1,1]+current);
end;
end;
end;
end;
end;
procedure outa;
var s:string;
begin
for i:=1 to ci do begin
for j:=1 to cj do begin
s:=format('%2d',[a[i,j,1]])+'('+format('%2d',[a[i,j,2]])+')'; write(s:7);
end;
writeln;
end;
writeln;
end;
7
001000000100
001000000101
000101000101
013101001100
010001010101
011111110101
001000010101
100010001111
000011011011
001000210011
1(16) 1(17) 7(24) 1(19) 1(18) 1(17) 1(16) 1(17) 1(18) 7(25) 1(26) 1(27)
1(15) 1(16) 7(23) 1(18) 1(17) 1(16) 1(15) 1(16) 1(17) 7(24) 1(25) 7(32)
1(14) 1(15) 1(16) 7(23) 1(16) 7(21) 1(14) 1(15) 1(16) 7(23) 1(24) 7(31)
1(13) 7(20) 1(17) 7(22) 1(15) 7(20) 1(13) 1(14) 7(21) 7(28) 1(23) 1(24)
1(12) 7(19) 1(16) 1(15) 1(14) 7(19) 1(12) 7(19) 1(14) 7(21) 1(22) 7(29)
1(11) 7(16) 7(21) 7(14) 7(13) 7(12) 7(11) 7(18) 1(13) 7(20) 1(21) 7(28)
1(10) 1( 9) 7(14) 1( 7) 1( 6) 1( 5) 1( 4) 7(11) 1(12) 7(19) 1(20) 7(27)
7(15) 1( 8) 1( 7) 1( 6) 7(11) 1( 4) 1( 3) 1( 4) 7(11) 7(18) 7(25) 7(32)
1( 8) 1( 7) 1( 6) 1( 5) 7(10) 7( 9) 1( 2) 7( 9) 7(16) 1(11) 7(18) 7(25)
1( 9) 1( 8) 7(11) 1( 4) 1( 3) 1( 2) 1( 1) 7( 8) 1( 9) 1(10) 7(17) 7(24)
procedure findpath(path:string; curi,curj:integer);
// path - закодированный текущий путь
// curi,curj - текущая позиция в матрице
begin
if a[curi,curj,2]=1 then begin
ts.add(path); // добрались до исходной точки, добавляем полученный путь в список путей
exit; // и выходим
end;
// следующими операторами ищем вокруг текущей позиции такие точки, из которых произошел переход в текущую
// и рекурсивно продолжаем поиск пути, переходя в эти точки
if (curi>1) and (a[curi-1,curj,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('D'+path,curi-1,curj);
if (curi<ci) and (a[curi+1,curj,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('U'+path,curi+1,curj);
if (curj>1) and (a[curi,curj-1,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('R'+path,curi,curj-1);
if (curj<cj) and (a[curi,curj+1,2]=a[curi,curj,2]-a[curi,curj,1]) then findpath('L'+path,curi,curj+1);
end;
begin
ts:=tstringlist.create;
assign(input,'input.txt'); reset(input); // сопоставили стандартный поток ввода с файлом 'input.txt'
assign(output,'output.txt'); rewrite(output); // сопоставили стандартный поток вывода с файлом 'output.txt'
// две предыдущих операции проделали, чтобы перенаправить ввод и вывод на требуемые файлы
reada; // загрузили исходные данные
spf; // нашли все кратчайшие пути
findpath('',endi,endj); // сформировали набор закодированных кратчайших путей от исходной точки к конечной
ts.sort; // отсортировали
for i:=0 to ts.count-1 do writeln(ts.strings[i]); // и вывели в результирующий файл
ts.free;
end.
program prog;
{$APPTYPE CONSOLE}
uses
SysUtils;
function DelX(es: String): String; // удаляет из строки все символы кроме цифр
var
i: Integer;
begin
Result:= '';
for i:= 1 to Length(es) do
if (es[i] >= '0') and (es[i] <= '9') then
Result:= Result+es[i];
end;
var
a: array [1..1000] of record
c1, c2: integer;
end;
c: Integer;
lSave, gSave: array [0..1000] of Integer;
procedure ReadD;
var
lc1, lc2: Integer;
s: String;
begin
while true do begin
Read(lc1);
Readln(s);
s:= DelX(s);
if (s = '') then
Break;
lc2:= StrToInt(s);
if (lc1 = lc2) then
Continue;
c:= c+1;
a[c].c1:= lc1;
a[c].c2:= lc2;
end;
end;
procedure ShowR;
var
i: Integer;
begin
Writeln(gSave[0]);
for i:= 1 to gSave[0] do
` Writeln(a[gSave[i]].c1, ' ', a[gSave[i]].c2);
end;
function Check(n: Integer): Boolean;
var
i, l1, l2, t1, t2: Integer;
begin
Result:= false;
t1:= a[n].c1;
t2:= a[n].c2;
for i:= 1 to lSave[0] do begin
l1:= a[lSave[i]].c1;
l2:= a[lSave[i]].c2;
if (t1 = l1) or (t1 = l2) or (t2 = l1) or (t2 = l2) then
Exit;
end;
Result:= true;
end;
procedure Find(n: Integer);
var
i, j: Integer;
begin
for i:= n+1 to c do begin
if Check(i) then begin
lSave[0]:= lSave[0]+1;
lSave[lSave[0]]:= i;
Find(i);
if (lSave[0] > gSave[0]) then
for j:= 0 to lSave[0] do begin
gSave[j]:= lSave[j];
end;
lSave[0]:= lSave[0]-1;
end;
end;
end;
begin
Assign(Input, 'input.txt'); // перенаправляем потоки ввода/вывода
Reset(Input);
Assign(Output, 'output.txt');
Rewrite(Output);{}
lSave[0]:= 0; // инициализируем переменные
c:= 0;
ReadD; // считываем входные данные
Find(0); // находим максимальную цепочку пар чисел
ShowR; // выводим результат
end.
Вернуться в Алгоритмизация и программирование
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3