Rà soát trùng số áo cầu thủ và ước lượng năng lực xử lí

Danh sách đăng ký của một giải bóng đá phong trào ghi số áo của n cầu thủ. Nếu hai cầu thủ có cùng số áo, trọng tài dễ ghi nhầm biên bản trận đấu, nên ban tổ chức cần một thuật toán rà soát để đếm số cặp cầu thủ (i, j) với i < j mà số áo trùng nhau.

Em hãy tự thiết kế thuật toán dùng hai vòng lặp lồng nhau để giải quyết bài toán trên (không dùng hàm dựng sẵn để đếm phần tử trùng), sau đó tận dụng chính đặc điểm độ phức tạp O(n2) của thuật toán này để ước lượng: với thời gian xử lí cho phép T giây và tốc độ máy tính S phép tính cơ bản/giây, kích thước danh sách cầu thủ tối đa k mà thuật toán còn xử lí kịp là giá trị lớn nhất thoả k*k <= T*S (hãy tự tìm k bằng một vòng lặp tăng dần, không dùng hàm tính căn bậc hai có sẵn).

Định dạng vào: Dòng 1 là số nguyên n; dòng 2 gồm n số nguyên là số áo các cầu thủ; dòng 3 gồm hai số nguyên T và S cách nhau bởi khoảng trắng.

Định dạng ra: In ra hai dòng: dòng 1 là số cặp cầu thủ trùng số áo trong danh sách đã cho; dòng 2 là giá trị k lớn nhất mà thuật toán O(n²) này có thể xử lí trong T giây với tốc độ S phép/giây.