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

NKA1 - A1

Chính phủ lập ra một hội đồng để sửa chữa đường cao tốc chính A1 của đất nước. Đường cao tốc có dạng một đường thẳng, bao gồm các cột cây số liên tiếp cách đều nhau. Hai cột cây số liên tiếp cách nhau 1km. Cột cây số thứ nhất cách điểm đầu tiên của đường cao tốc 1km. Có N vị trí cột cây số cần sửa chữa trên đường cao tốc. Mỗi cột cây số được xác định bởi một số nguyên cho biết khoảng cách đối với điểm đầu tiên của đường cao tốc (tính theo km). Bắt đầu từ một cột cây số nào đó, đường cao tốc được chia thành các đoạn dài bằng nhau, mỗi đoạn chứa đúng M cột cây số liên tiếp. Một đội sửa đường sẽ được gửi đến mỗi đoạn có chứa một (hoặc nhiều) vị trí cần sửa chữa. Thông thường, số vị trí cần sửa chữa lớn hơn nhiều so với số đội sửa đường nên tốt nhất cần chia đường cao tốc thành các đoạn độ dài bằng nhau sao cho số đoạn chứa vị trí cần sửa chữa là ít nhất.

Biết rằng trong M cột cây số đầu tiên, không có vị trí nào cần sửa chữa. Đoạn đầu tiên phải được bắt đầu trong M cột cây số đầu tiên.

Hỏi cần huy động ít nhất bao nhiêu đội sửa đường để sửa chữa được tất cả vị trí cần thiết trên đường cao tốc A1? Xác định các vị trí mà đoạn đầu tiên có thể bắt đầu.

Dữ liệu

  • Dòng đầu tiên bao gồm 2 số nguyên M và N cách nhau bởi khoảng trắng (1 ≤ M, N ≤ 100000).
  • Dòng thứ 2 bao gồm N số nguyên cách nhau bởi khoảng trắng mô tả những vị trí cần sửa chữa. N số nguyên tạo thành một dãy tăng chặt, mỗi số không vượt quá 2000000000.

Kết qủa

  • Dòng đầu tiên chứa số đội sửa đường ít nhất cần huy động.
  • Dòng thứ hai chứa tất cả các vị trí mà đoạn đầu tiên có thể bắt đầu. Các số cách nhau bởi khoảng trắng và phải tạo thành một dãy tăng chặt.

Ví dụ

Dữ liệu:
3 5
4 5 7 8 9

Kết qủa
2 
1

Dữ liệu:
4 3
7 14 15

Kết qủa
2
1 2 4

Dữ liệu:
2 10
3 4 7 8 12 13 14 15 20 21

Kết qủa
7
1 2

Được gửi lên bởi:Duc
Ngày:2007-12-27
Thời gian chạy:4.460s
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatian OI 2003

hide comments
2015-07-25 09:43:30 [Nghien] Le Long
Bài này chặt nhị phân thôi
2015-07-25 09:39:41 there's no salvation for me...
bài này phải neo ms AC
2014-09-27 04:24:52 Toàn
Bài từ năm 2007 đến 2014 mới có người commnent thế này!!! Rip
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.