Đề thi Olympic 30/4 môn tin học khối 11 năm 2015

BÀI 1. Xếp hạng

Một cuộc thi đấu game có N game thủ tham gia, cùng chơi một trò có tên PICK. Mỗi game thủ đều có 1 phút để chơi và giành được một số điểm nào đó, tùy theo khả năng của họ. điểm đặc biệt của trò chơi PICK này là nó lấy thông tin chi tiết về các thao tác chơi của các game thủ khiến cho không có hai game thủ nào có thể có cùng số điểm.
Lần lượt các game thủ có số hiệu từ 1 đến N, đến lượt mình vào cuộc, chơi xong trong thời gian cho phép (1 phút) thì thông báo điểm thu được cho ban tổ chức và được ban tổ chức lập tức thông báo thứ hạng mà game thủ đó đạt được tính đến thời điểm thông báo (người cao điểm hơn sẽ có hạng cao hơn, điểm cao nhất có hạng 1, điểm cao thứ 2 sẽ có hạng 2,…). Hạng mà mỗi game thủ nhận được như vậy, cũng chính là hạng cao nhất có thể mà game thủ đó đạt được, tính cho đến thời điểm kết thúc cuộc thi.

Chẳng hạn, game thủ đầu tiên với số điểm thu được 12, sẽ được xếp hạng 1, game thủ thứ 2 với 17 điểm cũng sẽ được xếp hạng 1, game thủ thứ 3 với 16 điểm sẽ được xếp hạng 2, game thủ thứ 4 với 13 điểm được xếp hạng 3, v.v…
Yêu cầu: Cho số điểm giành được của lần lượt N game thủ tham gia và M số hiệu của các game thủ trong số đó, hãy cho biết hạng cao nhất của mỗi game thủ trong số M game thủ này.

Dữ liệu: Cho trong file văn bản RANKING.INP có:
• Dòng đầu chứa hai số nguyên dương N và M (1 ≤ M ≤ N ≤ 32676)
• Dòng thứ hai ghi lần lượt điểm giành được của N game thủ, bắt đầu từ game thủ số hiệu 1 (là người chơi đầu tiên), kết thúc cho game thủ thứ N (người chơi cuối cùng). ðiểm của mỗi game thủ là một số nguyên dương không vượt quá 10^6.

• M dòng tiếp theo kể từ dòng thứ ba, mỗi dòng ghi một số nguyên dương, là số hiệu của một game thủ (trong số N game thủ). (Dữ liệu đảm bảo luôn đúng đắn, tức là điểm của các game thủ đều khác nhau đôi một; các số trên cùng dòng đều cách nhau bởi khoảng trống)

Kết quả: Ghi ra file văn bản RANKING.OUT thành M dòng, là hạng cao nhất của game thủ tương ứng trong file dữ liệu

Ví dụ:

RANKING.INP

5 3

12 17 16 13 21

4

2

3

RANKING.OUT

3

1

2

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với N ≤ 2000.

• Giới hạn thời gian cho mỗi test: 01 giây. 

BÀI 2. Hoàng tử Ếch

Hoàng tử Ếch đang ở bờ này của con sông, phải nhảy được sang bờ bên kia- nơi công chúa đang bị mụ phù thủy giam giữ- để giải thoát cho nàng. để làm việc này, hoàng tử phải nhờ đến một số trong số N lá sen vốn được giăng thành hàng ngang trên mặt sông. Hoàng tử, xuất phát từ bờ bên này, chỉ có thể nhảy đến các lá sen phía trước mặt (không được nhảy giật lùi) hoặc nhảy thẳng sang bờ bên kia nếu muốn, lần lượt qua các lá sen (nếu cần) để rồi kết thúc được tại bờ bên kia. Việc nhảy như vậy phải tuân thủ quy tắc: nếu tổng số bước nhảy lớn hơn 1 thì mỗi bước nhảy sau không được dài hơn bước nhảy trước đó.

Xem vị trí của hoàng tử (bờ bên này) và công chúa (bờ bên kia) cùng với mỗi lá sen như một điểm trên trục số: bờ bên này có tọa độ 0, bờ bên kia có tọa độ xN+1, lá sen i có tọa độ xi (i = 1, 2, …, N) thỏa điều kiện: 0 < x1 < … < xN < xN+1.

Trong quá trình nhảy, hoàng tử Ếch được tăng cường thêm sinh lực nhờ tận hưởng hết số muỗi thần có trên lá sen đặt chân đến: lá sen i có Mi con muỗi như vậy (i = 1, 2, …, N). đương nhiên,hoàng tử rất muốn mình dồi dào sinh lực nhất có thể tại thời điểm gặp được công chúa nhờ việc tận hưởng được số muỗi nhiều nhất Mmax.
Yêu cầu: Hãy viết chương trình xác định giá trị của Mmax.
Dữ liệu:

Vào từ file văn bản PRINCE.INP gồm N+2 dòng có cấu trúc như sau:
• Dòng đầu ghi một số nguyên N (1 ≤ N ≤ 500)
• Dòng thứ i trong N dòng tiếp theo ghi hai số nguyên xi , Mi (cách nhau bởi khoảng trống) tương ứng là tọa độ và số muỗi của lá sen i (1≤ xi ≤ 10^6, 1 ≤ Mi ≤ 10^9, i = 1, 2, …, N).
• Dòng thứ N+2 (dòng cuối cùng) ghi số xN+1.
Kết quả: Ghi ra file văn bản PRINCE.OUT số nguyên duy nhất Mmax tìm được.

PRINCE.INP

5

2 4

6 5

7 3

10 6

12 5

17

PRINCE.OUT

10

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với N ≤ 20.

• Giới hạn thời gian cho mỗi test: 01 giây.

BÀI 3. Khắc phục sự cố

Tập đoàn viễn thông đa quốc gia UltraCom hiện sở hữu một hệ thống truyền tin gồm N trung tâm truyền nhận dữ liệu (gọi tắt là trung tâm) nằm rải rác khắp địa cầu (các trung tâm này được đánh số từ 1 đến N) và M vệ tinh (gọi tắt là vệ tinh) cũng được phân bố đều khắp trên bầu trời quanh địa cầu (các vệ tinh này được đánh số từ 1 đến M).
Mỗi trung tâm i đều có thể thiết lập kết nối trực tiếp (để khai thác) với mỗi vệ tinh j với chi phí xác định Cij nào đó.

Hai trung tâm được xem là thông băng với nhau nếu chúng cùng được kết nối với một vệ tinh hoặc chúng cùng thông băng với một số trung tâm khác. Toàn hệ thống của UltraCom đương nhiên vốn là thông băng hoàn toàn, tức là bất kỳ hai trung tâm nào cũng đều thông băng với nhau.

Một sự cố bí ẩn vừa diễn ra trong thời gian gần đây đã khiến một số kết nối bị hư hỏng hoàn toàn và hệ thống của UltraCom bị rơi vào tình trạng không thông băng hoàn toàn được, đặt ra nhiệm vụ cấp bách cho UltraCom phải khẩn trương khắc phục hậu quả này.

Sau sự cố, bộ phận phụ trách kỹ thuật của UltraCom đã tiến hành khảo sát toàn hệ thống và nhận thấy rằng:

1. Mỗi trung tâm đều vẫn còn đang kết nối bình thường với một số các vệ tinh đồng thời mỗi vệ tinh đều còn đang được kết nối bởi một số trung tâm nào đó.

2. Một số kết nối vừa bị hỏng sẽ không thuộc diện xem xét khắc phục nữa, do chi phí quá lớn.

3. Hoàn toàn có phương án khả thi để khắc phục hệ thống thông băng hoàn toàn.

để tiết kiệm chi phí tại thời điểm nhạy cảm của nền kinh tế toàn cầu, ban lãnh đạo tập đoàn quyết định sẽ chỉ thiết lập lại một số kết nối đã bị hư hỏng sao cho tổng chi phí khắc phục là nhỏ nhất có thể.

Yêu cầu: Xác lập phương án cụ thể và tổng chi phí nhỏ nhất để UltraCom khắc phục sự cố

Dữ liệu vào: Cho trong file văn bản REPAIR.INP, gồm:

• Dòng đầu ghi tuần tự 2 số nguyên dương N, M (2 ≤ M, N ≤ 1000)

• Dòng thứ i trong N dòng tiếp theo ghi M số nguyên Ci1, …, CiM (-1 ≤ Cij ≤ 10000; i = 1, …, N; j = 1, 2,…, M) với ý nghĩa: Cij là chi phí để kết nối trung tâm i với vệ tinh j cùng sự lưu ý đặc biệt: Cij = 0 nếu trung tâm i vẫn đang kết nối bình thường được với vệ tinh j, Cij = -1 nếu bỏ qua việc tái lập sự kết nối giữa trung tâm i với vệ tinh j (do chi phí quá lớn).

• Tất cảc các số nguyên trên cùng dòng đều cách nhau bởi khoảng trống. Dữ liệu luôn đảm bảo tính đúng đắn để có lời giải, tức là luôn có phương án để UltraCom khắc phục sự cố.

Kết quả: Ghi ra file văn bản REPAIR.OUT các thông tin sau:

• Dòng đầu ghi một số nguyên, là tổng chi phí nhỏ nhất tìm được. Thông tin này chiếm 50% số điểm của test.

• Dòng thứ 2 ghi số nguyên dương K, với K là số kết nối cần khắc phục. Thông tin này chiếm 25% số điểm của test.

• K dòng tiếp theo, mỗi dòng ghi hai số nguyên c, s (cách nhau bởi khoảng trống) cho biết cần tái lập kết nối giữa trung tâm c với vệ tinh s. Nếu có nhiều kết quả (phương án), chỉ cần chỉ ra một trong chúng. Thông tin trên K dòng này chiểm 25% số điểm của test.

VD1:

REPAIR.INP

4 3

0 -1 5

0 4 4

-1 0 -1

1 2 0

REPAIR.OUT

3

2

4 1

4 2

REPAIR.INP

4 4

0 -1 5 3

-1 4 5 -1

-1 0 -1 0

6 7 0 -1

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với N, M ≤ 200.

• Giới hạn thời gian cho mỗi test: 01 giây.