Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 5 KB
PROGRAM ShoppingPlan;
CONST
tid = 'large';
inputFile = 'D-'+tid+'-practice.in';
outputFile = 'D-'+tid+'-practice.out';
maxItems = 15;
maxStores = 50;
maxFull = (1 SHL maxItems) - 1;
infinitePrice = 1E9;
VAR
num_items, num_stores, price_of_gas: INTEGER;
item_names: ARRAY [1..maxItems] OF STRING;
item_perishable: ARRAY [1..maxItems] OF BOOLEAN;
store_x : ARRAY [0..maxStores] OF INTEGER;
store_y : ARRAY [0..maxStores] OF INTEGER;
store_prices : ARRAY [0..maxStores, 1..maxItems] OF INTEGER;
store_codes: ARRAY [0..maxStores] OF INTEGER;
solve_cache : ARRAY [0..maxStores, 0..maxFull] OF DOUBLE;
dist_price : ARRAY [0..maxStores, 0..maxStores] OF DOUBLE;
FUNCTION Solve(store, items: INTEGER): DOUBLE; FORWARD;
FUNCTION DistPrice(store1, store2: INTEGER; perish: BOOLEAN) : DOUBLE;
BEGIN
IF perish THEN DistPrice := dist_price[store1][0]+dist_price[0][store2]
ELSE DistPrice := dist_price[store1][store2];
END;
FUNCTION Combine(store, items0, items, pos: INTEGER; perish: BOOLEAN): DOUBLE;
VAR
next_store, item_code: INTEGER;
cur: DOUBLE;
BEGIN
IF pos > num_items THEN
BEGIN
IF (items0 = items) AND (store <> 0) THEN Combine := infinitePrice
ELSE
BEGIN
IF (items = (1 SHL num_items)-1) THEN Combine := DistPrice(store, 0, FALSE)
ELSE
BEGIN
Combine := InfinitePrice;
FOR next_store := 1 TO num_stores DO
BEGIN
IF store = next_store THEN CONTINUE;
cur := DistPrice(store, next_store, perish)+Solve(next_store, items);
IF (cur < Combine) THEN Combine:= cur;
END;
END;
END;
END
ELSE
BEGIN
Combine:=Combine(store, items0, items, pos+1, perish);
item_code := 1 SHL (pos-1);
IF ((store_codes[store] AND item_code) <> 0) AND ((items AND item_code) = 0) THEN
BEGIN
cur:= store_prices[store][pos]+Combine(store, items0, items OR item_code, pos+1, perish OR item_perishable[pos]);
IF cur < Combine THEN Combine := cur;
END;
END;
END;
FUNCTION Solve(store, items: INTEGER): DOUBLE;
BEGIN
IF solve_cache[store][items] < 0 THEN
BEGIN
solve_cache[store][items] := Combine(store, items, items, 1, FALSE);
END;
Solve := solve_cache[store][items];
END;
FUNCTION Solve(): DOUBLE;
VAR
i, j: INTEGER;
dx, dy: DOUBLE;
BEGIN
FOR i:= 0 TO maxStores DO
FOR j:= 0 TO maxFull DO
solve_cache[i][j]:= -1;
FOR i:= 0 TO num_stores DO
FOR j := 0 TO num_stores DO
BEGIN
dx := store_x[i]-store_x[j];
dy := store_y[i]-store_y[j];
dist_price[i][j] := sqrt(dx*dx+dy*dy)*price_of_gas;
END;
Solve := Solve(0, 0);
END;
FUNCTION NextToken(line: STRING; VAR pos: INTEGER): STRING;
VAR
pos0, len: INTEGER;
BEGIN
pos0:= pos;
len := Length(line);
WHILE (pos <= len) AND (line[pos] <> ' ') AND (line[pos] <> ':') DO INC(pos);
NextToken := Copy(line, pos0, pos-pos0);
INC(pos);
END;
PROCEDURE TestCase(id: INTEGER; VAR fin, fout: Text);
VAR
i, j, pos, len: INTEGER;
s, item_price, item_name: STRING;
errCode: WORD;
solution: DOUBLE;
BEGIN
ReadLn(fin, num_items, num_stores, price_of_gas);
ReadLn(fin, s);
len := Length(s);
pos := 1;
FOR i:= 1 TO num_items DO
BEGIN
item_names[i] := NextToken(s, pos);
item_perishable[i] := item_names[i][ Length(item_names[i]) ] = '!';
IF item_perishable[i] THEN item_names[i] := Copy(item_names[i], 1, Length(item_names[i])-1);
END;
FOR i := 0 TO num_stores DO
BEGIN
store_codes[i]:=0;
FOR j:= 1 TO num_items DO store_prices[i][j] := 0;
store_x[i]:= 0; store_y[i]:=0;
IF (i = 0) THEN CONTINUE;
Read(fin, store_x[i], store_y[i]);
ReadLn(fin, s);
len := Length(s);
pos := 2;
WHILE (pos <= len) DO
BEGIN
item_name := NextToken(s, pos);
item_price := NextToken(s, pos);
j := 1; WHILE (j <= num_items) AND (item_names[j] <> item_name) DO INC(j);
store_codes[i] := store_codes[i] OR ( 1 SHL (j-1) );
Val(item_price, store_prices[i][j], errCode);
END;
END;
solution:= Solve();
WriteLn('Case #',id,': ', solution:0:7);
WriteLn(fout, 'Case #',id,': ', solution:0:7);
END;
PROCEDURE Main();
VAR
fin, fout: Text;
i, N: INTEGER;
BEGIN
Assign(fin, inputFile);
Assign(fout, outputFile);
Reset(fin);
Rewrite(fout);
ReadLn(fin, N);
FOR i:= 1 TO N DO
BEGIN
TestCase(i, fin, fout);
END;
Close(fin);
Close(fout);
END;
BEGIN
Main();
END.