IOI 2009 - Ngày 1

Một giải đấu bắn cung được tổ chức theo các quy tắc sau. Có \(N\) bia được xếp thành một hàng và đánh số từ \(1\) đến \(N\) theo vị trí trên hàng: bia ngoài cùng bên trái mang số \(1\), còn bia ngoài cùng bên phải mang số \(N\). Có \(2N\) cung thủ tham gia. Tại mọi thời điểm trong giải đấu, mỗi bia có hai cung thủ. Mỗi vòng đấu diễn ra như sau: hai cung thủ ở mỗi bia thi đấu với nhau để xác định người thắng và người thua, sau đó tất cả cung thủ được sắp xếp lại theo quy tắc:

• Những người thắng ở các bia từ \(2\) đến \(N\) chuyển sang bia bên trái, tức lần lượt là các bia từ \(1\) đến \(N-1\).
• Những người thua ở các bia từ \(2\) đến \(N\), cùng với người thắng ở bia \(1\), vẫn ở nguyên bia của mình.
• Người thua ở bia \(1\) chuyển sang bia \(N\).

Giải đấu kéo dài \(R\) vòng, với số vòng ít nhất bằng số cung thủ, tức \(R \ge 2N\).

Bạn là cung thủ duy nhất đến giải đấu đúng giờ. Tất cả \(2N-1\) cung thủ còn lại đều đã đến sớm và đang đứng thành một hàng. Bây giờ bạn phải chen vào một vị trí nào đó trong hàng của họ. Bạn biết rằng sau khi bạn vào hàng, hai cung thủ ngoài cùng bên trái sẽ bắt đầu giải đấu ở bia \(1\), hai người tiếp theo ở bia \(2\), và cứ như vậy cho đến hai cung thủ ngoài cùng bên phải bắt đầu ở bia \(N\).

Cả \(2N\) cung thủ trong giải đấu, kể cả bạn, đều được xếp hạng theo kỹ năng; số thứ hạng càng nhỏ thì kỹ năng càng tốt. Không có hai cung thủ nào cùng thứ hạng. Khi hai cung thủ thi đấu với nhau, người có số thứ hạng nhỏ hơn luôn thắng.

Biết kỹ năng của từng đối thủ, bạn muốn chọn vị trí chen vào hàng sao cho khi giải đấu kết thúc, bạn ở một bia có số nhỏ nhất có thể. Nếu có nhiều cách đạt được điều đó, bạn muốn chọn cách bắt đầu ở bia có số lớn nhất có thể.

Nhiệm vụ

Cho thứ hạng của tất cả cung thủ, bao gồm cả bạn, cùng thứ tự các đối thủ đang đứng trong hàng, hãy viết chương trình xác định bia mà bạn nên bắt đầu giải đấu để đạt được các mục tiêu trên.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(R\), cách nhau bởi một dấu cách.
• \(2N\) dòng tiếp theo cho biết thứ hạng của các cung thủ. Dòng đầu tiên trong số này chứa thứ hạng của bạn. Các dòng còn lại chứa thứ hạng của các cung thủ khác, mỗi người một dòng, theo thứ tự họ đang đứng từ trái sang phải. Mỗi dòng chứa một số nguyên từ \(1\) đến \(2N\), trong đó hạng \(1\) là tốt nhất và hạng \(2N\) là kém nhất. Không có hai cung thủ nào cùng thứ hạng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên từ \(1\) đến \(N\): số của bia mà bạn sẽ bắt đầu giải đấu.

Ràng buộc

• \(1 \le N \le 200\,000\): số bia, cũng bằng một nửa số cung thủ.
• \(2N \le R \le 1\,000\,000\,000\): số vòng đấu.
• \(1 \le S_k \le 2N\): thứ hạng của cung thủ \(k\).

Phân nhóm

Bài có tổng cộng \(100\) điểm. Trong một số test có tổng cộng \(60\) điểm, \(N\) không vượt quá \(5000\). Trong số các test này, một số test có tổng cộng \(20\) điểm thỏa mãn \(N\) không vượt quá \(200\).

Ví dụ

4 8
7
4
2
6
5
8
1
3

3

4 9
2
1
5
8
3
4
7
6

2

Nguồn

IOI 2009.

Bạn cần thuê công nhân cho một dự án xây dựng. Có \(N\) ứng viên xin việc, được đánh số từ \(1\) đến \(N\). Mỗi ứng viên \(k\) yêu cầu được trả ít nhất \(S_k\) đô la nếu được thuê. Ngoài ra, ứng viên \(k\) có trình độ chuyên môn \(Q_k\). Quy định của ngành xây dựng yêu cầu tiền công của những người được thuê phải tỉ lệ với trình độ chuyên môn của họ. Ví dụ, nếu bạn thuê hai công nhân \(A\) và \(B\) với \(Q_A = 3Q_B\), bạn phải trả cho \(A\) đúng gấp ba lần số tiền trả cho \(B\). Bạn được phép trả số tiền không nguyên, kể cả những số tiền không thể biểu diễn bằng số thập phân hữu hạn, chẳng hạn một phần ba hoặc một phần sáu đô la.

Bạn có \(W\) đô la và muốn thuê càng nhiều công nhân càng tốt. Bạn được quyết định thuê ai và trả cho họ bao nhiêu, nhưng phải đáp ứng yêu cầu tiền công tối thiểu của những người được chọn, tuân thủ quy định của ngành và không vượt quá ngân sách \(W\) đô la.

Do tính chất của dự án, trình độ chuyên môn hoàn toàn không quan trọng, nên bạn chỉ quan tâm đến việc tối đa hóa số công nhân mà không xét đến trình độ của họ. Tuy nhiên, nếu có nhiều cách đạt được số công nhân lớn nhất, bạn muốn chọn cách có tổng số tiền phải trả nhỏ nhất. Nếu vẫn có nhiều cách như vậy, bạn có thể chọn bất kỳ cách nào.

Nhiệm vụ

Cho yêu cầu tiền công tối thiểu và trình độ chuyên môn của từng ứng viên, cùng số tiền bạn có, hãy viết chương trình xác định những ứng viên cần thuê. Bạn phải thuê nhiều người nhất có thể và trả tổng số tiền ít nhất có thể cho số người đó, đồng thời tuân thủ quy định của ngành nêu trên.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(W\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả các ứng viên, mỗi ứng viên một dòng. Dòng thứ \(k\) trong số này mô tả ứng viên số \(k\), chứa hai số nguyên \(S_k\) và \(Q_k\), cách nhau bởi một dấu cách.

Dữ liệu ra

Chương trình ghi ra đầu ra chuẩn:

• Dòng đầu chứa một số nguyên \(H\), là số công nhân bạn thuê.
• \(H\) dòng tiếp theo liệt kê số hiệu của các ứng viên bạn chọn thuê, mỗi người một dòng, theo thứ tự bất kỳ. Các số hiệu phải đôi một khác nhau và nằm trong khoảng từ \(1\) đến \(N\).

Ràng buộc

• \(1 \le N \le 500\,000\): số ứng viên.
• \(1 \le S_k \le 20\,000\): tiền công tối thiểu mà ứng viên \(k\) yêu cầu.
• \(1 \le Q_k \le 20\,000\): trình độ chuyên môn của ứng viên \(k\).
• \(1 \le W \le 10\,000\,000\,000\): số tiền bạn có.

Lưu ý quan trọng: Giá trị lớn nhất của \(W\) không thể lưu bằng \(32\) bit. Để lưu \(W\) trong một biến, bạn phải dùng kiểu dữ liệu \(64\) bit, chẳng hạn long long trong C/C++ hoặc int64 trong Pascal.

Phân nhóm

Bài có tổng cộng \(100\) điểm. Với mỗi test, bạn nhận toàn bộ điểm của test đó nếu tập ứng viên được chọn đạt được tất cả các mục tiêu và thỏa mãn mọi ràng buộc. Nếu kết quả có dòng đầu đúng, tức giá trị \(H\) đúng, nhưng không đáp ứng đầy đủ mô tả ở trên, bạn nhận \(50\%\) số điểm của test đó. Quy tắc này vẫn áp dụng ngay cả khi kết quả không đúng định dạng, miễn là dòng đầu đúng.

Trong một số test có tổng cộng \(50\) điểm, \(N\) không vượt quá \(5000\).

Ví dụ

4 100
5 1000
10 100
8 10
20 1

2
2
3

3 4
1 2
1 3
1 3

3
1
2
3

3 40
10 1
10 2
10 3

2
2
3

Nguồn

IOI 2009.

Kỳ thi Olympic Tin học Plovdiv (POI) được tổ chức tại địa phương theo những quy tắc khác thường sau. Có \(N\) thí sinh và \(T\) bài toán. Mỗi bài chỉ được chấm bằng một test, vì vậy với mỗi bài và mỗi thí sinh chỉ có hai khả năng: thí sinh giải được bài đó hoặc không giải được. Không có điểm thành phần cho bất kỳ bài nào.

Số điểm của mỗi bài được xác định sau khi kỳ thi kết thúc và bằng số thí sinh không giải được bài đó. Điểm của mỗi thí sinh bằng tổng số điểm của những bài mà thí sinh ấy giải được.

Philip đã tham gia kỳ thi, nhưng các quy tắc tính điểm phức tạp khiến cậu bối rối. Giờ đây, cậu đang nhìn vào kết quả mà không xác định được vị trí của mình trên bảng xếp hạng cuối cùng. Hãy giúp Philip bằng cách viết chương trình tính điểm và thứ hạng của cậu.

Trước kỳ thi, các thí sinh được gán các số hiệu đôi một khác nhau từ \(1\) đến \(N\). Số hiệu của Philip là \(P\). Bảng xếp hạng cuối cùng liệt kê các thí sinh theo thứ tự điểm giảm dần. Trong số các thí sinh bằng điểm, người giải được nhiều bài hơn được xếp trước người giải được ít bài hơn. Nếu vẫn bằng nhau theo tiêu chí này, các thí sinh có cùng kết quả được xếp theo thứ tự số hiệu tăng dần.

Nhiệm vụ

Cho biết mỗi thí sinh giải được những bài nào, hãy viết chương trình xác định điểm của Philip và thứ hạng của cậu trên bảng xếp hạng cuối cùng.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N\), \(T\) và \(P\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả những bài mà từng thí sinh giải được. Dòng thứ \(k\) trong số này mô tả thí sinh có số hiệu \(k\) và chứa \(T\) số nguyên cách nhau bởi các dấu cách. Số đầu tiên cho biết thí sinh \(k\) có giải được bài thứ nhất hay không, số thứ hai cho biết điều tương tự với bài thứ hai, và cứ như vậy. Mỗi số chỉ có thể là \(0\) hoặc \(1\): \(1\) nghĩa là thí sinh \(k\) giải được bài tương ứng, còn \(0\) nghĩa là không giải được.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa hai số nguyên cách nhau bởi một dấu cách. Số thứ nhất là điểm mà Philip đạt được trong kỳ thi POI. Số thứ hai là thứ hạng của Philip trên bảng xếp hạng cuối cùng. Thứ hạng là một số nguyên từ \(1\) đến \(N\), trong đó \(1\) chỉ thí sinh đứng đầu bảng, tức một thí sinh có điểm cao nhất, còn \(N\) chỉ thí sinh đứng cuối bảng, tức một thí sinh có điểm thấp nhất.

Ràng buộc

• \(1 \le N \le 2000\): số thí sinh.
• \(1 \le T \le 2000\): số bài toán.
• \(1 \le P \le N\): số hiệu của Philip.

Phân nhóm

Bài có tổng cộng \(100\) điểm. Trong một số test có tổng cộng \(35\) điểm, không có thí sinh nào khác có cùng điểm với Philip.

Ví dụ

5 3 2
0 0 1
1 1 0
1 0 0
1 1 0
1 1 0

3 2

Nguồn

IOI 2009.

Bonny, nghệ nhân làm sô-cô-la nổi tiếng của Plovdiv, cần cắt một thanh sô-cô-la có nho khô. Thanh sô-cô-la là một khối hình chữ nhật gồm các ô vuông giống hệt nhau, có các cạnh song song với cạnh của thanh sô-cô-la. Các ô được xếp thành \(N\) hàng và \(M\) cột, tổng cộng \(NM\) ô. Mỗi ô có ít nhất một quả nho khô; không có quả nho khô nào nằm giữa hai ô hoặc vắt qua ranh giới giữa các ô.

Ban đầu, thanh sô-cô-la là một khối liền. Bonny cần cắt nó thành những khối ngày càng nhỏ hơn, cho đến khi tách được toàn bộ \(NM\) ô riêng lẻ. Vì rất bận, Bonny cần người phụ việc Peter ranh mãnh giúp cắt. Peter chỉ thực hiện những đường cắt thẳng xuyên suốt khối từ cạnh này sang cạnh kia và muốn được trả công cho từng nhát cắt. Bonny không có sẵn tiền, nhưng còn rất nhiều nho khô, nên đề nghị trả công cho Peter bằng nho khô. Peter đồng ý, nhưng đặt ra điều kiện: mỗi khi cắt một khối sô-cô-la thành hai khối nhỏ hơn, anh ta phải được trả số quả nho khô bằng tổng số quả nho khô trên khối được đưa cho anh ta cắt.

Bonny muốn trả cho Peter ít nhất có thể. Cô biết số quả nho khô trên từng ô trong \(NM\) ô. Cô có thể chọn thứ tự đưa các khối còn lại cho Peter, đồng thời chỉ định hướng cắt (ngang hoặc dọc) và vị trí chính xác của từng đường cắt. Hãy giúp Bonny quyết định cách cắt thanh sô-cô-la thành các ô riêng lẻ để trả cho Peter ít nho khô nhất.

Nhiệm vụ

Cho số quả nho khô trên từng ô, hãy viết chương trình xác định số quả nho khô ít nhất mà Bonny phải trả cho Peter.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả số quả nho khô trên mỗi ô của thanh sô-cô-la. Dòng thứ \(k\) trong số này mô tả hàng thứ \(k\), gồm \(M\) số nguyên cách nhau bởi một dấu cách, theo thứ tự các ô từ trái sang phải. Số nguyên thứ \(p\) trên dòng thứ \(k\) trong số \(N\) dòng này là số quả nho khô trên ô ở hàng \(k\), cột \(p\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số quả nho khô ít nhất mà Bonny phải trả cho Peter.

Ràng buộc

• \(1 \le N, M \le 50\): số ô trên mỗi chiều của thanh sô-cô-la.
• \(1 \le R_{k,p} \le 1000\): số quả nho khô trên ô ở hàng \(k\), cột \(p\).

Phân nhóm

Bài có tổng cộng \(100\) điểm. Trong một số test có tổng cộng \(25\) điểm, cả \(N\) và \(M\) đều không vượt quá \(7\).

Ví dụ

2 3
2 7 5
1 9 5

77

    Không có cách cắt nào khác tách được thanh sô-cô-la thành $6$ ô riêng lẻ với chi phí nhỏ hơn.

Nguồn

IOI 2009.