[C10_VP_25] Trò chơi

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Nhân dịp Tết thiếu nhi ngày 1-6, Bờm và Cuội nhận được ~2N~ đồ chơi, các đồ chơi có giá trị đôi một khác nhau, thuộc phạm vi từ ~1~ đến ~2N~. Đồ chơi của Bờm có giá trị ~a_1, a_2, a_3, \ldots, a_N~, đồ chơi của Cuội có các giá trị còn lại. Hai bạn cùng rủ nhau chơi một trò chơi như sau:

  • Hai người lần lượt chọn một đồ chơi cho từng ván, mỗi người chỉ dùng mỗi đồ chơi đúng một lần.
  • Người có đồ chơi có giá trị lớn hơn thì thắng ván đó.

Yêu cầu

Hỏi trong trường hợp may mắn nhất, Bờm có thể thắng bao nhiêu ván?

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

  • Dòng đầu tiên: Ghi một số nguyên ~N~ ~(1 \le N \le 50000)~.
  • ~N~ dòng tiếp theo: Mỗi dòng ghi ~1~ số nguyên ~a_i~ ~(1 \le a_i \le 2N)~, là giá trị các đồ chơi Bờm có.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số ván nhiều nhất mà Bờm có thể thắng.

Ràng buộc dữ liệu

  • Subtask 1 (50% điểm): ~N \le 100~.
  • Subtask 2 (50% điểm): ~N \le 50000~.

Ví dụ

Ví dụ 1
INPUT
3
1
5
4
OUTPUT
2

Giải thích:

  • Ván ~1~: Bờm chọn đồ chơi có giá trị ~1~, Cuội chọn đồ chơi có giá trị ~6~ (Cuội thắng).
  • Ván ~2~: Bờm chọn đồ chơi có giá trị ~5~, Cuội chọn đồ chơi có giá trị ~2~ (Bờm thắng).
  • Ván ~3~: Bờm chọn đồ chơi có giá trị ~4~, Cuội chọn đồ chơi có giá trị ~3~ (Bờm thắng).

Bình luận

Hãy đọc nội quy trước khi bình luận.