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