VO 15 Bài 5 - Chăn Lợn

Xem dạng PDF

Gửi bài giải

Điểm: 1,78 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VO 2015
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân John có một cậu con trai là Benjamin, đang học ở thành phố, là một học sinh rất giỏi toán. Năm nay cậu cũng đã hơn ~18~ tuổi và nông dân John đã già nên ông quyết định để lại trang trại cho cậu con trai. Benjamin mặc dù rất tiếc việc học hành dở dang ở trên thành phố nhưng vì ba già yếu nên cậu phải về quê để giúp cha minh. Nhưng Benjamin đã nghĩ cho dù về nông thôn làm việc nhưng cậu vẫn sẽ cố gắng theo đuổi đam mê của mình.

Khi về phụ giúp cha cậu, cậu thấy rằng việc chăm sóc những con bò quá mệt nhọc nên cậu đã quyết định bán hết toàn bộ số bò và mua ~N~ con heo về và rắc rồi bắt đầu từ đây. Mỗi con khi mua được dán một mã số - ~\textbf{ index[i] }~ là số cho biết chủ cũ của con heo thứ ~i~. Các con heo khi được nuôi cùng nhau thì sẽ có một số con bị bắt nạt bởi một số con khác và những con bị bắt nạt sẽ bị ức chế sinh trưởng. Vấn đề trên đúng là một vấn đề nan giải. Sau một thời gian quan sát cậu thấy mỗi con sẽ có một chỉ số sức mạnh và được tính bằng công thức như sau:

~Strength[i] = index[i] \text{ } AND \text{ } M~. (Với M là một số nguyên)

Hơn nữa cậu còn biết rằng nếu như ~Strength[i] \text{ } OR \text{ } Strength[j] = Strength[i]~ thì con heo thứ ~\textbf{ j }~ sẽ bị con heo thứ ~\textbf{ i }~ bắt nạt.

~AND~ và ~OR~ là phép tính thông thường trong PASCAL/C++. Bạn nào chưa biết thì có thể đọc trong hai đường dẫn dưới đây.

Giải pháp của Benjamin là sẽ phân các con heo vào các chuồng khác nhau sao cho trong mỗi chuồng thì không có con heo nào bị bắt nạt. Benjamin đã dùng khá nhiều tiền để mua lại đàn heo nên chi phí xây dựng chuồng phải càng ít càng tốt. Điều đó có nghĩa là số lượng chuồng phải là ít nhất có thể.

Input

Đối với subtask 1subtask 2 :

  • Input gồm một dòng chứa ~2~ số ~N~ và ~M~.

Đối với subtask 3subtask 4 :

  • Input gồm ~N+1~ dòng.
  • Dòng đầu chứa ~2~ số ~N~ và ~M~.
  • Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa số ~index[i]~ là mã số của con heo thứ ~i~.

Output

Dòng đầu chứa số ~K~ là số lượng chuồng ít nhất có thể.

Giới hạn

Subtask 1 ( ~16\%~ số test ) :

  • ~10^{9} \leq N \leq 10^{18};~ ~M = 2^{60} - 1~
  • ~index[i] = i~, với ~i = 1..N~.

Subtask 2 ( ~20\%~ số test ) :

  • ~10^{9} \leq N, M \leq 10^{18}~ .
  • ~N~ có dạng: ~N = 2^{x} - 1~.
  • ~index[i] = i~, với ~i = 1..N~.

Subtask 3 ( ~24\%~ số test ) :

  • ~1 \leq N \leq 5000;~ ~1 \leq M < 2^{31}~ .
  • ~0 \leq index[i] < 2^{31}~.

Subtask 4 ( ~40\%~ số test ) :

  • ~1 \leq N \leq 100000;~ ~M = 1037536599~.
  • ~0 \leq index[i] < 2^{31}~ .

Sample Input

8 3
0
1
2
3
4
5
6
7

Sample Output

6

Bình luận

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


Không có bình luận tại thời điểm này.