Anonymous user
Count the coins/0-1: Difference between revisions
m
→{{header|Perl}}: prepend pascal
(→{{header|Phix}}: well...) |
m (→{{header|Perl}}: prepend pascal) |
||
Line 157:
%%%mzn-stat-end
Finished in 207msec
</pre>
=={{header|Pascal}}==
first count all combinations by brute force.Modified nQueens.
<lang pascal>program Coins0_1;
{$IFDEF FPC}
{$MODE DELPHI}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$Apptype console}
{$ENDIF}
uses
sysutils;// TDatetime
const
coins1 :array[0..4] of byte = (1, 2, 3, 4, 5);
coins2 :array[0..6] of byte = (1, 1, 2, 3, 3, 4, 5);
coins3 :array[0..15] of byte = (1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100);
nmax = High(Coins3);
type
{$IFNDEF FPC}
NativeInt = longInt;
{$ENDIF}
tFreeCol = array[0..nmax] of Int32;
var
n,gblCount : nativeUInt;
FreeIdx,
IdxWeight : tFreeCol;
procedure AddNextWeight(Row,sum:nativeInt);
var
i,Col,Weight : nativeInt;
begin
IF row <= n then
begin
For i := row to n do
begin
Col := FreeIdx[i];
Weight:= IdxWeight[col];
IF Sum+Weight > 0 then
CONTINUE;
Sum +=Weight;
If Sum = 0 then
Begin
Sum -=Weight;
inc(gblCount);
end
else
begin
//swap FreeRow[Row<->i]
FreeIdx[i] := FreeIdx[Row];
FreeIdx[Row] := Col;
AddNextWeight(Row+1,sum);
//Undo
Sum -=Weight;
FreeIdx[Row] := FreeIdx[i];
FreeIdx[i] := Col;
end;
end;
end;
end;
procedure CheckAll(i,MaxSum:NativeInt);
Begin
n := i;
gblCount := 0;
AddNextWeight(0,-MaxSum);
WriteLn(MaxSum:6,gblCount:12);
end;
var
i: nativeInt;
begin
For i := 0 to High(coins1) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins1[i];
end;
CheckAll(High(coins1),6);
For i := 0 to High(coins2) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins2[i];
end;
CheckAll(High(coins2),6);
For i := 0 to High(coins3) do
Begin
FreeIdx[i] := i;
IdxWeight[i] := coins3[i];
end;
CheckAll(High(coins3),40);
end.</lang>
{{out}}
<pre> 6 10
6 38
40 3782932
// real 0m0,079s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )
</pre>
=={{header|Perl}}==
| |||