Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: Bài LKNIGHT không có điểm (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Trả lời: Bài LKNIGHT không có điểm
#66540
lynklee (Thành viên)
lynk193
Đã biết code đệ quy
Bài viết: 12
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Bài LKNIGHT không có điểm 8 năm, 3 tháng trước   (+0)
Em làm với code sau:
Mọi người thử tìm nguyên nhân giúp mình
Code:
 
Const   fi='';fo='';
        MaxN=1000;
        dx:array[1..8] of Integer=(-2,-1,1,2,2,1,-1,-2);
        dy:array[1..8] of Integer=(1,2,2,1,-1,-2,-2,-1);
Type    Int=LongInt;
Var     f1,f2:Text;
        n,k,d,i,j:int;
        s:AnsiString;
Procedure OpenF;
Begin
        Assign(f1,fi);Reset(f1);
        Assign(f2,fo);Rewrite(f2);
        Readln(f1,n,k);
        Readln(f1,s);
End;
Procedure CloseF;
Begin
        Write(f2,d);
        Close(f1);Close(f2);
End;
Procedure Tinh;
Var     p,q,e:Int;
Begin
        i:=0;j:=0;
        For p:=1 to k do
                Begin
                        Val(s[p],q,e);
                        i:=i+dx[q];j:=j+dy[q];
                End;
End;
Procedure Process;
Var     x,y:Int;
Begin
        d:=0;
        For x:=1 to n do
                For y:=1 to n do
                        If (x+i>=1)and(x+i<=n)and(y+j>=1)and(y+j<=n) then Inc(d);
End;
BEGIN
        OpenF;
        Tinh;
        Process;
        CloseF;
END.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#66556
chicken123 (Thành viên)
chicken123
Đang tập code
Bài viết: 3
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài LKNIGHT không có điểm 8 năm, 3 tháng trước   (+0)
Thuật toán của bạn bị sai ở thủ tục Process
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#66557
thanghungkhi (Thành viên)
thanghungkhi+1
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài LKNIGHT không có điểm 8 năm, 3 tháng trước   (+0)
Ở phần tính, sau mỗi lần cộng i,j, bạn cho so sánh i với i nhỏ nhất và i lớn nhất, j với j nhỏ nhất và j lớn nhất.
imin, imax, jmin,jmax gán lần lượt là left, right, top, bottom. Rong=abs(rigth-left)+1 và Dai=abs(bottom-top)+1
Nói cách khác, bạn tìm bao chữ nhật của các ô mà mã đi qua xuất phát từ (0,0).
Nếu duyệt, với mỗi ô trong bảng, bạn cho so sánh với điều kiện Rong và Dai, sẽ AC.
Để nhanh hơn, khi thử test kĩ, bạn sẽ thấy chỉ cần sử dụng 1 phép tính nhân là có kết quả
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#66566
lynklee (Thành viên)
lynk193
Đã biết code đệ quy
Bài viết: 12
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài LKNIGHT không có điểm 8 năm, 3 tháng trước   (+0)
ban noi kho hieu qua
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#66567
shiningstar_193 (Thành viên)
shiningstar193+3
Nhắm mắt code không bug
Bài viết: 222
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài LKNIGHT không có điểm 8 năm, 3 tháng trước   (+0)
Gọi maxd,maxc lần lượt là chênh lệch tọa độ dòng và cột lớn nhất khi con mã đi từ một ô xuất phát bất kì đi theo dãy các nước đi cho ở đề bài.
Tương tự gọi mind,minc lần lượt là chênh lệch tọa độ dòng và cột nhỏ nhất khi con mã đi từ một ô xuất phát bất kì đi theo dãy các nước đi cho ở đề bài.
Gọi dd,cc là chênh lệch tọa độ dòng và cột của ô đích với ô xuất phát khi đi k nước đi.
=> dd:= ∑_(i=1)^k▒〖dx[i]〗; cc:=∑_(i≔1)^k▒〖dy[i]〗
Gọi kq là kết quả của bài toán.
Khởi tạo: kq:=0; maxd=-maxlongint;maxc=-maxlongint; mind:=maxlongint;minc:=maxlongint;dd:=0;cc:=0;
Ta có thể tính được maxd,maxc,mind,minc,dd,cc trong O(n) như sau:
Duyệt dãy đường đi của quân mã với mỗi nước đi x ta làm như sau:
+ dd:=dd+dx[x];cc:=cc+dy[x];
+maxd:=Max (maxd,dd);
+maxc:=Max (maxc,cc);
+mind:=Min (mind,dd);
+minc:=Min (minc,cc);
Sau khi duyệt hết k nước ta đã có dd,cc,maxd,maxc,mind,minc.
Gọi mảng a:array[1..maxn,1..maxn] of Boolean với ý nghĩa a[i,j]=true khi ô (i,j) là ô đích và a[i,j]=false nếu ô (i,j) không thể là ô đích khi thực hiện k nước đi đã cho.
Sau đó ta đi duyệt tất cả các ô có thể làm ô xuất phát với ô (i,j) xuất phát ta tính được ô đích khi đi k nước đi là:
U=i+dd;
V=j+cc;
Điều kiện để ô (u,v) là ô đích khi và chỉ khi (u,v) thuộc bàn cờ, a[u,v]=true và trong dãy đường đi đó quân mã không được đến bất cứ ô nào ngoài bàn cờ tức là:
+) i+maxd<=n, j+maxc<=n
+) i+mind>0, j+minc>0
Nếu thỏa mãn các điều kiện trên thì ta tăng kq lên một đồng thời a[u,v]:=false.
Khi đó đáp án của bài toán là kq.
 
Đã lưu IP Đã lưu IP  
 
Dù chỉ là 1 ngôi sao nhỏ, không thể sánh bằng ánh trăng rực rỡ ở bên cạnh, nhưng cũng không vì thế mà cam chịu cuối đầu, vẫn ngày ngày vươn mình chiếu sáng khắp nhân gian
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS