| type |
| int = longint; |
| function min(a, b: int): int; |
| begin |
| if (a >= b) then |
| result := b |
| else |
| result := a; |
| end; |
| var |
| i, j, n, hei: int; |
| h, l, who: array[1..2000] of int; |
| was: array[1..2000] of boolean; |
| a: array[0..2000, 0..2000] of int; |
| took: array[0..2000, 0..2000] of boolean; |
| besthl, x: int; |
| toth: int = 0; |
| begin |
| reset(input, 'advent.in'); |
| rewrite(output, 'advent.out'); |
| read(n); |
| for i := 1 to n do |
| begin |
| read(h[i], l[i]); |
| inc(toth, h[i]); |
| end; |
| read(hei); |
| fillchar(a, sizeof(a), $77); |
| a[0, 0] := 0; |
| for i := 1 to n do |
| begin |
| besthl := $77777777; |
| for j := 1 to n do |
| if not was[j] and (h[j] + l[j] < besthl) then |
| begin |
| besthl := h[j] + l[j]; |
| x := j; |
| end; |
| was[x] := true; |
| who[i] := x; |
| for j := 0 to i - 1 do |
| begin |
| if (toth - a[i - 1, j] + l[x] >= hei) then |
| begin |
| a[i, j + 1] := a[i - 1, j] + h[x]; |
| took[i, j + 1] := true; |
| end; |
| if (a[i - 1, j] < a[i, j]) then |
| begin |
| a[i, j] := a[i - 1, j]; |
| took[i, j] := false; |
| end; |
| end; |
| end; |
| j := n; |
| while (a[n, j] = $77777777) do |
| dec(j); |
| writeln(j); |
| for i := n downto 1 do |
| begin |
| if (took[i, j]) then |
| begin |
| write(who[i], ' '); |
| dec(j); |
| end; |
| end; |
| writeln; |
| end. |
| {$apptype console} |
| {$q+,r+,n-,o+} |
| const cinfile = 'advent.in'; |
| coutfile = 'advent.out'; |
| const nmax = 2011; |
| inf = maxlongint shr 1; |
| type int = longint; |
| var h, l, a, b, way : array[0..nmax] of int; |
| n, sum, c, height : int; |
| procedure init; |
| var i : int; |
| begin |
| read(n); |
| for i:=1 to n do read(h[i], l[i]); |
| read(height); |
| end; |
| procedure qsort(p, q : int); |
| var pp, qq, x, t : int; |
| begin |
| pp:=p - 1; |
| qq:=q + 1; |
| x:=h[b[(p + q) shr 1]] + l[b[(p + q) shr 1]]; |
| while true do begin |
| repeat dec(qq); until (h[b[qq]] + l[b[qq]] <= x); |
| repeat inc(pp); until (h[b[pp]] + l[b[pp]] >= x); |
| if (pp >= qq) then break |
| else begin |
| t:=b[qq]; |
| b[qq]:=b[pp]; |
| b[pp]:=t; |
| end; |
| end; |
| if (p < qq) then qsort(p, qq); |
| if (qq + 1 < q) then qsort(qq + 1, q); |
| end; |
| procedure sort; |
| var i : int; |
| begin |
| for i:=1 to n do b[i]:=i; |
| if (n > 1) then qsort(1, n); |
| end; |
| procedure solve; |
| var i, j : int; |
| begin |
| for i:=1 to n do a[i]:=inf; |
| sum:=0; |
| for i:=1 to n do inc(sum, h[i]); |
| a[0]:=0; |
| way[0]:=0; |
| c:=0; |
| for j:=1 to n do begin |
| for i:=c downto 0 do |
| if (sum - a[i] + l[b[j]] >= height) then begin |
| if (a[i + 1] > a[i] + h[b[j]]) then begin |
| a[i + 1]:=a[i] + h[b[j]]; |
| way[i + 1]:=b[j]; |
| end; |
| end; |
| if (a[c + 1] <> inf) then inc(c); |
| end; |
| end; |
| procedure writeanswer; |
| procedure go(x : int); |
| begin |
| if (x = 0) then exit; |
| go(x - 1); |
| write(way[x]); |
| if (x < c) then write(' '); |
| end; |
| begin |
| writeln(c); |
| go(c); |
| end; |
| begin |
| assign(input, cinfile); reset(input); |
| assign(output, coutfile); rewrite(output); |
| init; |
| sort; |
| solve; |
| writeanswer; |
| close(input); close(output); |
| end. |
| uses |
| sysutils; |
| const |
| max_n = 100000; |
| max_m = 100000; |
| max_t = 24 * 60 - 1; |
| type |
| tarr = array [1..max_n] of longint; |
| var |
| n, m: longint; |
| c, b: array [1..max_n] of longint; |
| acity, atime, dcity, dtime: tarr; |
| ans: longint; |
| function d(c: char): longint; |
| begin |
| d := ord(c) - ord('0'); |
| end; |
| function readTime(): longint; |
| var |
| d1, d2, d3, d4: char; |
| begin |
| if seekeof then; |
| read(d1, d2); |
| read(d3); |
| read(d3, d4); |
| readTime := (d(d1) * 10 + d(d2)) * 60 + d(d3) * 10 + d(d4); |
| end; |
| var |
| t: array [0..max_t] of longint; |
| tcity, ttime: tarr; |
| procedure sort(var city, time: tarr); |
| var |
| i: longint; |
| begin |
| fillchar(t, sizeof(t), 0); |
| for i := 1 to m do begin |
| inc(t[time[i]]); |
| end; |
| for i := 1 to max_t do begin |
| t[i] := t[i] + t[i - 1]; |
| end; |
| tcity := city; |
| ttime := time; |
| for i := 1 to m do begin |
| time[t[ttime[i]]] := ttime[i]; |
| city[t[ttime[i]]] := tcity[i]; |
| dec(t[ttime[i]]); |
| end; |
| end; |
| var |
| i: longint; |
| pa, pd: longint; |
| f: boolean; |
| begin |
| assign(input, 'buses.in'); reset(input); |
| assign(output, 'buses.out'); rewrite(output); |
| read(n, m); |
| ans := 0; |
| for i := 1 to m do begin |
| read(dcity[i]); |
| dtime[i] := readTime(); |
| dec(b[dcity[i]]); |
| read(acity[i]); |
| atime[i] := readTime(); |
| inc(b[acity[i]]); |
| if (dtime[i] > atime[i]) then begin |
| inc(ans); |
| end; |
| end; |
| sort(dcity, dtime); |
| sort(acity, atime); |
| for i := 1 to m do begin |
| end; |
| pa := 1; |
| pd := 1; |
| for i := 0 to max_t do begin |
| while (pa <= m) and (atime[pa] = i) do begin |
| inc(c[acity[pa]]); |
| inc(pa); |
| end; |
| while (pd <= m) and (dtime[pd] = i) do begin |
| if (c[dcity[pd]] > 0) then begin |
| dec(c[dcity[pd]]); |
| end else begin |
| inc(ans); |
| end; |
| inc(pd); |
| end; |
| end; |
| f := true; |
| for i := 1 to n do begin |
| f := f and (b[i] = 0); |
| end; |
| if f then begin |
| writeln(ans); |
| end else begin |
| writeln(-1); |
| end; |
| close(input); |
| close(output); |
| end. |
| {$apptype console} |
| {$q+,r+,n-,o+} |
| { |
| sort + dijkstra |
| O(N*logN*lmax + N*N*k) |
| } |
| const cinfile = 'fur.in'; |
| coutfile = 'fur.out'; |
| const nmax = 1011; |
| lmax = 2011; |
| inf = maxlongint shr 1; |
| type int = longint; |
| var s : array[1..nmax, 1..lmax] of char; |
| len : array[1..nmax] of int; |
| p : array[1..nmax] of int; |
| common : array[1..nmax, 1..nmax] of int; |
| ak : array[1..23] of int; |
| d : array[1..nmax, 1..nmax] of int; |
| r : array[1..nmax] of int; |
| way : array[1..nmax] of int; |
| use : array[1..nmax] of byte; |
| n, k : int; |
| procedure init; |
| var i : int; |
| c : char; |
| begin |
| read(n); |
| assert((n >= 1) and (n <= 1000)); |
| for i:=1 to n do begin |
| repeat |
| read(c); |
| until c in ['a'..'z']; |
| len[i]:=0; |
| repeat |
| inc(len[i]); |
| s[i][len[i]]:=c; |
| read(c); |
| until not (c in ['a'..'z']); |
| s[i][len[i] + 1]:=pred('a'); |
| assert(len[i] <= 2000); |
| end; |
| read(k); |
| assert((k >= 1) and (k <= 10)); |
| inc(k); |
| ak[1]:=1; |
| for i:=2 to k do begin |
| read(ak[i]); |
| assert((ak[i] >= 1) and (ak[i] <= n)); |
| end; |
| end; |
| function diff(x, y : int) : int; |
| var i, stop : int; |
| begin |
| if (len[x] < len[y]) then stop:=len[x] else stop:=len[y]; |
| inc(stop); |
| for i:=1 to stop do |
| if (s[x][i] <> s[y][i]) then begin |
| diff:=ord(s[x][i]) - ord(s[y][i]); |
| exit; |
| end; |
| diff:=x - y; |
| end; |
| procedure qsort(left, right : int); |
| var pp, qq, x, t : int; |
| begin |
| pp:=left - 1; |
| qq:=right + 1; |
| x:=p[(left + right) shr 1]; |
| while true do begin |
| repeat dec(qq); until (diff(x, p[qq]) >= 0); |
| repeat inc(pp); until (diff(x, p[pp]) <= 0); |
| if (pp >= qq) then break |
| else begin |
| t:=p[qq]; |
| p[qq]:=p[pp]; |
| p[pp]:=t; |
| end; |
| end; |
| if (left < qq) then qsort(left, qq); |
| if (qq + 1 < right) then qsort(qq + 1, right); |
| end; |
| procedure sort; |
| var i, j, x, y : int; |
| cadj : array[1..nmax] of int; |
| begin |
| for i:=1 to n do p[i]:=i; |
| if (n > 1) then qsort(1, n); |
| for i:=1 to n do begin |
| x:=p[i]; |
| y:=p[i mod n + 1]; |
| cadj[x]:=0; |
| while (cadj[x] < len[x]) and (s[x][cadj[x] + 1] = s[y][cadj[x] + 1]) do |
| inc(cadj[x]); |
| assert((cadj[x] <= len[x]) and (cadj[x] <= len[y])); |
| end; |
| fillchar(common, sizeof(common), 0); |
| for i:=2 to n do begin |
| x:=p[i]; |
| y:=inf; |
| j:=i; |
| while true do begin |
| dec(j); |
| if j = 0 then break; |
| if (y > cadj[p[j]]) then y:=cadj[p[j]]; |
| if y = 0 then break; |
| common[p[j]][x]:=y; |
| common[x][p[j]]:=y; |
| end; |
| end; |
| end; |
| procedure create_graph; |
| var i, j, t : int; |
| begin |
| for i:=1 to n do begin |
| t:=0; |
| j:=i; |
| repeat |
| dec(j); |
| if j = 0 then j:=n; |
| if t < common[i][j] then t:=common[i][j]; |
| if t = len[i] then d[j][i]:=inf else d[j][i]:=t + 2; |
| until j = i; |
| end; |
| for i:=1 to n do begin |
| d[i][i mod n + 1]:=1; |
| d[i][(i - 2 + n) mod n + 1]:=1; |
| end; |
| end; |
| procedure solve; |
| var i, j, t : int; |
| procedure go(x : int); |
| var y, tmp : int; |
| begin |
| y:=way[x]; |
| if (y = 0) then exit; |
| go(y); |
| if (y mod n + 1 = x) then writeln('down') else |
| if (y - 2 + n) mod n + 1 = x then writeln('up') |
| else begin |
| writeln('Alt'); |
| for tmp:=1 to d[y][x] - 1 do |
| writeln(s[x][tmp]); |
| end; |
| end; |
| begin |
| for t:=1 to k - 1 do begin |
| fillchar(use, sizeof(use), 0); |
| for i:=1 to n do r[i]:=inf; |
| r[ak[t]]:=0; |
| way[ak[t]]:=0; |
| while (true) do begin |
| j:=1; |
| for i:=2 to n do if (use[i] = 0) then |
| if (use[j] = 1) or |
| ((use[j] = 0) and (r[j] > r[i])) |
| then j:=i; |
| if (use[j] = 1) or (r[j] >= inf) then break; |
| use[j]:=1; |
| for i:=1 to n do if (use[i] = 0) then |
| if r[i] > r[j] + d[j, i] then begin |
| r[i]:=r[j] + d[j, i]; |
| way[i]:=j; |
| end; |
| end; |
| writeln(r[ak[t + 1]]); |
| go(ak[t + 1]); |
| end; |
| end; |
| begin |
| assign(input, cinfile); reset(input); |
| assign(output, coutfile); rewrite(output); |
| init; |
| sort; |
| create_graph; |
| solve; |
| close(input); close(output); |
| end. |
Комментарии