123Code...

Nội dung Bài tập

Mã:: GOM_DUA

Tên:: Gom Đũa

Dạng thi:: oi

Thang điểm:: 10 điểm

Giới hạn thời gian:: 1 giây

Giới hạn bộ nhớ:: 256 MB

Nguồn bài tập:: VNOI Contest

Được tạo bởi:: 4901104079

: Share

Có thanh tre có độ dài nguyên dương. Bạn được phép thực hiện thao tác sau không hoặc nhiều lần: Chọn một thanh tre bất kì, bẻ thanh tre đó thành hai thanh tre nhỏ hơn có độ dài nguyên dương, sao cho hai thanh tre mới có độ dài không bằng nhau. Sau khi thực hiện thao tác, bạn sử dụng những thanh tre để gom thành các đôi đũa. Một đôi đũa được tạo thành từ hai thanh tre có độ dài bằng nhau. Hãy tìm số lượng đôi đũa lớn nhất có thể tạo được sau khi thực hiện thao tác trên. Input Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ( 1 ≤ t ≤ 10000). Mô tả của mỗi test case như sau. Dòng đầu tiên chứa số nguyên ( 1 ≤ n ≤ 2*10^5) — số lượng thanh tre. Dòng thứ hai chứa n số nguyên a1, a2, … , an ( 1 ≤ ai ≤ 10^9 ) — độ dài của các thanh tre. Output Với mỗi test case, in ra một số nguyên duy nhất là số lượng đôi đũa lớn nhất tạo được Ví dụ 1: Input Output 2 7 1 1 1 2 2 2 2 4 2 3 3 2 3 3 Ví dụ 2: Input Output 2 1 4 10 3 1 4 1 5 9 2 6 5 3 1 15 Giải thích: Trong test case đầu tiên ở ví dụ đầu tiên, ta có 3 thanh tre độ dài 1 , và 4 thanh tre độ dài 2 . Ta không thể bẻ thanh tre nào thành hai thanh tre nhỏ hơn mà có độ dài khác nhau. Từ các thanh tre này, ta có thể tạo ra 1 đôi đũa từ hai thanh tre độ dài 1 , và thêm 2 đôi đũa nữa từ các thanh tre độ dài . Như vậy số lượng đôi đũa có thể tạo được là 1 + 2 = 3 . Lưu ý ta còn lại một thanh tre độ dài 1 không ghép với thanh tre nào cả. Trong test case thứ hai ở ví dụ đầu tiên, ta có thể bẻ thanh tre có độ dài 3 thành hai thanh tre nhỏ hơn có độ dài và . Như vậy ta sẽ có 1 đôi đũa từ thanh tre độ dài 1 , và 2 đôi đũa từ thanh tre độ dài 2. Như vậy ta cũng vẫn thu được 1 + 2 = 3 đôi đũa. Trong test case đầu tiên ở ví dụ thứ hai, ta có duy nhất một thanh tre độ dài 4 .Ban đầu ta có thể bẻ thanh tre này thành thanh tre độ dài 1 và 3 . Tiếp đó ta có thể bẻ thanh tre độ dài 3 thành thanh tre độ dài 1 và 2 . Từ đây ta có thể tạo ra một đôi đũa từ hai thanh tre độ dài 1 .
Quảng cáo