Đến nội dung

Hình ảnh

Giải bài toán quét vôi tối ưu bằng đệ quy


  • Please log in to reply
Chủ đề này có 10 trả lời

#1
transontung

transontung

    Binh nhất

  • Thành viên mới
  • 25 Bài viết

Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với màu trắng, xanh, vàng.Có 9 robot (đánh số từ 1 đến 9 ) phụ trách việc quét vôi các phòng. Mỗi robot chỉ quét vôi một số phòng nhất định. Việc quét vôi được thực hiện nhờ 1 chương trình cài sẵn theo quy tắc:

          - Nếu phòng đang có màu trắng thì quét màu xanh

          - Nếu phòng đang có màu xanh thì quét mau vàng

            - Nếu phòng đang có màu vàng thì quét màu trắng;.

Cần phải gọi lần lượt một số các robot ra quét vôi (mỗi lần 1 robot, một robot có thể gọi nhiều lần và có thể có robot không được gọi. Robot đc gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng tất cả các phòng đều có màu trắng.Hãy tìm ra phương án như vậy sao cho lượng vôi phải quét là ít nhất. Giả thiết rằng lượng vôi cho mỗi lượt quét đối với các phòng là như nhau.

 

DỮ LIỆU : đọc từ file văn bản ROBOT.INP gồm các dòng :

 - 9 dòng đầu, mỗi dòng mô tả danh sách các phòng đc quét vôi bởi 1 robot theo thứ tự từ robot 1 đến robot 9. Mỗi dòng như vậy gồm các số hiệu phòng viết sát nhau. Chẳng hạn dòng thứ 3 có nội dung 2356 mô tả robot 3 phụ trách việc quét vôi các phòng 2,3,5,6.

- Dòng cuối mô tả màu vôi ban đầu của các phòng. Dòng này gồm 9 kí tự viết sát nhau, ký tự thứ i biểu diễn màu vôi của phòng i với quy ước: kí tự T chỉ màu trắng, ký tự X chỉ màu xanh, ký tự V chỉ màu vàng.

 

KẾT QUẢ : đưa ra file văn bản ROBOT.OUT  gồm 2 dòng dưới dạng:

 - Nếu không có phương án thì ghi lại một chữ số 0

- Trái lại , ghi dãy thứ tự các robot đc gọi ( các số hiệu robot viết sát nhau).

 

VD:  

   ROBOT.INP                                                   ROBOT.OUT

                                                                                             

                                                                           41

   1245                                                                11224455699  

   123

   2356

   147

   13579

   369

   4578

   789

   5689

   XVXVTTVXX



#2
nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết

Nhận xét: Nếu 1 robot được gọi thực hiện quá 3 lần thì nó trở lại trạng thái ban đầu, nên nếu quét 3 lần trở đi thì k còn tối ưu. Từ đây có thể sinh dãy tam phân để thể hiện số lần quét từng robot và tìm đáp án. Độ phức tạp o(3^9);



#3
transontung

transontung

    Binh nhất

  • Thành viên mới
  • 25 Bài viết

Nhận xét: Nếu 1 robot được gọi thực hiện quá 3 lần thì nó trở lại trạng thái ban đầu, nên nếu quét 3 lần trở đi thì k còn tối ưu. Từ đây có thể sinh dãy tam phân để thể hiện số lần quét từng robot và tìm đáp án. Độ phức tạp o(3^9);

vậy làm hộ cái



#4
nghethuat102

nghethuat102

    Trung sĩ

  • Thành viên
  • 147 Bài viết

vậy làm hộ cái

tôi thích làm hay không đó là sự lựa chọn của tôi, và trong trường này câu trả lời là không.



#5
transontung

transontung

    Binh nhất

  • Thành viên mới
  • 25 Bài viết

tôi thích làm hay không đó là sự lựa chọn của tôi, và trong trường này câu trả lời là không.

Oài! Bạn hiểu lầm rồi . Ý tôi là bạn làm hộ tôi chứ không có ý khiêu khích j đâu.Nếu bạn nghĩ là có thì SORRY



#6
Zjkar

Zjkar

    Hạ sĩ

  • Thành viên
  • 82 Bài viết

Căng thăng quá ....



#7
transontung

transontung

    Binh nhất

  • Thành viên mới
  • 25 Bài viết

Ơ không ai làm được à  :(



#8
Fjzar

Fjzar

    Binh nhất

  • Thành viên mới
  • 30 Bài viết

Ơ không ai làm được à  :(

Để nghĩ cái đã  :huh:

Mà không hiểu cái vd .... <_<


Bài viết đã được chỉnh sửa nội dung bởi Fjzar: 10-03-2016 - 12:17


#9
Zjkar

Zjkar

    Hạ sĩ

  • Thành viên
  • 82 Bài viết

Căng thẳng thế

Thực sự không hiểu ví dụ cho lắm  :D

Ẹc .. vậy mà cũng nói ........ :mellow:



#10
mjko2000

mjko2000

    Lính mới

  • Thành viên mới
  • 2 Bài viết
var
a:array[0..100,0..100] of integer;
c,b:array[1..1000] of integer;
n,bd:integer;
procedure nhap;
var
f:text;
i,k:integer;
ch:char;
begin
assign(f,'robot.inp');
reset(f);
for i:=1 to 9 do begin
        k:=0;
        while not eoln(f) do begin
                k:=k+1;
                read(f,a[i,k]);
                end;
                b[i]:=k;
                readln(f);
        end;
for i:=1 to n do begin
        read(f,ch);
        if ch='X' then c[i]:=2;
        if ch='V' then c[i]:=1;
        if ch='T' then c[i]:=0;
        end;
close(f);
end;
procedure xuat;
var f:text;
i,j:integer;
begin
assign(f,'robot.out');rewrite(f);
if bd<>20000 then
        write(f,bd)
        else write(f,0);
close(f);
end;
function kt:boolean;
var
i:integer;
begin
        kt:=true;
        for i:=1 to 9 do if c[i]<>0 then kt:=false;
end;
procedure robot(i,dem:integer);
var
j,x,k,t:integer;
begin
        if i<=9 then for x:=0 to 2 do begin
                {d[bd]:=i;}
                if x=0 then robot(i+1,dem) else
                        if x=1 then begin for j:=1 to b[i] do begin
                        t:=c[a[i,j]];
                        if c[a[i,j]]=2 then c[a[i,j]]:=1 else if
                                c[a[i,j]]=1 then c[a[i,j]]:=0 else
                                        c[a[i,j]]:=2;
                                        if kt=true then if dem<bd then bd:=dem+1; end; robot(i+1,dem+1); c[a[i,j]]:=t;end else
                                            if x=2 then begin for j:=1 to b[i] do begin
                                                t:=c[a[i,j]];
                                                if c[a[i,j]]=2 then c[a[i,j]]:=0 else if
                                                c[a[i,j]]=1 then c[a[i,j]]:=2 else
                                                c[a[i,j]]:=1;if kt=true then if dem<bd then bd:=dem+2; end; robot(i+1,dem+2); c[a[i,j]]:=t; end;
                end;
end;
begin
nhap;
bd:=20000;
robot(1,0);
xuat;
end.


#11
HackerCM1011

HackerCM1011

    Lính mới

  • Thành viên mới
  • 1 Bài viết

t làm tới 9 phòng nhé. còn muốn làm n phòng thì sửa lại

 

 

const fi='test.inp'; fo='test.out';
var p:array[0..10000] of string;
    h:array[0..10000] of char;
    b,x,xbest:array[1..100] of byte;
    f:text;
    s:string;
    sv,svbest:longint;
 
 
    procedure doc;
    var i,j:longint;
        k:string;
    begin
        assign(f,fi); reset(f);
        fillchar(p,sizeof(p),0);
        for i:=1 to 9 do
        begin
            readln(f,p[i]);
        end;
        readln(f,s);
        for i:=1 to 9 do
        begin
                if s[i]='T' then b[i]:=0;
                if s[i]='X' then b[i]:=1;
                if s[i]='V' then b[i]:=2;
        end;
        close(f);
    end;
 
    procedure khoitao;
    begin
        svbest:=19;
        sv:=0;
    end;
 
 
 
 
    procedure inkq;
    var i,j:longint;
    begin
       // writeln(f,svbest);
        for i:=1 to 9 do
        for j:=1 to xbest[i] do write(f,i);
    end;
 
 
 
    procedure update;
    var i,sum:byte;
    begin
        sum:=0;
        for i:=1 to 9 do sum:=sum+ (b[i] mod 3);
        if (sum=0) and (sv<svbest) then
        begin
                svbest:=sv;
                xbest:=x;
        end;
    end;
 
 
 
 
    procedure try(i:byte);
    var spi,k,h,j:byte;
        st:string;
    begin
        if sv>svbest then exit;
        for j:=0 to 2 do
        begin
                x[i]:=j;
                st:=p[i];
                spi:=length(st);
                sv:=sv+spi*j;
                for k:=1 to j do
                        for h:=1 to spi do b[ord(st[h])-48]:=(b[ord(st[h])-48]+1);
                if i=9 then update
                else try(i+1);
                sv:=sv-spi*j;
                for k:=1 to j do
                        for h:=1 to spi do b[ord(st[h])-48]:=(b[ord(st[h])-48]-1);
        end;
    end;
 
begin
        doc;
        khoitao;
        try(1);
        assign(f,fo); rewrite(f);
        if svbest<19 then inkq
        else writeln(f,0);
        close(f);
end.
 
 
 
 
 
 
 
 
 
 





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh