[VOI Training] SEQ19845

Xem PDF

Nộp bài


Điểm: 20 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Con số \(19845\) có gợi cho bạn điều gì không? Khi học lịch sử Việt Nam, Vinh biết rằng ngày \(19-8-1945\) là ngày Tổng khởi nghĩa, ngày nhân dân cả nước ta nhất tề đứng lên làm cuộc Cách mạng Tháng Tám vĩ đại. Con số này đã gợi ý cho cuom1999 khảo sát dãy số \(\textbf{SEQ19845}\) sau đây: Dãy số nguyên không âm \(a_1\), \(a_2\),..., \(a_n\) được gọi là dãy \(\textbf{SEQ19845}\) nếu không tồn tại hai chỉ số \(i\) và \(j\) \((1 \leq i,j \leq n)\) mà \(a_i-a_j\) hoặc là bằng \(19\) hoặc là bằng \(8\) hoặc là bằng \(4\) hoặc là bằng \(5\).

Ví dụ:

Dãy số nguyên \(1\), \(3\), \(4\), \(17\) là dãy \(\textbf{SEQ19845}\).

cuom1999 quan tâm tới bài toán sau đây: Cho dãy số nguyên không âm \(b_1\), \(b_2\),..., \(b_m\), hãy tìm cách loại bỏ một số ít nhất phần tử của dãy để được dãy còn lại là \(\textbf{SEQ19845}\).

Yêu cầu

Hãy giúp cuom1999 giải quyết bài toán đặt ra


Dữ liệu

Dòng đầu chứa số nguyên dương \(m\);

Dòng thứ hai chứa \(m\) số nguyên không âm \(b_1\), \(b_2\),..., \(b_m\) \(\left(b_i \leq 10^9\right)\).


Kết quả

Ghi ra số nguyên \(k\) là số phần tử bị loại bỏ. Ghi số \(0\) nếu dãy đã cho là \(\textbf{SEQ19845}\).


Ví dụ

Input
6
7 3 5 1 9 21
Output
3

Ràng buộc:

  • Có \(25\%\) số test ứng với \(25\%\) số điểm của bài có \(m \leq 20\).
  • Có \(75\%\) số test còn lại ứng với \(75\%\) số điểm của bài có \(m \leq 2000\).

Ý tưởng: VOI 2016

Upgrade: Lê Phước Định