Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11XU - Bộ sưu tập đồng xu

alex có một bộ sưu tập đồng xu rất đẹp. yenthanh132 cũng thích những đồng xu nhưng do lười nên không có sưu tầm xu và kết quả là tới giờ vẫn không có đồng xu nào cả. Thấy yenthanh132 có vẻ thích bộ sưu tập đồng xu của mình nên một hôm alex quyết định sẽ tặng cho yenthanh132 một số đồng xu trong bộ sưu tập. Nhưng vốn biết tính tham lam của yenthanh132, nếu cho anh ta tùy ý lựa chọn thì thế nào anh ta cũng sẽ lấy hết tất cả đồng xu trong bộ sưu tập của alex. Thế là alex đã nghĩ ra một cách để yenthanh132 không thể lấy hết được các đồng xu của mình…

Trong bộ sưu tập đồng xu của alex có tất cả M loại khác nhau (được đánh số từ 1 đến M). Đầu tiên alex chọn ra N đồng xu trong bộ sưu tập đồng xu của mình (không phải chọn ra tất cả). Biết rằng N  là một số nguyên dương và luôn chia hết cho 4. Các đồng xu được đánh số từ 1 đến N, sau đó anh ta lấy ra N/2 bao thư, đánh số từ 1 đến N/2, mỗi bao thư bỏ 2 đồng xu liên tiếp vào. Nói cách khác bao thư thứ nhất chứa đồng xu 1, 2; bao thư thứ 2 chứa đồng xu 3,4;… bao thư thứ N/2 chứa đồng xu (n-1) và n. Cuối cùng alex để n bao thư này lên bàn và bảo với yenthanh132 được phép chọn một số bao thư với điều kiện sau:

  • Với mỗi cặp bao thư được đánh số k*2-1 và k*2 (k từ 1 đến N/4) thì yenthanh132 hoặc không chọn cả 2 hoặc chỉ có thể chọn một trong 2 bao thư.
  • Với mỗi bao thư mà yenthanh132 được chọn, thì yenthanh132 sẽ được phải lấy cả 2 đồng xu trong bao thơ đó.
  • Sau khi yenthanh132 đã lấy xong các đồng xu thì nếu như: trong số các bao thư mà yenthanh132 lấy được, alex có thể chọn ra 1 tập các bao thư (khác rỗng) sao cho với mỗi loại trong M loại đồng xu khác nhau trong bộ sưu tập của anh ta thì tổng số lượng đồng xu loại đó trong tập các bao thư alex chọn sẽ: hoặc bằng 0 hoặc là một số chẵn. Thì yenthanh132 phải trả lại toàn bộ những đồng xu đó cho alex (tất nhiên trong quá trình chọn các bao thư chứa đồng xu yenthanh132 sẽ phải chọn như thế nào đó để tránh gặp kết quả như vậy).

Vốn tính tham lam nên mặt dù alex cho điều kiện ngặc nghèo như vậy nhưng yenthanh132 vẫn cố gắng để làm sao có thể lấy được càng nhiều đồng xu càng tốt từ alex.

Yêu cầu: Hãy giúp yenthanh132 tính xem anh ta có thể lấy được nhiều nhất bao nhiêu đồng xu từ bộ sưu tập các đồng xu của alex. Nếu bạn giúp được, có thể anh ta sẽ chia cho bạn vài đồng đấy :)

Dữ liệu vào

  • Dòng đầu tiên chứa số 2 số nguyên N, M lần lượt là số lượng đồng xu alex chọn ra để bỏ vào bao thư và số loại đồng xu khác nhau.
  • Dòng thứ 2 chứa N số nguyên a[i] (1 ≤ a[i] ≤ M; i từ 1 đến n). Là loại của đồng xu thứ i. Lưu ý có thể có những loại đồng xu mà không xuất hiện trong N đồng xu mà alex chọn ra, bởi vì đó chỉ là một phần trong bộ sưu tập của anh ta mà thôi.

Dữ liệu ra

  • Một số nguyên duy nhất là số lượng đồng xu tối đa mà yenthanh132 có thể lấy được từ alex.  

Giới hạn

  • 10% số test có 4 ≤ n ≤ 100.
  • Trong tất cả các test có 4 ≤ n ≤ 2000.
  • 1 ≤ M ≤ 10000.

Ví dụ

Input 2:
4 3
1 2 3 3
(Giải thích: Có 4 đồng xu, 2 bao thư, bao đầu tiên chứa đồng xu 1,2; bao thứ 2 chứa đồng xu 3,4).

Output 1:
2
(Giải thích: Chỉ có thể chọn bao thư 1. Nếu chọn bao thư 2 thì khi alex chọn bao thư này sẽ có tập 2 đồng xu loại 3)


Input 2:
16 10
1 2 1 6 6 2 1 6 2 3 1 2 2 6 3 1

Output 2:

6
(Giải thích: Chọn bao thư 1, 3 và 5)

(Trong lúc thi sẽ chấm trước 2 test (bao gồm test ví dụ)).


Được gửi lên bởi:Hacker7
Ngày:2012-12-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:Lê Yên Thanh

hide comments
2016-11-03 14:50:47
Code pascal:
http://shink.in/Ew9PJ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.