JOI 2026 - Ultimate Dango Maker

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1500 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

JOI-kun là một người làm bánh dango. Cậu có \(A_i\) chiếc bánh dango màu \(i\), với \(1 \le i \le N\). Một xiên dango dùng đúng ba chiếc bánh. Nếu màu của ba chiếc là \(c_1,c_2,c_3\), mọi hiệu tuyệt đối giữa hai màu phải không vượt quá \(1\).

Mỗi chiếc bánh chỉ được dùng cho nhiều nhất một xiên. Hãy tìm số xiên dango lớn nhất có thể tạo.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In số xiên dango lớn nhất có thể tạo.

Ràng buộc

  • \(1 \le N \le 200000\).
  • \(0 \le A_i \le 10^9\).
  • Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

  1. \(6\) điểm: \(N=1\).
  2. \(9\) điểm: \(N \le 2\).
  3. \(10\) điểm: mọi \(A_i\) chia hết cho \(3\).
  4. \(17\) điểm: mọi \(A_i=2\).
  5. \(21\) điểm: mọi \(A_i \le 3\).
  6. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3
3 1 2
Output 
2
Giải thích

Có thể làm một xiên bằng ba chiếc bánh màu \(1\), và một xiên bằng một chiếc bánh màu \(2\) cùng hai chiếc bánh màu \(3\). Xiên thứ nhất hợp lệ vì \(|1-1|=0\le1\); xiên thứ hai hợp lệ vì \(|2-3|\le1\) và \(|3-3|\le1\). Không thể làm hơn hai xiên, nên in \(2\).

Ví dụ này thỏa mãn các nhóm \(5\), \(6\).

Ví dụ 2

Input 
1
99
Output 
33
Giải thích

Có thể làm \(33\) xiên, mỗi xiên gồm ba chiếc bánh màu \(1\). Không thể làm nhiều hơn, nên in \(33\).

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(6\).

Ví dụ 3

Input 
2
5 6
Output 
3
Giải thích

Có thể làm một xiên gồm ba chiếc bánh màu \(1\), một xiên gồm hai chiếc bánh màu \(1\) và một chiếc bánh màu \(2\), cùng một xiên gồm ba chiếc bánh màu \(2\). Tổng cộng có ba xiên và không thể làm nhiều hơn, nên in \(3\).

Ví dụ này thỏa mãn các nhóm \(2\), \(6\).

Ví dụ 4

Input 
6
0 2 2 3 1 2
Output 
3
Giải thích

Ví dụ này thỏa mãn các nhóm \(5\), \(6\).

Ví dụ 5

Input 
1
0
Output 
0
Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(5\), \(6\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Ultimate Dango Maker.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: