{ Petr Hruska }
program vlak;
{ vstup:
prvni radek s vahami vagonu
druhy radek s poctem vagonu na jednom oblouku a nosnosti oblouku
}
const max_vagonu = 100;
type p_vagon = ^t_vagon;
t_vagon = record
pred, next : p_vagon;
vaha : integer;
end;
var vagony : t_vagon;
n : integer; { pocet platnych prvku vagony }
k : integer; { pocet vagonu na jednom oblouku }
s : integer; { nosnost oblouku }
p : integer; { pocet vagonu ve vlaku }
a : integer; { soucet poslednich k vagonu }
vahy : array[-max_vagonu+1 .. max_vagonu] of integer; { vahy vagonu }
procedure zapis;
var f : text;
i : integer;
begin
assign(f, 'vystup.txt');
rewrite(f);
for i := 1 to n do write(f, vahy[i], ' ');
for i := 1 to n do write(vahy[i], ' ');
writeln;
close(f);
end;
procedure zapis_nelze;
var f : text;
begin
assign(f, 'vystup.txt');
rewrite(f);
writeln(f, 'NELZE');
close(f);
end;
{ po skonceni je seznam vagony identicky }
function lze : boolean;
var i : integer;
v : p_vagon;
r : boolean;
begin
lze := true;
if p = n then { nasli jsme }
begin
zapis;
exit;
end;
{ a je soucet poslednich k vagonu }
a := a - vahy[p - k + 1]; { odeceteme vahu vagonu o k pozic zpet }
p := p + 1; { hloubka rakurze }
v := vagony.next;
while v <> @vagony do
begin
if v^.vaha + a <= s then { pokud ma vlak senci projet ... }
begin
{ vyjmout }
v^.pred^.next := v^.next;
v^.next^.pred := v^.pred;
a := a + v^.vaha;
vahy[p] := v^.vaha; { ulozime pro pripadne odcitani }
r := lze; { rekurzivni volani }
a := a - v^.vaha; { obnovime hodnotu a }
{ vratit }
v^.pred^.next := v;
v^.next^.pred := v;
if r then exit;
end;
v := v^.next;
end;
p := p - 1;
a := a + vahy[p - k + 1];
lze := false;
end;
{ klasicke trideni vyberem maxima O(n^2) }
procedure sort;
var v, max, start : p_vagon;
i, pom : integer;
begin
start := @vagony;
for i := n - 1 downto 1 do
begin
start := start^.next;
max := start;
v := start^.next;
while v <> @vagony do
begin
if v^.vaha > max^.vaha then max := v;
v := v^.next;
end;
{ prohodime start a max }
pom := start^.vaha;
start^.vaha := max^.vaha;
max^.vaha := pom;
end;
end;
procedure init;
var i : integer;
v : p_vagon;
f : text;
begin
assign(f, 'vstup.txt');
reset(f);
n := 0;
vagony.pred := @vagony;
vagony.next := @vagony;
{ nacteni do spojoveho seznamu }
while not eoln(f) do
begin
new(v);
read(f, v^.vaha);
v^.next := @vagony;
v^.pred := vagony.pred;
vagony.pred^.next := v;
vagony.pred := v;
n := n + 1;
end;
readln(f);
readln(f, k, s);
close(f);
sort;
for i := -k + 1 to k - 1 do vahy[i] := 0;
p := 0;
a := 0;
end;
begin
init;
if not lze then zapis_nelze;
end.