Bài 2. Xếp hạng
Có học sinh, đánh số thứ tự 1, 2, … , , tham gia một cuộc thi lập trình. Các thí sinh được chấm
bài ngay trong thời gian thi nên mỗi bạn đều biết điểm thi của mình. Ban tổ chức cho biết không có
hai thí sinh nào có cùng điểm thi. Tuy nhiên, bảng xếp hạng cuối cùng lại chưa được công bố.
Rất mong muốn biết được thứ hạng để xác định “màu huy chương”, một số thí sinh đã so sánh điểm
thi với nhau. Có tất cả so sánh như vậy, kết quả mỗi so sánh là một cặp số nguyên ( ; ) được
hiểu là thí sinh có điểm cao hơn thí sinh , đồng nghĩa sẽ có thứ hạng kết quả cao hơn .
Cho biết thông tin về các lần so sánh, hãy xác định xem có bao nhiêu thí sinh đã có thể biết chính
xác thứ hạng của mình.
Dữ liệu (brank.inp)
• Dòng1: hai số nguyên , (1 ≤ ≤ 100; 1 ≤ ≤ 4500)
• Dòng2 … + 1: mỗi dòng là thông tin về một so sánh gồm hai số nguyên , (1 ≤
, ≤ ; ≠ ) chỉ thí sinh sẽ có thứ hạng cao hơn thí sinh . Các so sánh không mâu
thuẫn.
1/2
Kết quả (brank.out)
• Dòng 1: số nguyên là số lượng thí sinh có thể xác định chính xác thứ hạng kết quả.
Ví dụ
brank.inp brank.out giải thích
5 5
2 Hai thí sinh có thể biết chính xác thứ hạng là thí
4 3
sinh #2 và thí sinh #5
4 2
3 2
1 2
2 5
Bạn đang xem bài 2. - Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học lớp 12 năm học 2012-2013 – Sở Giáo dục và Đào tạo Vĩnh Phúc (Đề chính thức)