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.|

VOPIG - Chăn Lợn

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ố - 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] AND 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] OR Strength[j] = Strength[i] thì con heo thứ  j sẽ bị con heo thứ 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 ) :

  • 109 ≤ N ≤ 1018; M = 260-1

  • index[i] = i, với i = 1..N.

Subtask 2 ( 20% số test ) :

  • 109 ≤ N, M ≤ 1018.

  • N có dạng: N = 2- 1.

  • index[i] = i, với i = 1..N.

Subtask 3 ( 24% số test ) :

  • 1 ≤ N ≤ 5000; 1 ≤ M < 231.

  • 0 ≤ index[i] < 231.

Subtask 4 ( 40% số test ) :

  • 1 ≤ N ≤ 100,000; M = 1037536599.

  • 0 ≤ index[i] < 231.

Thời gian chạy: 1s cho mỗi test. Riêng test đề bài có giới hạn thời gian chạy là 0.5s.

Chú ý:

  • Trong thời gian thi, bài của bạn chỉ được chấm với test đề bài.
  • Nếu bài của bạn chạy đúng trên máy mình, nhưng sai khi nộp lên SPOJ, bạn có thể kiểm tra ở ideone. Chú ý khi submit lên ideone, để chế độ Secret để người khác không đọc được code của bạn.

Example:

Input:
8 3
0
1
2
3
4
5
6
7

Output:
6

Được gửi lên bởi:VOJ Team
Ngày:2014-12-21
Thời gian chạy:0.5s-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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VO 2015

hide comments
2018-04-13 05:25:11
vbc

Last edit: 2018-04-13 05:25:32
2018-04-13 05:24:50
bài AC: http://bfy.tw/HciP
2018-04-13 05:24:16
http://bfy.tw/HciM
2018-04-13 04:28:11
bài này easy mà

Last edit: 2018-04-13 05:22:55
2018-04-13 04:25:44
trâu cũng AC
2017-07-28 05:33:13
Hướng dẫn: http://shink.in/rjsbv
2016-12-05 16:56:21
bài trẻ con,16 đấm cx AC
2016-12-05 10:02:41
ai co code gui minh vs 9 sub ko qua sub 2
2015-12-30 13:42:18 ChienTran
v~ subtask
2015-11-07 05:29:21
oh shit
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.