MAXSQ - Maximum Square
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: MrThaodaica

Mr. Thảo quyết định làm một mái nhà bằng gỗ cho ngôi nhà. Anh ấy có n tấm ván hình chữ nhật được đánh số từ 1 tới n. Tấm ván thứ i có kích thước là ai  x  1 (nghĩa là, chiều rộng là 1 và chiều dài là ai).

Bấy giờ, Mr.Thảo muốn làm mái nhà bằng hình vuông. Anh ấy sẽ chọn một vài tấm ván và đặt chúng cạnh nhau theo thứ tự. Sau đó anh ấy sẽ dán tất cả các tấm ván này bằng cạnh đứng của chúng. Cuối cùng, anh ta sẽ cắt ra hình vuông từ hình dạng kết quả theo cách sao cho các cạnh của hình vuông là ngang và dọc.

Ví dụ: Mr. Thảo có các tấm ván có chiều dài lần lượt là 4, 3, 1, 4, 5. Anh ta có thể chọn các tấm ván có chiều dài là 4,3,5. Sau đó anh ta có thể cắt ra hình vuộng 3 x 3 (đây là mức tối đa có thể). Lưu ý rằng đây không phải là cách duy nhất anh ta có thể có được hình vuông 3 x 3.

Độ dài cạnh hình vuông lớn nhất Mr. Thảo có thể cắt là?

INPUT:

               -Dòng đầu tiên chứa số nguyên k (1 <= k <=10) là số test cases input.

               -Trong mỗi test case, dòng đầu tiên chứa một số nguyên n (1 <= n <= 1000) – số tấm ván. Dòng tiếp theo chứa n số nguyên a1, a2, .. , an (1<=ai <= n) là độ dài của mỗi tấm ván.

OUTPUT

               -Mỗi dòng test cases, in ra số nguyên là chiều dài lớn nhất có thể của hình vuông.

Ví dụ

  • input
    4
    5
    4 3 1 4 5
    4
    4 4 4 4
    3
    1 1 1
    5
    5 5 1 1 5
    output
    3
    4
    1
    3
Back to Top