## Editorial for Những ngôi nhà

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var m,n:byte;
dem:integer;
b:array[1..100] of byte;
a:array[0..25] of byte;

procedure rf;
var i,j:byte;
begin
j:=0;
for i:=1 to n do
begin
j:=j+a[i];
end;
a[0]:=m-j;
m:=n+a[0];
if m=n then
for i:=1 to n do b[i]:=i
else
begin
b[1]:=1;
for i:=2 to 1+a[0] do b[i]:=0;
for j:=2 to n do b[a[0]+j]:=j;
end;
end;

procedure writef;
var i,j:byte;
begin
for i:=1 to m do
if b[i]=0 then write(0,' ')
else for j:=1 to a[b[i]] do write(b[i],' ');
writeln;
end;

procedure swap(var a,b:byte);
var t:byte;
begin
t:=a; a:=b; b:=t;
end;

procedure pr;
var i,j,l,r:byte;
begin
dem:=0;
repeat
inc(dem);
writef;
if dem=1000 then halt;
i:=m-1;
while (i>0) and (b[i]>=b[i+1]) do dec(i);
if i>0 then
begin
j:=m;
while (j>i) and (b[j]<=b[i]) do dec(j);
swap(b[i],b[j]);
l:=i+1; r:=m;
while l<r do
begin
swap(b[l],b[r]);
dec(r);
inc(l);
end;
end;
until i=0;
end;

begin
rf;
pr;
end.


program houses;
uses    math;
const   maxN=22;
maxL=111;
fi='';
var     a:array[0..maxn] of longint;
f:array[1..maxL] of longint;
check:array[1..maxN] of boolean;
l,n,res,sum:longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
begin
inc(sum,a[i]);
end;
a[0]:=1;
close(inp);
end;

procedure output;
var     i,j:longint;
begin
i:=1;
while i<=l do
begin
if f[i]<>0 then
for j:=1 to a[f[i]] do
write(f[i],' ')
else
write(f[i],' ');
inc(i,a[f[i]]);
end;
writeln;
end;

procedure back(i,s:longint);
var     j:longint;
begin
if i>l then
begin
inc(res);
if res>1000 then halt;
output;
exit;
end;
if (i>1) and ((sum-s)<=(l-i)) then
begin
f[i]:=0;
back(i+1,s);
end;
for j:=1 to n do
if not check[j] then
begin
check[j]:=true;
f[i]:=j;
back(i+a[j],s+a[j]);
check[j]:=false;
end;
end;

begin
input;
back(1,0);
end.


#### Code mẫu của RR

//Written by Nguyen Thanh Trung
{\$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=100;
var
f1,f2:text;
sum,n,l:longint;
kq,len:array[1..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i:longint;
begin
for i:=1 to n do
begin
sum+=len[i];
end;
kq[1]:=1; sum:=l-sum; for i:=sum+1 downto 2 do kq[i]:=0;
for i:=2 to n do
kq[sum+i]:=i;
end;
procedure print;
var
i,j:longint;
begin
for i:=1 to n do
if kq[i]=0 then write(f2,'0 ')
else for j:=1 to len[kq[i]] do write(f2,kq[i],' ');
writeln(f2);
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
i,j,mid:longint;
begin
i:=l; j:=r; mid:=kq[l+random(r-l+1)];
repeat
while kq[i]<mid do inc(i);
while kq[j]>mid do dec(j);
if i<=j then
begin
swap(kq[i],kq[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure solve;
var
count,i,vt,j,luu:longint;
found:boolean;
begin
n+=sum; count:=0;
repeat
print; inc(count); if count=1000 then break;
found:=false;
for vt:=n-1 downto 1 do
if kq[vt]<kq[vt+1] then break;
if kq[vt]<kq[vt+1] then
begin
found:=true;
luu:=vt+1;
for j:=vt+2 to n do
if (kq[j]>kq[vt]) and (kq[j]<kq[luu]) then luu:=j;
swap(kq[vt],kq[luu]);
if vt<n then sort(vt+1,n);
end;
end;
begin
openF;
inp;
solve;
closeF;
end.


#### Code mẫu của hieult

#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
long l,n,spt,dem=0,a[21],d[101],m[101],i,j,tong;
void thunhan()
{
long i,j;
dem++;
for(i=1;i<=spt;i++)
{
if(m[i]==0)
printf("0 ");
else
for(j=1;j<=a[m[i]];j++)
printf("%ld ",m[i]);
}
printf("\n");
if(dem==1000)
exit(0);
}
void tim(long i,long x)
{
long j,k;
for(j=0;j<=n;j++)
{
if(j==0)
{
if(i!=1)
{
if(spt-i>=x)
{
m[i]=0;
if(i==spt)
thunhan();
else tim(i+1,x);
}
}
}
else if(d[j]==0)
{
m[i]=j;
d[j]=1;
x=x-1;
if(i==spt)
thunhan();
else tim(i+1,x);
x=x+1;
d[j]=0;
}
}
}
main()
{
scanf("%ld %ld",&l,&n);
for(i=1;i<=n;i++)
{
scanf("%ld",&a[i]);
tong =tong+a[i];
}
spt=l-tong+n;
tim(1,n);
//getch();
}


#### Code mẫu của ll931110

Program HOUSES;
Const
input  = '';
output = '';
Var
a: array[1..20] of integer;
b: array[1..100] of integer;
d: array[0..20] of boolean;
l,n,request,count,s: integer;
fi,fo: text;

Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);

Assign(fo, output);
Rewrite(fo);
End;

Procedure init;
Var
i: integer;
Begin
For i:= 1 to n do read(fi, a[i]);

count:= 1;
request:= n;

s:= 0;
For i:= 1 to n do s:= s + a[i];
Fillchar(d, sizeof(d), true);
End;

Procedure printresult;
Var
i: integer;
Begin
If b[1] <> 0 then
Begin
For i:= 1 to l do write(fo, b[i], ' ');
Writeln(fo);
inc(count);
End;
End;

Procedure attempt(i: integer);
Var
j,k,t: integer;
Begin
If count = 1001 then exit;
If i = 1 then t:= 1 else t:= 0;

For k:= t to n do
if d[k] then
If k = 0 then
Begin
b[i]:= 0;
If (i = l) and (request = 0) then printresult
else if i <= l - s then attempt(i + 1);
End
else
Begin
If i + a[k] - 1 <= l then
Begin
For j:= i to i + a[k] - 1 do b[j]:= k;
s:= s - a[k];
dec(request);
d[k]:= false;

if (i + a[k] - 1 = l) and (request = 0) then printresult
else if i + a[k] - 1 <= l - s then attempt(i + a[k]);

For j:= i to i + a[k] - 1 do b[j]:= 0;
s:= s + a[k];
inc(request);
d[k]:= true;
End;
End;
End;

Procedure closefile;
Begin
Close(fo);
Close(fi);
End;

Begin
openfile;
init;
attempt(1);
closefile;
End.


#### Code mẫu của skyvn97

#include<stdio.h>
#define MAXN   30
#define MAXL   200
int l,n,sx,sum;
int a[MAXN];
int x[MAXL];
int cnt;
bool blt[MAXL];
bool p;
void print(void)
{
int i;
cnt++;
if (!p) p=true; else printf("\n");
for (i=1;i<l;i=i+1) printf("%d ",x[i]);
printf("%d",x[l]);
}
void btrk(int t)
{
if (cnt>=1000) return;
int i,j;
for (i=0;i<=n;i=i+1)
{
x[t]=i;
if (x[1]!=0)
{
if (i==0)
{
if ((sum-sx)<=(l-t))
{
if (t==l) print();
else btrk(t+1);
}
}
else
if (blt[i])
{
blt[i]=false;
for (j=t+1;j<a[i]+t;j=j+1) x[j]=i;
sx=sx+a[i];
if (a[i]+t-1==l) print();
else btrk(a[i]+t);
blt[i]=true;
sx=sx-a[i];
}
}
}
}
int main(void)
{
cnt=0;
int i;
p=false;
scanf("%d",&l);
scanf("%d",&n);
sum=0;
sx=0;
for (i=1;i<=n;i=i+1)
{
scanf("%d",&a[i]);
sum=sum+a[i];
blt[i]=true;
}
btrk(1);
}