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.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

HOUSES - Những ngôi nhà

English Vietnamese

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 ai 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, a1 = 2, a2=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 ai = bi với mọi i < j và aj < bj).

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ị a1, a2, …, an.

Hạn chế

  • 1 ≤ L ≤ 100.
  • 1 ≤ N ≤ 20.
  • a1 + a2 + ... + aN ≤ 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
Submit solution!
Được gửi lên bởi:Jimmy
Ngày:2008-07-29
Thời gian chạy:0.200s
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:VNOI Online Informatics Olympiad '09
Day 1
hide comments
Xem lại 1  2 Xem tiếp >
2022-07-26 21:42:48
1 hit ac
2021-05-27 18:01:16
Tham khảo: https://vnspoj.github.io/problems/HOUSES
2017-11-17 04:49:24
ai = 0 duoc ko a
2017-07-27 12:06:07
Code AC: http://ideone.com/eQ3Nte
2017-02-06 14:15:00
sai lỗi easy
2016-11-03 15:44:29
Backtrack với chú ý là mỗi ngôi nhà sẽ có 2 khả năng là bán hoặc không bán. Nếu bán thì sẽ bán các nhà liên tiếp. Nếu không bán thì phải thỏa mãn bán đủ cho N người.
http://thuattoan.phamvanlam.com/spoj-com-thuat-toan-bai-houses-nhung-ngoi-nha/
2016-09-30 10:29:05
Trâu cũng AC =)))
2016-09-30 10:24:36
Please be careful, leave short comments only. Don't spam here.
2016-09-30 10:24:14
Don't post any source code here.
2016-09-05 09:06:38
Mình quay lui bình thường vẫn AC đây đâu cần đặt cận đâu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.