Nội dung Bài tập
- Mã:
- GOM_DUA
- Tên:
- Gom Đũa
- Dạ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 tạo bởi:
- 4901104079
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
Quảng cáo
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 .
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 .
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...