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
ngày thi 2 (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Ủ ĐỀ - ngày thi 2
#70064
royalsilver16 (Thành viên)
royalsilver16+1
Super fast coder
Bài viết: 78
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
ngày thi 2 8 năm trước   (+0)
mọi người cho mình hỏi sol chuẩn bài 5 là gì nhỉ? mình thấy hầu như là dij n lần
 
Đã lưu IP Đã lưu IP  
 
I do what I like
I like what I do
  Đã khóa chức năng gửi bài.
#70065
silvertrinh304 (Thành viên)
Đã biết code đệ quy
Bài viết: 14
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: ngày thi 2 8 năm trước   (+1)
Tóm tắt sơ về 2 bài đầu:
Bài 4: Trộn xâu (STMERGE)
Cho hai xâu x và y gồm m kí tự và n kí tự, cần dựng xâu t (độ dài m+n) gồm tất cả kí tự trong x và y với thứ tự xuất hiện lần lượt trong t đúng như trong x và trong y. Chi phí trộn xâu tính bằng tổng các c(t_i,t_i+1) như sau:
- nếu t_i và t_i+1 lấy từ cùng 1 xâu thì c = 0;
- nếu lấy từ khác xâu thì sẽ có chi phí là c(x_i,y_j) (với hai kí tự liền kề nhau t_i,t_i+1 là x_i và y_j, i,j là vị trí trong xâu gốc)
Tính chi phí trộn xâu min.
Example:
Input:
1 (số lượng bộ dữ liệu)
2 3 (m và n)
3 2 30 (ma trận c(x_i,y_j))
15 5 4
Output: 6
(60% test có m,n<=10)

Bài 5: hành trình du lịch (TOURS)
Cho đồ thị gồm n đỉnh m cạnh có trọng số. Tìm và in ra n chu trình từ đỉnh i có chi phí nhỏ nhất (đi từ đỉnh i qua một số đỉnh khác và về lại i), in -1 nếu không tìm ra
Example:
Input:
1
6 8
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7
Output:
11
11
6
11
6
-1
 
Đã lưu IP Đã lưu IP  
 
Oops, Brainless.
  Đã khóa chức năng gửi bài.
#70066
iamnhvt (Thành viên)
iamnhvt123-
Super fast coder
Bài viết: 68
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: ngày thi 2 8 năm trước   (+0)
bài 1 dùng 2 mảng 2 chiều song song quy hoạch động đúng ko ạ em làm mà ko dám chắc
gọi x[i,j] là vị trí xi lớn hơn yj trong xâu k
y[i,j] là vị trí xi nhơ hơn yj trong xâu k
x[i,j]:=min(x[i-1,j],y[i-1,j]+c[i,j]);
y[i,j]:=min(y[i,j-1],x[i,j-1]+c[i,j]);
mấy anh cho em ý kiến cái công thức đó với ạ
sai 1 cái coi như em tiêu đời
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70068
silvertrinh304 (Thành viên)
Đã biết code đệ quy
Bài viết: 14
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: ngày thi 2 8 năm trước   (+1)
Dù code kém nhưng cũng cố đống góp vậy, tòm tắt nốt bài 3 và bổ sung giới hạn bài 2
Ràng buộc bài 2:
30% test: n<=20
30% test: 20<n<=100, m<=10^4
40% test: 100<n<=1000, m<=10^5
Mỗi test có số t ở đầu là số lượng bộ dữ liệu nhé quên mất

Bài 3: Sản xuất đồ chơi (ORGAN) chính xác hơn là sản xuất đàn organ
Cho n ống đàn với độ cao lần lượt h_1, h_2 ... h_n. Tìm cách chia n ống ra s nhóm sao cho thỏa mãn các điều kiện sau:
- tổng trọng lượng ống của nhóm nằm trong [b_min .. b_max], trọng lượng ống đàn i tính bằng (h_i * m)
- trong nhóm không có quá w vị trí mà h_i > h_i+1
Tìm số cách chia lớn nhất.
Example:
Input:
1 (số bộ dữ liệu)
5 2 2 1 9 12 (lần lượt: n, s, w, m, b_min, b_max)
4 6 2 3 7 (h_i)

Output: 8

Ràng buộc:
30%: n<=10
30%: 10<n<=30
40%: 30<n<=200
 
Đã lưu IP Đã lưu IP  
 
Oops, Brainless.
  Đã khóa chức năng gửi bài.
#70069
pencil_man (Thành viên)
pencil_man
Đã code là AC
Bài viết: 98
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: ngày thi 2 8 năm trước   (+0)
bài 3 không cài số lớn có thọt nhiều test ko nhỉ :-s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70070
varidly (Thành viên)
Đ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: ngày thi 2 8 năm trước   (+0)
mình chỉ làm được bài 2 ((dij heap)*n) với bài 3 (ko ăn đc test lớn). bài 1 biết là qhđ mà tìm mãi ko ra. ai làm được bài 1 với 3 đóng góp đi.
 
Đã lưu IP Đã lưu IP  
 
Không ngừng cố gắng và vươn xa!
  Đã khóa chức năng gửi bài.
#70072
quocbao66 (Thành viên)
quocbao66+4
Super fast coder
Bài viết: 69
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: ngày thi 2 8 năm trước   (+0)
Bài 1 mình làm qhđ trên 2 mảng 2 chiều, cơ mà ảo lắm, hai mảng chả liên quan gì tới nhau, chả biết có fail không, lo quá
Bài 2 mình cài n lần dijkstra heap. Mình nghĩ có thể ăn hết test.
Bài 3 thì chỉ cài đệ quy nhằm ăn 30% điểm số thôi

Ngày 2 đề có vẻ dể ăn hơn ngày 1 thì phải

Edit: Cảm ơn bạn namkcdhv_96 nhé, mình nhầm
 
Đã lưu IP Đã lưu IP  
 
Hamlet:
" Tồn tại hay không tồn tại. Đó mới là vấn đề "
  Đã khóa chức năng gửi bài.
#70073
chutieudepzai (Thành viên)
namkcdhv_96
Đã biết code đệ quy
Bài viết: 9
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: ngày thi 2 8 năm trước   (+0)
quocbao66 viết:
QUOTE:
Bài 1 mình làm qhđ trên 2 mảng 2 chiều, cơ mà ảo lắm, hai mảng chả liên quan gì tới nhau, chả biết có fail không, lo quá :(
Bài 2 mình cài n lần dijkstra heap. Mình nghĩ với dpt cỡ n^2 * log(n) thì có thể ăn hết test.
Bài 3 thì chỉ cài đệ quy nhằm ăn 30% điểm số thôi :D

Ngày 2 đề có vẻ dể ăn hơn ngày 1 thì phải :D

dijstra heap dpt (m+n)*log(n) bạn à
mỗi lần duyết các cạnh bạn update mất log n nữa
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70074
Nguyen_Duy_Khanh (Thành viên)
songuku95+25
Không code nữa rồi
Bài viết: 374
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: ngày thi 2 8 năm trước   (+0)
Bài 4 QHĐ O(n*m)
Bài 2 mình dùng floyd
Bài 3 chắc phải dùng bignum. Nếu không chắc ăn dưới 30%
 
Đã lưu IP Đã lưu IP  
 
Y!M: duy_khanh308
  Đã khóa chức năng gửi bài.
#70075
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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: ngày thi 2 8 năm trước   (+0)
chutieudepzai viết:
QUOTE:
quocbao66 viết:
QUOTE:
Bài 1 mình làm qhđ trên 2 mảng 2 chiều, cơ mà ảo lắm, hai mảng chả liên quan gì tới nhau, chả biết có fail không, lo quá :(
Bài 2 mình cài n lần dijkstra heap. Mình nghĩ với dpt cỡ n^2 * log(n) thì có thể ăn hết test.
Bài 3 thì chỉ cài đệ quy nhằm ăn 30% điểm số thôi :D

Ngày 2 đề có vẻ dể ăn hơn ngày 1 thì phải :D

dijstra heap dpt (m+n)*log(n) bạn à
mỗi lần duyết các cạnh bạn update mất log n nữa

Cho mình hỏi bài 2 làm dijkstra heap sẽ được khoảng bao nhiêu test
 
Đã 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