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: TCO 2012 Round 2A (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: TCO 2012 Round 2A
#62039
technolt (Admin)
technolt+70
Admin
Bài viết: 296
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
TCO 2012 Round 2A 8 năm, 9 tháng trước   (+0)
Đề khó quá, có ai làm được bài nào thì lên thảo luận đi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#62040
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
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: TCO 2012 Round 2A 8 năm, 9 tháng trước   (+1)
450:
Gọi input là x.
Chú ý là chỉ cần đặt các teleport door vào các điểm trong input.
Sort lại các tọa độ, nhét vào mảng c.
f(i,j) = chi phí của việc di chuyển trong các tọa độ <= c(i), và đặt j teleport door vào các điểm này.
Để tính f(i,j) dựa trên f(i',j-1) thì mình xét các đoạn x (t) --> x (t+1) giao với đoạn (c[i'], c[i]). Chú ý là để di chuyển trong đoạn này, mình chỉ cần quan tâm đến 2 teleport door ở c[i'] và c[i]

=.= Nhìn thấy 450 --> tưởng dễ --> nhảy vào --> gần hết giờ --> quay lại 300 ko kịp =.= T_T
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#62042
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
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: TCO 2012 Round 2A 8 năm, 9 tháng trước   (+1)
Cách làm 300 của mình:

Dựng đồ thị 2 phía, switch và lamp, giữa 2 đỉnh có cạnh nếu switch i có thể tương ứng với lamp j.
Ban đầu tất cả đều có cạnh. Với mỗi experiment, những cặp switch và lamp cho ra giá trị khác nhau sẽ bị xóa cạnh.
Nếu không thể tìm 1 cách gán mỗi switch vào mỗi lamp trên đồ thị còn lại (nghĩa là không thể tìm 1 bộ ghép đầy đủ) thì trả về -1.
Ngược lại đồ thị sẽ chia thành các vùng liên thông, mỗi vùng có số switch = số lamp.

1. Số experiment cần thêm cho vùng có x switch sẽ bằng min(i) thỏa 2^i >= x. (chỗ này mình fail vì chỉ nghĩ là x-1 )

CM: Mỗi experiment ta lấy x/2 đỉnh của vùng đó -> chia thành 2 vùng con có x/2 và x-x/2 đỉnh.

2. Kết quả là max experiment của các vùng.

CM: Do các vùng không liên quan với nhau nên có thể gộp chung experiment làm cùng lúc.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#62043
hieult (Thành viên)
hieult+9
Đã biết code đệ quy
Bài viết: 15
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: TCO 2012 Round 2A 8 năm, 9 tháng trước   (+1)
Cách làm của mình cũng tương tự như flash nhưng mà đoạn tính experiment thì cần lưu ý mỗi vùng liên thông tất cả x switch đều nối với x lamp vì tất các lamp này đều có trạng thái giống nhau trong tất cả các trường hợp
 
Đã 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