HOUSES - Những ngôi nhà

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Một công ty đầu tư xây dựng một khu nhà gồm L căn nhà nằm cạnh nhau trên một con đường. Có N người muốn mua nhà ở khu nhà này, biết rằng người thứ i muốn mua a i căn nhà và mỗi người đều muốn mua những căn nhà nằm cạnh nhau. Do số căn nhà cần mua có thể nhỏ hơn tổng số căn nhà (L) nên sẽ có một số căn nhà chưa được bán. Để đảm bảo mỹ quan của khu nhà, công ty sẽ luôn luôn bán căn nhà đầu tiên (theo thứ tự từ trái sang phải).

Biết yêu cầu của những người mua, một cách bán những căn nhà của công ty có thể được biểu diễn bằng 1 dãy gồm L số. Trong đó số thứ i bằng 0 nếu căn nhà thứ i chưa được bán và bằng k nếu căn nhà thứ i được bán cho người thứ k.

Ví dụ: khi L=4, N=2, a 1 = 2, a 2 =1, dãy “2 0 1 1” thể hiện một cách bán những căn nhà của công ty: căn nhà đầu tiên bán cho người thứ 2, căn nhà thứ 3 và thứ 4 bán cho người đầu tiên và căn nhà thứ 2 được để lại.

Yêu cầu: Hãy giúp công ty liệt kê các cách bán những căn nhà. Các cách bán căn nhà được liệt kê theo thứ tự từ điển của dãy số biểu diễn. Nếu số cách bán căn nhà lớn hơn 1000, chỉ cần liệt kê 1000 cách đầu tiên. (Biết rằng dãy a có thứ tự từ điển đứng trước dãy b nếu và chỉ nếu tồn tại chỉ số j, sao cho a i = b i với mọi i < j và a j < b j ).

Dữ liệu

  • Dòng đầu tiên: chứa 2 số nguyên L, N.
  • Dòng thứ 2 chứa N số nguyên, tương ứng là các giá trị a 1 , a 2 , …, a n .

Hạn chế

  • 1 ≤ L ≤ 100.
  • 1 ≤ N ≤ 20.
  • a 1 + a 2 + ... + a N ≤ L.

Kết quả

Gồm nhiều dòng, mỗi dòng tương ứng với dãy số biểu diễn một cách bán những căn nhà của công ty, 2 số liên tiếp của dãy số được cách nhau bởi một khoảng trắng. Các dãy số được liệt kê theo thứ tự từ điển.

Ví dụ 

Dữ liệu
4 2
2 1

Kết quả
1 1 0 2
1 1 2 0
2 0 1 1
2 1 1 0

  • Người up: paulmcvn
  • Nguồn bài: VNOI Online Informatics Olympiad '09Day 1