HomeChuyên đề

Đề thi học sinh giỏi tin học lớp 12 – TP Đà Nẵng – Năm học 2006 – 2007

Like Tweet Pin it Share Share Email
Like và share giúp mình phát triển website nhé.
  •  
  •  

Đề thi học sinh giỏi tin học lớp 12 – TP Đà Nẵng – Năm học 2006 – 2007

ĐỀ THI CHÍNH THỨC

 

Tổng quan đề thi Lá bài Phân phối kênh
Tên bài làm BL1.PAS BL2.PAS
Dữ liệu vào Labai.inp Kenh.inp
Dữ liệu ra Labai.out Kenh.out
Giới hạn 1 giây 2 giây

 

Bài 1:(5 điểm) Lá bài

          Có N lá bài với các số hiệu là 1, 2, …, N (N £ 50). Trên lá bài i ghi một số nguyên dương F[i], 1 £ F[i] £ N.

Yêu cầu: Hãy tìm nhiều lá bài nhất sao cho tập các số hiệu của chúng bằng với tập các số ghi trên các lá bài đó.

          Dữ liệu vào: Đọc từ file text LABAI.INP có cấu trúc như sau:

  • Dòng thứ nhất chứa số nguyên dương N.
  • Các dòng tiếp theo, mỗi dòng chứa 10 số (cho đến khi hết N số) lần lượt là  các số ghi trên các lá bài, từ lá bài 1 đến lá bài N, mỗi số cách nhau ít nhất một dấu cách.

          Dữ liệu ra: Kết quả ghi ra file text LABAI.OUT có cấu trúc như sau:

  • Dòng thứ nhất ghi số lượng lá bài.
  • Các dòng tiếp theo, mỗi dòng ghi 10 số hiệu của các lá bài được chọn, các số hiệu ghi theo thứ tự tăng dần cho đến hết, mỗi số cách nhau ít nhất một dấu cách.

          Ví dụ:

LABAI.INP LABAI.OUT
14

6 5 1 3 4 2 8 10 7 9

3 2 1 9

10

1 2 3 4 5 6 7 8 9 10

 

Bài 2:(5 điểm)   Phân phối kênh

Công ty dịch vụ mạng máy tính cần phân phối kênh hoạt động phục vụ cho N (N <1000)  yêu cầu của khách hàng đánh số từ 1 đến N. Với mỗi khách hàng thứ i, ta biết khoảng thời gian yêu cầu sử dụng kênh là (Si, Ti), i = 1, 2 , …, N (khách hàng sẽ sử dụng kênh từ thời điểm Si đến thời điểm Ti). Thời gian chuyển giao quyền sử dụng kênh từ khách hàng này cho khách hàng khác là không đáng kể. Như vậy, nếu hai khách hàng nào đó được bố trí làm việc trên cùng một kênh thì các khoảng thời gian sử dụng của họ chỉ có thể có nhiều nhất một thời điểm chung.

Yêu cầu: Hãy tìm cách phân phối sao cho sử dụng ít kênh nhất mà vẫn đảm bảo phục vụ cho N yêu cầu của khách hàng.

Dữ liệu vào: Đọc từ file text KENH.INP có cấu trúc như sau:

  • Dòng đầu tiên chứa số N.
  • Dòng thứ i trong số N dòng tiếp theo chứa hai số nguyên dương Si, Ti, i = 1, 2, …, N mỗi số cách nhau ít nhất một dấu cách.

Dữ liệu ra: Kết quả ghi ra file text KENH.OUT có cấu trúc như sau:

  • Dòng đầu tiên ghi số lượng kênh cần sử dụng p.
  • Dòng thứ i trong số p dòng tiếp theo ghi các chỉ số của các khách hàng sử dụng kênh thứ i, i = 1, 2, …, p.

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *