Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Đề thi IOI2009 - Bài 3: THI OLYMPIC VÙNG PROVDIV (POI)
18/09/2009

Cuộc thi Olympic Tin học địa phương của vùng Plovdiv (POI) được tiến hành theo quy tắc đặc biệt như sau. Có N thí sinh và T bài toán. Mỗi bài được chấm bằng một test duy nhất. Vì vậy, với mỗi bài toán và với mỗi thí sinh chỉ có hai khả năng: hoặc là thí sinh giải được bài toán đó hoặc không giải được. Người ta không cho điểm từng phân với mỗi bài.


Điểm của mỗi bài được xác định sau cuộc thi và bằng số lượng thí sinh không giải được bài này. Điểm của mỗi thí sinh bằng tổng điểm của các bài mà thí sinh đã giải được.

Philip tham gia cuộc thi này, nhưng cảm thấy khá lung túng với luật chấm điểm rắc rối và bây giờ, đối diện với bảng kết quả, anh không thể xác định được vị trí của mình trong bảng xếp hạng. Hãy viết chương trình giúp Philip tính điểm và vị trí của mình trong bảng xếp hạng.

Trước cuộc thi mỗi thí sinh được nhận một mã số (ID) phân biệt có giá trị trong phạm vi từ 1 đến N. Mã số của Philip là P. Bảng kết quả cuối cùng của cuộc thi là danh sách các thí sinh theo thứ tự giảm dần của điểm mà thí sinh đó nhận được. Trong trường hợp bằng điểm nhau, thí sinh nào giải được nhiều bài hơn sẽ được xếp trên những người giải được ít bài hơn. Với các thí sinh giống nhau theo tiêu chí này thì trên bảng kết quả tên của họ sẽ được đưa ra theo thứ tự tăng dần của mã số ID.

BÀI TOÁN

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

RÀNG BUỘC

1 ≤ N ≤ 2000 Số lượng thí sinh

1 ≤ T ≤ 2000. Số lượng bài toán.

1 ≤ P ≤ N. Mã số ID của Philip.

INPUT

Chương trình của bạn phải đọc các dữ liệu sau từ standard input:

Dòng đầu tiên chứa các 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ả các bài toán mà thí sinh giải được. Dòng thứ k trong các dòng này mô tả các bài toán mà thí sinh có mã số ID là k giải được. Mỗi dòng như thế chứa T số nguyên, cách nhau bởi một dấu cách. Số thứ nhất cho biết thí sinh k có giải được bài toán thứ nhất hay không, số thứ hai – có ý nghĩa tương tự như vậy với bài toán thứ hai, … Mỗi số trong T số này có giá trị là 0 hoặc 1, trong đó 1 cho biết thí sinh k giải được bài toán tương ứng với 0 – thí sinh không làm được bài đó.

OUTPUT

Chương trình của bạn phải ghi ra standard output 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 xác định điểm của Philip trong kỳ thi POI. Số thứ hai là thứ hạng của Philip trong bảng kết quả. Thứ hạng là một số nguyên trong phạm vi từ 1 đến N, trong đó 1 là thứ hạng thí sinh đứng đầu trong danh sách (tức là thí sinh có điểm cao nhất) và N là thứ hạng thí sinh đứng cuối danh sách kết quả (tức là thí sinh có điểm thấp nhất).

CÁCH CHẤM ĐIỂM

Có một nhóm các test với tổng số điểm là 35, trong đó không có thí sinh nào có điểm giống Philip.

VÍ DỤ

Bài thứ nhất chỉ có một thí sinh không giải được vì vậy nó sẽ có điểm là 1. Bài thứ 2 có 2 thí sinh không giải được vì vậy nó được cho 2 điểm Bài thứ 3 có 4 thí sinh không giải được vì vậy điểm của bài này là 4. Như vậy thí sinh thứ nhất được 4 điểm, các thí sinh thứ hai (Philip), thứ tư và thứ năm đều có điểm là 3; và thí sinh thứ 3 có điểm là 1. Các thí sinh 2, 4, 5 hòa nhau theo tiêu chỉ phân loại thứ nhất (số bài giải được) và được sắp xếp theo tiêu chí phân loại thứ hai (mã phân loại nhỏ hơn). Philip có mã nhỏ nhất trong số này, vì vậy hạng của Philip là 2. Philip chỉ đứng sau thí sinh mã số 1.
URL của bài viết này::http://www.vnschool.net/modules.php?name=News&file=article&sid=3521
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn