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: VNOI 2010 - Lời giải và thảo luận (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 5
CHỦ ĐỀ - Trả lời: VNOI 2010 - Lời giải và thảo luận
#23048
ConanKudo (Admin)
conankudo+149
Admin
Bài viết: 782
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
Bài 1:
Lời giải :
Đặt K = S / M, ta nhận thấy ngay để bài toán có nghiệm thì a[i] <= K với mọi i.
Giờ nếu ta trải dãy bi này ra thành một dãy dài S phần tử:
1 1 1 1 1 2 2 3 3 3. .. .. n n
Với hộp thứ I, chọn các viên bi thứ I , I + K , I + 2K … , I + (M-1)K, ta thấy ngay đây chính là một cách chọn đúng vì 2 viên bi liên tiếp ko thể nào có cùng màu ( do a[i] <= K).
Time cho bài này rất thoải mái ( theo tư tưởng thi QG ), một số bạn dùng Heap hay Priority Queue cũng có thể AC ( mỗi tội dài và dễ sai hơn thôi )
Code bằng Pascal:
Code:
var
    n,m,i,j,sum,k,cnt:longint;
    Beads,a:array[1..500000] of longint;
begin
    readln(n,m);
    sum:=0;
    for i:=1 to n do
        begin
            read(Beads[i]);
            sum := sum + Beads[i];
        end;
    cnt := 0;
    for i:=1 to n do
    for j:=1 to Beads[i] do
        begin
            inc(cnt);
            a[cnt] := i;
        end;
    k := sum div m;
    for i:=1 to k do
        begin
            for j:=0 to m-1 do write(a[i + j * k],' ');
            writeln;
        end;
end.
 
Đã lưu IP Đã lưu IP  
 
There are times when you can't save others with just love and kindness.
  Đã khóa chức năng gửi bài.
#23050
white_cobra (Thành viên)
Nhắm mắt code không bug
Bài viết: 188
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
 
Đã lưu IP Đã lưu IP  
 
Khiêm tốn , thật thà , dũng cảm
  Đã khóa chức năng gửi bài.
#23052
ConanKudo (Admin)
conankudo+149
Admin
Bài viết: 782
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
white_cobra viết:
QUOTE:
bài này hình như thấy ở đâu rồi . Đọc source của anh Kaiel giải cũng như thế .

Ở trong đề VNOI'10 em ạ
 
Đã lưu IP Đã lưu IP  
 
There are times when you can't save others with just love and kindness.
  Đã khóa chức năng gửi bài.
#23053
lebim (Thành viên)
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
Cho em hỏi, code em thế này, ko hiểu sao lại = 0d. :-s

Code:
const
 fi='';
 fo='';
 maxN=500000;
type
 ll=longint;
 tt=text;
 bo=boolean;
var
 A,L:array[0..maxN+1]of int64;
 M,N,h,x:ll;
 s:int64;
 f,g:tt;
 
procedure input;
var i,j:ll;
begin
 assign(f,fi);
 reset(f);
 assign(g,fo);
 rewrite(G);
 readln(f,n,m);
 s:=0;
 x:=0;
 for i:=1 to n do
  begin
   read(f,a[i]);
   inc(s,a[i]);
   for j:=1 to a[i] do
    begin
     inc(x);
     L[x]:=i;
    end;
  end;
 close(f);
 h:=s div m;
end;
 
procedure process;
var i,j:ll;
begin
 for i:=1 to h-1 do
  begin
   for j:= 1 to x do
    if (j mod h=i) then write(g,L[j],' ');
   writeln(g);
  end;
 for i:=1 to x do
  if i mod h = 0 then write(g,L[i],' ');
 close(g);
end;
 
begin
 input;
 process;
end.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23054
mrdl (Thành viên)
mrdl+4
Không code nữa rồi
Bài viết: 516
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
fi='marble.inp';
fo='marble.out';
do thế này này
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23055
lebim (Thành viên)
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
mrdl viết:
QUOTE:
fi='marble.inp';
fo='marble.out';
do thế này này :))


đã sửa lại rồi bạn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23056
lightning31 (Thành viên)
lightning31
Nhắm mắt code không bug
Bài viết: 168
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
Trời ạ, bài 2 ghi chi phí cạnh là số nguyên 32bit có dấu làm em tưởng có trọng số âm. Ai ngờ ở trên lại ghi là số tự nhiên. Chán thật, chỉ tại đọc đề không cẩn thận.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23057
cuthai1993 (Thành viên)
cuthai1993
Đã code là AC
Bài viết: 94
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
Cho em hỏi mọi người giải quyết bài 3 bằng cách nào ạ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23058
lebim (Thành viên)
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
hic, bạn nào giải thích zùm zới, thuật toán + code khá zống nhau.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#23059
ConanKudo (Admin)
conankudo+149
Admin
Bài viết: 782
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: VNOI 2010 - Lời giải và thảo luận 10 năm, 10 tháng trước   (+0)
lebim viết:
QUOTE:
Cho em hỏi, code em thế này, ko hiểu sao lại = 0d. :-s

Code:
 
 for i:=1 to h-1 do
  begin
   for j:= 1 to x do
    if (j mod h=i) then write(g,L[j],' ');
   writeln(g);
  end;
 
vòng for này có độ phức tạp là S^2/M, làm sao mà sống đc
 
Đã lưu IP Đã lưu IP  
 
There are times when you can't save others with just love and kindness.
  Đã 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