(stre.*)

Cho \(n\) que diêm, que thứ \(i\) có chiều dài là một số nguyên \(a_{i}\).

Hãy tìm số lượng que diêm tối thiểu cần thêm vào \(n\) que diêm đã cho để xếp được các hình chữ nhật từ các quen đã cho sao cho mỗi que diêm chỉ thuộc một hình chữ nhật và mỗi cạnh của hình chữ nhật chỉ được tạo thành từ 1 que diêm.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq 10^{6})\)

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}(1 \leq a_{i} \leq 1000)\)

Kết quả:

+ Một số nguyên duy nhất cho biết kết quả của bài toán.

Ví dụ:

Solution:

Gọi \(d\lbrack x\rbrack(1 \leq x \leq 10000\) là số lượng que diêm có độ dài \(x\) trong \(n\) que diêm đã cho. Có thể sử dụng đếm phân phối để tạo mảng \(d\).

Gọi kết quả ban đầu là \(ans = 0\)

Ta thấy rằng:

+ Nếu \(d\lbrack x\rbrack \geq 4\) thì có thể lấy mỗi 4 que diêm độ dài \(x\) để tạo thành 1 hình chữ nhật, do vậy số que diêm độ dài \(x\) còn lại là \(d\lbrack x\rbrack\% 4\)

+ Nếu \(d\lbrack x\rbrack = 3\) thì ta cần thêm 1 quen diêm độ dài đúng bằng \(x\) để tạo thành 1 hình chữ nhật. Do vậy \(ans + = (d\lbrack x\rbrack = = 3)\); với \(x = 1\ldots 10^{3}\)

+ Nếu ta có 2 số \(x\) và \(y\ (x
eq y)\) sao cho \(d\lbrack x\rbrack = d\lbrack y\rbrack = 2\) thì có thể dùng hai que độ dài \(x\) và 2 que độ dài \(y\) để xếp thành một hình chữ nhật. Do vậy ta đếm \(mod2\) là số lượng \(d\lbrack x\rbrack = = 2\), nếu \(mod2\) lẻ thì còn thừa hai que diêm độ dài \(x\) chưa được ghép.

+ Đếm \(mod1\) là số lượng \(d\lbrack x\rbrack = 1\).

Nếu \(mod1 = 0\) thì cần thêm 2 que diêm để ghép với 2 que diêm ở \(mod2\):

\[ans + = 2\]

Nếu \(mod1 > 0\) và \(mod2 = 1\) thì cần thêm 1 que diêm có để ghép:

\[ans + + ;mod - - ;\]

Đến đây ta chỉ còn các que diêm độ dài \(x\) có số lượng 1:

+ Cứ 2 que diêm có độ dài khác nhau thì ta cần thêm 2 que diêm để tạo thành 1 hình chữ nhật: \(ans + = (mod1/2*2)\) và \(mod1\% = 2\)

+ Nếu \(mod1 = = 1\) thì cần thêm 3 que diêm: \(ans + = 3\)