Вот такая интересная задача:
Имя входного файла: dice.in
Имя выходного файла: dice.out
Количество тестов: 15
Ограничение по памяти: 1 Мб
Ограничение по времени: 1 с
На клетчатом поле размером MxN в левом нижнем углу лежит игральная кость. За один ход ее можно перекатить на клетку вправо или вверх. Стоимостью пути называется сумма чисел на верхней грани кубика во всех клетках пути. Найдите минимальную стоимость пути в правый верхний угол.
Формат входного файла
В первой строке два натуральных числа N и M <= 1000 — размеры доски. Во второй строке три числа от 1 до 6 — числа на верхней, левой и передней грани кубика соответственно (сумма чисел на противоположных гранях кубика равна 7).
Формат выходного файла
Одно натуральное число — минимальная стоимость искомого пути.
Пример
dice.in
5 5
1 4 5
dice.out
29
Помогите с решением.
Полная версия: Задача о кубике
эта задача была то ли на россии ,то ли на каких то сборах ,завтра постараюсь выложить решение.
Цитата(virt @ 13.03.05 18:59)
эта задача была то ли на россии ,то ли на каких то сборах ,завтра постараюсь выложить решение.
Если выложишь, то спасибо!!!!!
Задача децкая, решаеться динамическим программированием.
В оригинале кубик лежит не в углу, как наказаанный, а в какой-то клетке доски, задаваемой координатами. И прийти ему тож надо в клетку, задаваемую координатами.
Решение можно найти в нете.
ЗЫ: у меня был код, да затерялся в гигабайтах фрагменированого NTFS
В оригинале кубик лежит не в углу, как наказаанный, а в какой-то клетке доски, задаваемой координатами. И прийти ему тож надо в клетку, задаваемую координатами.
Решение можно найти в нете.
ЗЫ: у меня был код, да затерялся в гигабайтах фрагменированого NTFS
Код
var a:array[1..1000,1..1000]of integer;
i,j,n,m:integer;
v,b,p:integer;
function sled(i,j:integer):integer;
begin
....
end;
..............
read(n,m);
read(v,b,p);
a[n,1]:=v;
for i:=n-1 downto 1 do
a[i,1]:=a[i+1,1]+sled(i,1);
for j:=2 to m do
a[n,j]:=a[n,j-1]+sled(1,j);
for i:=n-1 downto 1 do
for j:=2 to m do
if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......
i,j,n,m:integer;
v,b,p:integer;
function sled(i,j:integer):integer;
begin
....
end;
..............
read(n,m);
read(v,b,p);
a[n,1]:=v;
for i:=n-1 downto 1 do
a[i,1]:=a[i+1,1]+sled(i,1);
for j:=2 to m do
a[n,j]:=a[n,j-1]+sled(1,j);
for i:=n-1 downto 1 do
for j:=2 to m do
if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......
общий алгоритм очень прост.
функция sled выдает число которое будет на верхней грани.
Цитата(virt @ 14.03.05 20:05)
Код
var a:array[1..1000,1..1000]of integer;
i,j,n,m:integer;
v,b,p:integer;
function sled(i,j:integer):integer;
begin
....
end;
..............
read(n,m);
read(v,b,p);
a[n,1]:=v;
for i:=n-1 downto 1 do
a[i,1]:=a[i+1,1]+sled(i,1);
for j:=2 to m do
a[n,j]:=a[n,j-1]+sled(1,j);
for i:=n-1 downto 1 do
for j:=2 to m do
if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......
i,j,n,m:integer;
v,b,p:integer;
function sled(i,j:integer):integer;
begin
....
end;
..............
read(n,m);
read(v,b,p);
a[n,1]:=v;
for i:=n-1 downto 1 do
a[i,1]:=a[i+1,1]+sled(i,1);
for j:=2 to m do
a[n,j]:=a[n,j-1]+sled(1,j);
for i:=n-1 downto 1 do
for j:=2 to m do
if a[i,j-1]+sled(i,j-1) < a[i+1,j]+sled(i+1,j) then
a[i,j]:=a[i,j-1]+sled(i,j-1) else a[i,j]:=a[i+1,j]+sled(i+1,j);
......
общий алгоритм очень прост.
функция sled выдает число которое будет на верхней грани.
Не понял, как делать функцию sled, и как считать сумму.
ну а сам то подумай как sled реализовать ,определи например несколько состояний ,так что при переходе состояния однозначно меняются. Каждое состояние показавает какая цифра наверху ,и какая будет далешь ,и т.д.
ответ хранится в a[1,m] ::
ответ хранится в a[1,m] ::
Код
writeln(a[1,m]);
вот я написал пограммку.
вроде работает, нО(!):
чтение не из файла(не умею), и напиано при помощи рекурсии(только это и умею), ну и короче посмотри, может алгоритм поможет чем-нибудь...
Program Dice;
uses crt;
type
line=array[1..300] of shortint;
matrix=array[1..6] of shortint;
var
NN,MM,limit,k:integer;
mass:matrix;
lin:line;
procedure dices(masss:matrix;direct:char;n,m,turn:integer;way:line);
begin
if (n>NN) or (m>MM) or (turn>=limit) then exit
else
if n+m=NN+MM then begin
writeln('gotcha');
limit:=turn; {на данный момент наименьшая сумма верхних граней}
writeln(turn);
for k:=1 to n+m do
write(way[k],' ');
readln;
exit
end;
if direct='r' then {так кубик вращается вправо}
begin
k:=masss[5];
masss[5]:=masss[4];
masss[4]:=masss[3];
masss[3]:=masss[2];
masss[2]:=k;
n:=n+1 {позиция кубика по горизонтали}
end
else
if direct='u' then {так кубик вращается вверх}
begin
k:=masss[6];
masss[6]:=masss[2];
masss[2]:=masss[1];
masss[1]:=masss[4];
masss[4]:=k;
m:=m+1 {позиция кубика по вертикали}
end;
way[n+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних граней}
dices(masss,'u',n,m,turn+masss[2],way);
dices(masss,'r',n,m,turn+masss[2],way);
end;
BEGIN
clrscr;
writeln('ўўҐ¤ЁвҐ N');
readln(NN);
writeln('ўўҐ¤ЁвҐ M');
readln(MM);
limit:=(NN+MM)*5; {типа первый предел суммы, от фоная}
for k:=1 to 200 do
lin[k]:=0; {массив ходов}
writeln('ўўҐ¤ЁвҐ front');
readln(mass[1]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ up');
readln(mass[2]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ right');
readln(mass[3]); {это сам кубик}
mass[4]:=7-mass[2]; {это сам кубик}
mass[5]:=7-mass[3]; {это сам кубик}
mass[6]:=7-mass[1]; {это сам кубик}
dices(mass,'0',0,0,0,lin);
writeln('Done!');
readln
END
.
очень буду рад предложения по поводу того, как реализовать мою программу(если такое возможно) с требуемыми условиями задачи...
спасибо.
вроде работает, нО(!):
чтение не из файла(не умею), и напиано при помощи рекурсии(только это и умею), ну и короче посмотри, может алгоритм поможет чем-нибудь...
Код
Program Dice;
uses crt;
type
line=array[1..300] of shortint;
matrix=array[1..6] of shortint;
var
NN,MM,limit,k:integer;
mass:matrix;
lin:line;
procedure dices(masss:matrix;direct:char;n,m,turn:integer;way:line);
begin
if (n>NN) or (m>MM) or (turn>=limit) then exit
else
if n+m=NN+MM then begin
writeln('gotcha');
limit:=turn; {на данный момент наименьшая сумма верхних граней}
writeln(turn);
for k:=1 to n+m do
write(way[k],' ');
readln;
exit
end;
if direct='r' then {так кубик вращается вправо}
begin
k:=masss[5];
masss[5]:=masss[4];
masss[4]:=masss[3];
masss[3]:=masss[2];
masss[2]:=k;
n:=n+1 {позиция кубика по горизонтали}
end
else
if direct='u' then {так кубик вращается вверх}
begin
k:=masss[6];
masss[6]:=masss[2];
masss[2]:=masss[1];
masss[1]:=masss[4];
masss[4]:=k;
m:=m+1 {позиция кубика по вертикали}
end;
way[n+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних граней}
dices(masss,'u',n,m,turn+masss[2],way);
dices(masss,'r',n,m,turn+masss[2],way);
end;
BEGIN
clrscr;
writeln('ўўҐ¤ЁвҐ N');
readln(NN);
writeln('ўўҐ¤ЁвҐ M');
readln(MM);
limit:=(NN+MM)*5; {типа первый предел суммы, от фоная}
for k:=1 to 200 do
lin[k]:=0; {массив ходов}
writeln('ўўҐ¤ЁвҐ front');
readln(mass[1]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ up');
readln(mass[2]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ right');
readln(mass[3]); {это сам кубик}
mass[4]:=7-mass[2]; {это сам кубик}
mass[5]:=7-mass[3]; {это сам кубик}
mass[6]:=7-mass[1]; {это сам кубик}
dices(mass,'0',0,0,0,lin);
writeln('Done!');
readln
END
.
очень буду рад предложения по поводу того, как реализовать мою программу(если такое возможно) с требуемыми условиями задачи...
спасибо.
Код
Program Dice;
uses crt;
type
line=array[1..300] of shortint;
matrix=array[1..6] of shortint;
var
NN,MM,limit,k:integer;
mass:matrix;
lin,way:line;
procedure dices(masss:matrix;direct:char;n,m,turn:integer);
begin
if (n<1) or (m>MM) or (turn>=limit) then exit
else
if (nn-n+1)+m=NN+MM then
begin
limit:=turn; {на данный момент наименьшая сумма верхних граней}
lin:=way;
exit;
end;
if direct='r' then {так кубик вращается вправо}
begin
k:=masss[5];
masss[5]:=masss[4];
masss[4]:=masss[3];
masss[3]:=masss[2];
masss[2]:=k;
end else
if direct='u' then {так кубик вращается вверх}
begin
k:=masss[6];
masss[6]:=masss[2];
masss[2]:=masss[1];
masss[1]:=masss[4];
masss[4]:=k;
end;
way[(nn-n)+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних граней}
dices(masss,'u',n-1,m,turn+masss[2]);
dices(masss,'r',n,m+1,turn+masss[2]);
end;
BEGIN
clrscr;
writeln('ўўҐ¤ЁвҐ N'); readln(NN);
writeln('ўўҐ¤ЁвҐ M'); readln(MM);
limit:=maxint; {типа первый предел суммы, от фоная}
for k:=1 to 300 do
lin[k]:=0; {массив ходов}
way:=lin;
writeln('ўўҐ¤ЁвҐ front'); readln(mass[1]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ up'); readln(mass[2]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ right'); readln(mass[3]); {это сам кубик}
mass[4]:=7-mass[2]; {это сам кубик}
mass[5]:=7-mass[3]; {это сам кубик}
mass[6]:=7-mass[1]; {это сам кубик}
dices(mass,'0',nn,1,0);
readln;
END.
uses crt;
type
line=array[1..300] of shortint;
matrix=array[1..6] of shortint;
var
NN,MM,limit,k:integer;
mass:matrix;
lin,way:line;
procedure dices(masss:matrix;direct:char;n,m,turn:integer);
begin
if (n<1) or (m>MM) or (turn>=limit) then exit
else
if (nn-n+1)+m=NN+MM then
begin
limit:=turn; {на данный момент наименьшая сумма верхних граней}
lin:=way;
exit;
end;
if direct='r' then {так кубик вращается вправо}
begin
k:=masss[5];
masss[5]:=masss[4];
masss[4]:=masss[3];
masss[3]:=masss[2];
masss[2]:=k;
end else
if direct='u' then {так кубик вращается вверх}
begin
k:=masss[6];
masss[6]:=masss[2];
masss[2]:=masss[1];
masss[1]:=masss[4];
masss[4]:=k;
end;
way[(nn-n)+m]:=masss[2]; {промежуточный путь кубика в виде массива значений верхних граней}
dices(masss,'u',n-1,m,turn+masss[2]);
dices(masss,'r',n,m+1,turn+masss[2]);
end;
BEGIN
clrscr;
writeln('ўўҐ¤ЁвҐ N'); readln(NN);
writeln('ўўҐ¤ЁвҐ M'); readln(MM);
limit:=maxint; {типа первый предел суммы, от фоная}
for k:=1 to 300 do
lin[k]:=0; {массив ходов}
way:=lin;
writeln('ўўҐ¤ЁвҐ front'); readln(mass[1]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ up'); readln(mass[2]); {это сам кубик}
writeln('ўўҐ¤ЁвҐ right'); readln(mass[3]); {это сам кубик}
mass[4]:=7-mass[2]; {это сам кубик}
mass[5]:=7-mass[3]; {это сам кубик}
mass[6]:=7-mass[1]; {это сам кубик}
dices(mass,'0',nn,1,0);
readln;
END.
так вроде лучше.
Цитата
так вроде лучше.
ага, спасибо, вроде смотрю-правильно, а тест не работает... в чем ошибка
и 1000*1000 не получается-переполнение стека, че делать...
Цитата(madrabbit @ 18.03.05 21:56)
1000*1000 не получается-переполнение стека, че делать...
:D Любимая ошибка?
Ну, можешь увеличить размер под стек (первой строкой программы):
Код
{$M 65520, 0, 0}
Только при 1000х1000 программа будет очень долго выполняться (если этот алгоритм вообще приведет к решению)
volvo,
должен привести ,это полный перебор.
должен привести ,это полный перебор.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.