Yêu cầu Cho các số nguyên dương n, m, s và m cặp số (u, v) xác định từ u có thể kết nối trực tiếp tới được v. Hãy xác định số lượng trang web ổn định đối với s. Dữ liệu

Kết quả

Ví dụ

Input:

1 5

5 6

5 4

4 3

5 2

6 5
Output:

2

8. Nâng cấp mạng (2011 – vòng 1)

Một dãy các máy x₁, x₂, …, x_p trong đó giữa hai máy x_j và x_j+1 (j = 1, 2, …, p-1) có đoạn cáp nối được gọi là một đường truyền tin từ máy x₁ tới máy x_p. Thông lượng của đường truyền tin được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kì và giữa hai máy có không quá một đoạn cáp mạng nối chúng.

Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng d (d > 0) ta phải trả một chi phí đúng bằng d. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp mạng i đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy u_i tới máy v_i.

Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất.

Dữ liệu:

• 
  Dòng thứ nhất: Chứa hai số nguyên dương n, m (n, m <= 10^5).
  

• 
  Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương u_i, v_i, w_i (w_i<= 10^6),
  i = 1, 2, …, m.
  

Dữ liệu	Kết quả
6 7 1 2 6 1 3 5 2 4 3 3 4 9 4 5 4 4 6 8 5 6 7	5

9. Phân cụm (2006 – vòng 2)

Cho tập gồm n đối tượng X = {x₁, x₂, ..., x_n}, khoảng cách d(x_i, x_j) giữa mọi cặp x_i x_j và một số nguyên dương k (k  n). Giả thiết là d(x_i, x_j) là các số nguyên dương, d(x_i, x_j) = d(x_j, x_i) và d(x_i, x_i) = 0, với mọi i, j = 1, 2, ..., n. Ta gọi một cách phân cụm là một  cách phân hoạch tập X ra thành k tập con khác rỗng (mỗi tập con như vậy được gọi là một cụm). Cho C = {C₁, C₂, ..., C_k}  là một cách phân cụm, ta gọi độ phân tách của cách phân cụm C (ký hiệu là (C )) là giá trị nhỏ nhất trong số các khoảng cách giữa hai phần tử bất kỳ thuộc hai cụm khác nhau, nghĩa là

(C ) = min {d(u,v): u C_p, v C_q , p q }.

Yêu cầu: Tìm cách phân cụm với độ phân tách là lớn nhất.

Dữ liệu: Vào từ file văn bản CLUSTER.INP:

• 
  Dòng đầu tiên chứa hai số nguyên n và k.
  
• 
  Dòng thứ i trong số n dòng tiếp theo ghi các số d(x_i, x₁), d(x_i, x₂), ..., d(x_i, x_n), i = 1, 2, ..., n.
  

CLUSTER.INP	CLUSTER.OUT
4 3 0 1 2 3 1 0 2 3 2 2 0 3 3 3 3 0	2

• 
  Trong tất cả các test:1  n  200; d(x_i, x_j)  32000, i, j = 1, 2, ..., n.
  
• 
  Có 50% số lượng test với n 100.
  

10. Thoát mê cung (2006 – vòng 2)

Yêu cầu: Cho biết m, n, bản đồ số B và (u, v) – toạ độ một ô nào đó trong mê cung. Hãy xác định một cách đặt cửa cho các phòng đảm bảo thỏa mãn bản đồ B và thời gian T để thoát ra khỏi mê cung từ phòng (u, v) là ít nhất. Biết rằng dữ liệu bản đồ số B đảm bảo có ít nhất một cách đặt cửa để thoát ra ngoài.

• 
  Dòng đầu tiên chứa 4 số nguyên m, n, u và v.
  
• 
  Dòng thứ i trong m dòng sau chứa n số nguyên B_i1, B_i2,. . ., B_in.
  

Đưa ra số nguyên T.

• 
  Trong tất cả các test: 2 ≤ m, n ≤ 50.
  
• 
  Có 50% số lượng test với m, n ≤ 25.
  

4 4 3 3

1 0 3 2

0 1 0 0

3

11. Phương án phòng thủ (2007 – vòng 2)

Giả sử các hàng ngang được đánh số từ 1 đến m theo trình tự từ trên xuống dưới và hàng dọc được đánh số từ 1 đến n theo trình tự từ trái sang phải. Ô nằm trên giao của hàng ngang i và hàng dọc j được gọi là ô (i,j).

Hệ thống phòng thủ cần phải bảo đảm mỗi hàng ngang, hàng dọc đều có đủ số lượng chốt cần thiết. Bên cạnh đó, dựa vào thông tin tình báo, các chuyên gia cũng tính toán được khả năng đánh phá của địch p_ij (p_ij<1000) vào từng ô (i,j) trên trận địa (p_ij càng lớn nghĩa là khả năng địch đánh phá ô (i,j) càng cao). Căn cứ vào đó, người chỉ huy sẽ bố trí các chốt phòng thủ.

Bạn được mời làm cố vấn quân sự, hãy xác định phương án đặt vị trí các chốt phòng thủ trên trận địa đảm bảo được các yêu cầu về số lượng chốt phòng thủ đồng thời sao cho tổng khả năng đánh phá của địch vào các vị trí được chọn là nhỏ nhất.

·         Dòng đầu tiên chứa 2 số nguyên dương m, n (m, n ≤ 100),

·         Dòng thứ 2 chứa m số nguyên không âm lần lượt là số lượng chốt cần có từ hàng ngang thứ 1 đến hàng ngang thứ m,

·         Dòng thứ 3 chứa n số nguyên không âm lần lượt là số lượng chốt cần có từ hàng dọc thứ 1 đến hàng dọc thứ n,

·         m dòng tiếp theo, mỗi dòng chứa n số nguyên không âm mô tả các giá trị p_ij.

Các số trên cùng một dòng cách nhau bởi một dấu cách.

12. Tư vấn (2007 – vòng 2)

Một ngày cuối năm, có M khách (đánh số từ 1 đến M), mỗi khách cần tư vấn về một vấn đề. Khách chỉ có thể đến trung tâm có khả năng tư vấn về vấn đề của mình.

• 
  Dòng đầu ghi 2 số M (1 ≤ M ≤ 500), N (1 ≤ N ≤ 50),
  
• 
  Dòng tiếp ghi M chữ cái in hoa liên tiếp, trong đó chữ thứ i mô tả vấn đề cần tư vấn của khách i,
  
• 
  Dòng thứ j trong N dòng tiếp theo, ghi thông tin của trung tâm j, gồm một số nguyên là lượng khách cho phép tư vấn trong ngày (không quá 50), sau đó là một dấu cách, tiếp sau là một dãy các chữ cái in hoa liền nhau mô tả dãy vấn đề mà trung tâm có thể tư vấn.
  

Ví dụ:

ADVICE.INP		ADVICE.OUT
8 4 BNFQISNS 40 QIC 35 UPSF 45 FPHBU 15 WPSCNG		3

Каталог: forum -> attachment
forum -> Kiểm tra kiến thức Sinh học lớp 12
forum -> Danh sách giao lưu đại học Sookmyung ( 8/1/2014) Lớp 4H12
attachment -> CHƯƠng I: LẮp ráp và CÀI ĐẶt máy tíNH
attachment -> BÀi tập lớn môn: Kiến trúc máy tính Yêu cầu: Tìm hiểu kiến trúc mips
attachment -> BÀI 1 : html cơ sở 1-Thành phần-Element

tải về 418.79 Kb.

Chia sẻ với bạn bè của bạn: