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
Hỏi tí về mã đề NKSGAME (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Ủ ĐỀ - Hỏi tí về mã đề NKSGAME
#70238
shell1508 (Thành viên)
shell1508
Đang tập code
Bài viết: 4
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Hỏi tí về mã đề NKSGAME 8 năm trước   (+0)
Mình làm test đúng theo đề bài, giới hạn cũng đúng. Thử nhiều test khác nhẩm cũng thấy đúng mà chấm bài mình chỉ được 6,67 thôi
Đây là code, mọi người xem giùm mình. Tks all
Code:
program  nksgame;
const  fi='';
  fo='';
var  f,g:text;
  a,b,c:array[0..100001] of longint;
        n,i:longint;
        kq:longint;
 
//-------------------------------------------------
 
procedure sum;
var  i,j,k:longint;
begin
  k:=1;
  while k<=sqr(n) do
        begin
          i:=1;
                while i<= n do
                begin
                  j:=1;
                          while j<=n do
                                begin
                    c[k]:=a[i]+b[j];
                                inc(j);
                                inc(k);
                                end;
                        inc(i);
                end;
        end;
 
 
end;
 
//-------------------------------------------------
 {
procedure benhat;
var  min:longint;
begin
  min:=c[1];
  for i:=1 to sqr(n) do
           begin
                  if min>c[i] then
                        begin
                        min:=c[i];
                        kq:=min;
                        end;
                end;
end;
 }
procedure bubble;
var  i,j,tmp:longint;
begin
  for i:=1 to sqr(n) do
          for j:=sqr(n) downto i do
                  if c[j]<c[j-1] then
                        begin
                          tmp:=c[j];
                                c[j]:=c[j-1];
                                c[j-1]:=tmp;
                        end;
end;
//-------------------------------------------------
begin
  assign(f,fi);reset(f);
        assign(g,fo);rewrite(g);
        read(f,n);
        if n>100001 then
        exit
        else
        begin
          for i:=1 to n do read(f,a[i]); if abs(a[i]) > 1000000001 then exit;
          for i:=1 to n do read(f,b[i]); if abs(b[i]) > 1000000001 then exit;
        end;
        sum;
//        benhat;
        bubble;
        kq:=c[0];
        write(g,kq);
        close(f);close(g);
 
end.
 
Mình không dùng bignum vì giới hạn đề chỉ có 1000000000 nhân 2 lên vẫn bé hơn maxlongint
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70241
khanhsuphu12 (Thành viên)
ngockhanh+1
Biết code binary-indexed tree
Bài viết: 23
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: Hỏi tí về mã đề NKSGAME 8 năm trước   (+0)
bài này mình thấy bạn làm kiểu này chắc ăn đc test nhỏ thôi vì có 3 vòng lặp lồng nhau.
Hướng giải quyết bài này là như thế này:
Mình Quicksort hai mảng A, B. Sau đó với mỗi giá trị trong dãy A vừa đc sắp xếp ta dùng tìm kiếm nhị phân trong mảng B để tìm kiếm giá trị gần với giá trị "-A" nhất. Với thuật toán như vậy thì ta có độ phức tạp là O(nlogn) giải quyết đc yêu cầu bài toán! Bạn thử làm theo cách đó xem sao.
p/s: với các giá trị mang tính hằng số chẳng hạn như "1000000001" hay "100001" bạn nên khai báo ở CONST
 
Đã lưu IP Đã lưu IP  
 
Code For FOOD
  Đã khóa chức năng gửi bài.
#70246
shell1508 (Thành viên)
shell1508
Đang tập code
Bài viết: 4
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: Hỏi tí về mã đề NKSGAME 8 năm trước   (+0)
khanhsuphu12 viết:
QUOTE:
bài này mình thấy bạn làm kiểu này chắc ăn đc test nhỏ thôi vì có 3 vòng lặp lồng nhau.
Hướng giải quyết bài này là như thế này:
Mình Quicksort hai mảng A, B. Sau đó với mỗi giá trị trong dãy A vừa đc sắp xếp ta dùng tìm kiếm nhị phân trong mảng B để tìm kiếm giá trị gần với giá trị "-A" nhất. Với thuật toán như vậy thì ta có độ phức tạp là O(nlogn) giải quyết đc yêu cầu bài toán! Bạn thử làm theo cách đó xem sao.
p/s: với các giá trị mang tính hằng số chẳng hạn như "1000000001" hay "100001" bạn nên khai báo ở CONST :)

đã làm lại test
hướng đi là tìm số nhỏ nhất của dãy a cộng với min dãy b
tks bạn đã giúp
btw, mình chưa học binary search
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70251
panaka_13 (Thành viên)
panaka_13
Đang tập code
Bài viết: 1
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: Hỏi tí về mã đề NKSGAME 8 năm trước   (+0)
bạn có thể làm thế này
sắp xếp lại a,b

s:=a.min + b.max và lưu lại min:=abs(s);

bạn xét s.
s<0 mình cần tăng giá trị của s thì mới mong tìm được kết quả tốt hơn
=> tăng a lên (do b đã max rồi)
s>0 tương tự ta giảm b xuống
s=0 xuất ra 0 luôn

cứ mỗi lần tìm được s mới thì so sánh với min đã có
 
Đã lưu IP Đã lưu IP  
  Đã 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