Cele mai bune solutii
pentru problema "Bomboane"
(ziua1, problema1)
Punctaj Maxim : 50 puncte
Solutii :
Tanescu Horatiu- Bihor - 17 puncte
Scortaru Mihai - Cluj - 17 puncte;
Serafimescu Serban - 17 puncte;
Arba Mihai - Maramures - 17 puncte;
Nica Edison - Iasi - 17 puncte;
Comisia Centrala
Fisierele de teste
Program realizat de elevul Tanescu Horatiu - rezultat final : premiu II - 153 puncte
const
InStr : string = 'bonbon.in';
OutStr : string = 'bonbon.out';
var
N, M : Integer;
A : array[1..100, 1..100] of Integer;
X, sol : array[1..100] of Integer;
Sum, MinSum : Longint;
Occupied : array[1..100] of Boolean;
Timer : Longint absolute $0040:$006C;
Alarm : Longint;
procedure Solve(I, J : Integer);
var
K : Integer;
begin
if I <> 0 then
begin
X[I] := J;
if I = N then
begin
if Sum < MinSum then
begin
MinSum := Sum;
for K := 1 to N do Sol[K] := X[K];
end;
Exit;
end;
end;
for K := 1 to N do
if (A[I + 1, K] < MaxInt) and (Occupied[K] = False) and (Timer < Alarm) then
begin
Inc(Sum, A[I + 1, K]);
if Sum <= MinSum then { must be smaller that previous min sum }
begin
Occupied[K] := True;
Solve(I + 1, K);
Occupied[K] := False;
end;
Dec(Sum, A[I + 1, K]);
end;
end;
procedure ReadInputData;
var
F : Text;
I, J, X : Integer;
begin
Assign(F, InStr);
Reset(F);
ReadLn(F, N, M);
for I := 1 to N do
for J := 1 to N do
A[I, J] := MaxInt;
for I := 1 to N do
begin
Occupied[I] := False;
for J := 1 to M do
begin
Read(F, X);
A[I, X] := Abs(I - X);
end;
ReadLn(F);
end;
Close(F);
end;
procedure WriteOutputData;
var
F : Text;
I : Integer;
begin
Assign(F, OutStr);
Rewrite(F);
WriteLn(F, MinSum);
for I := 1 to N do X[Sol[I]] := I;
for I := 1 to N do Write(F, X[I], ' ');
Close(F);
end;
begin
Alarm := Timer + 6*17;
ReadInputData;
MinSum := MaxInt;
Solve(0, 0);
WriteOutputData;
end.
Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica
program bomboane_amestecate;
const maxn=100;
type lin=array [0..2*maxn+1] of integer;
plin=^lin;
mat=array [0..2*maxn+1] of plin;
var cap,cost:mat;
n,m,i,j,k,t,sursa,dest,v:integer;
f:text;
d,tata:array [0..2*maxn+1] of integer;
actua:boolean;
procedure aloca;
begin
for i:=0 to dest do begin
new(cap[i]);
new(cost[i]);
for j:=0 to dest do begin
cap[i]^[j]:=-1;
cost[i]^[j]:=maxint;
end;
end;
for i:=1 to n do begin
cap[sursa]^[i]:=1;
cost[sursa]^[i]:=0;
cost[i]^[sursa]:=0;
end;
for i:=n+1 to 2*n do begin
cap[i]^[dest]:=1;
cost[i]^[dest]:=0;
cost[dest]^[i]:=0;
end;
end;
procedure load;
begin
assign(f,'bonbon.in');reset(f);
readln(f,n,m);
sursa:=0;
dest:=2*n+1;
aloca;
for i:=1 to n do begin
for j:=1 to m do begin
read(f,k);
cap[k]^[i+n]:=1;
cost[k]^[i+n]:=abs(i-k);
cost[i+n]^[k]:=-cost[k]^[i+n];
end;
readln(f);
end;
close(f);
end;
procedure drumu_minim;
begin
for i:=sursa to dest do begin
d[i]:=maxint;
tata[i]:=sursa;
end;
d[sursa]:=0;
repeat
actua:=false;
for i:=sursa to dest do
if d[i]<>maxint then
for j:=sursa to dest do
if cap[i]^[j]=1 then
if d[i]+cost[i]^[j]<d[j] then begin
d[j]:=d[i]+cost[i]^[j];
tata[j]:=i;
actua:=true;
end;
until not(actua);
end;
procedure baga_cu_incredere;
begin
i:=dest;
while i<>0 do begin
j:=tata[i];
cap[j]^[i]:=0;
cap[i]^[j]:=1;
i:=j;
end;
end;
procedure baga_apa;
begin
drumu_minim;
baga_cu_incredere;
end;
function gata:boolean;
begin
v:=0;
for i:=n+1 to 2*n do
if cap[i]^[dest]=0 then v:=v+1;
if v=n then gata:=true
else gata:=false;
end;
procedure scrie;
begin
t:=0;
for i:=1 to n do begin
k:=0;
for j:=n+1 to 2*n do
if (cap[i]^[j]=0) and (cost[i]^[j]<>maxint) then k:=j;
t:=t+cost[i]^[k];
end;
assign(f,'bonbon.out');rewrite(f);
writeln(f,t);
for i:=1 to n do begin
k:=0;
for j:=n+1 to 2*n do
if (cap[i]^[j]=0) and (cost[i]^[j]<>maxint) then k:=j;
write(f,k-n,' ');
end;
close(f);
end;
begin {programul principal}
load;
repeat
baga_apa;
until gata;
scrie;
end.
Fisierele de teste :
Test 1 :
99 4
3 15 81 46
52 58 40 25
17 5 22 21
65 10 5 73
32 84 51 51
11 43 97 96
46 71 81 32
54 94 18 64
78 90 87 4
81 3 2 86
17 20 45 80
26 46 20 97
74 71 35 55
2 14 30 39
54 4 1 89
43 12 91 2
14 64 62 84
53 88 32 69
44 66 84 26
57 9 64 33
45 86 7 22
59 43 76 84
21 10 23 12
11 94 58 2
64 92 21 63
78 63 96 1
65 63 79 46
26 30 25 83
11 52 15 88
95 79 26 58
98 52 94 21
1 53 95 43
59 14 96 85
30 53 50 74
65 33 44 3
45 22 51 15
73 23 60 75
32 55 29 71
57 60 6 48
35 65 94 50
47 35 90 58
15 50 59 98
18 33 76 39
9 12 14 27
10 93 83 36
91 45 86 3
90 67 44 17
60 60 55 8
69 20 20 89
78 4 98 57
9 35 81 76
74 38 61 63
50 16 56 87
78 56 24 51
87 6 98 40
68 10 87 28
11 85 66 72
54 54 68 86
40 68 99 88
68 31 17 52
33 75 62 6
53 22 59 12
76 72 25 95
19 7 19 66
13 44 13 25
37 42 6 80
67 77 97 92
99 74 72 47
5 70 55 36
97 13 88 4
96 37 62 24
30 91 91 49
73 83 93 28
93 71 19 31
93 39 37 90
73 72 41 19
75 29 31 67
27 75 16 9
36 16 13 40
67 62 7 16
38 23 95 49
69 57 79 36
23 1 5 24
41 48 29 79
85 41 28 18
83 49 70 28
38 27 8 38
69 66 85 31
29 7 27 89
49 48 61 18
77 61 39 80
82 77 99 80
70 56 47 77
47 99 70 92
42 37 56 24
92 34 42 61
89 42 82 34
48 41 34 34
8 8 82 82
Test 2 :
2 1
1
Test 3 :
20 12
18 4 10 10 14 2 5 9 9 1 1 7
20 7 13 11 6 10 7 10 1 20 12 1
11 13 10 3 19 16 12 6 7 10 4 13
12 17 14 4 8 10 6 19 10 6 13 15
5 2 3 16 10 5 18 3 3 15 6 10
16 9 8 6 9 3 16 19 17 13 3 8
12 16 8 20 4 16 3 15 14 1 12 3
15 3 13 12 9 20 1 10 16 3 12 3
1 9 2 18 4 3 19 2 2 5 16 18
11 13 2 7 14 18 16 5 16 19 11 20
11 14 11 8 4 1 4 19 1 14 4 19
2 13 8 5 10 12 20 4 17 2 11 9
7 7 15 5 14 4 18 1 14 6 11 11
19 19 7 8 9 18 1 7 18 5 4 1
20 16 9 8 2 4 5 9 5 11 8 8
16 18 12 11 14 18 19 20 15 12 13 12
12 18 13 8 2 20 7 14 6 8 11 7
2 9 20 15 18 13 2 20 13 7 14 20
9 6 19 15 14 5 15 5 6 15 6 6
19 17 15 15 17 17 17 17 17 17 17 17
Test 4 :
1 1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
Test 5 :
98 12
23 39 2 15 95 32 88 81 60 61 11 22
77 48 6 64 95 38 29 66 37 38 82 84
14 3 45 78 34 34 15 72 54 44 5 75
82 82 51 53 68 48 16 85 1 8 88 66
19 20 57 15 13 35 53 22 40 85 7 37
21 27 97 79 59 78 51 20 22 71 13 68
65 7 32 77 83 72 25 28 40 95 73 60
77 6 20 85 44 27 31 69 67 67 61 71
59 35 36 9 54 98 19 48 86 9 57 61
80 94 4 88 1 57 60 6 81 86 6 77
56 71 76 55 9 18 43 43 65 49 78 35
87 88 18 20 11 20 61 80 56 94 65 49
29 37 26 84 40 35 33 4 47 57 79 57
92 7 38 46 74 5 30 25 92 81 58 19
49 5 92 66 93 64 8 63 43 15 9 67
30 29 28 77 26 21 50 20 83 37 89 90
74 27 61 40 6 41 92 87 57 19 77 29
85 64 71 47 52 16 68 53 92 65 18 22
40 89 77 70 58 80 94 46 45 88 75 71
24 50 73 79 29 17 17 61 42 28 57 70
52 10 95 76 35 63 31 65 79 91 25 22
7 78 2 37 49 10 1 44 12 13 55 52
94 44 86 43 85 55 13 65 29 14 9 5
28 61 96 48 69 47 35 64 33 45 9 47
44 52 87 17 94 51 91 71 29 46 44 33
53 21 36 18 55 86 46 35 4 19 49 15
75 71 25 77 57 60 64 18 72 25 21 78
66 12 44 14 38 61 18 73 95 65 79 71
97 38 78 2 62 13 19 19 4 76 87 19
14 78 74 48 69 81 6 55 80 55 67 60
72 24 17 90 79 4 48 33 8 17 2 67
65 44 40 21 95 68 95 30 47 24 91 94
56 22 74 3 57 69 26 2 22 61 25 92
82 19 93 59 27 20 37 32 40 32 51 90
37 50 96 36 21 87 22 73 44 89 90 8
80 57 77 35 13 2 4 70 97 64 25 72
86 90 33 26 76 18 89 6 47 18 15 44
9 36 22 55 34 75 40 94 96 46 89 66
12 60 87 97 34 63 97 47 7 17 65 12
29 60 93 48 88 64 49 45 1 2 98 72
15 16 35 19 19 78 26 11 24 57 93 33
12 13 23 19 95 30 36 84 17 41 7 15
61 78 77 14 98 89 15 12 65 87 17 66
21 24 53 87 94 1 12 14 65 74 60 78
54 10 72 76 22 61 68 2 5 42 54 4
24 75 79 20 54 21 50 58 44 64 40 28
8 94 8 62 46 85 23 76 66 77 31 48
90 41 26 95 35 9 53 5 4 59 1 38
82 31 48 90 11 55 67 84 45 25 84 17
50 74 21 10 5 91 92 36 24 22 82 52
31 48 85 86 88 65 15 60 91 76 21 31
85 71 52 87 44 84 70 54 32 76 49 3
63 39 32 70 6 17 32 97 55 7 32 67
82 59 11 35 95 93 40 62 34 20 85 83
87 52 14 60 67 40 33 79 47 16 63 24
51 28 3 91 1 12 48 80 82 56 45 77
26 38 2 73 18 57 93 91 15 74 79 74
25 1 3 11 91 6 30 28 75 3 91 39
15 4 76 48 47 6 94 41 69 64 39 61
40 66 60 37 37 52 54 27 73 91 49 53
70 73 42 80 75 72 87 16 43 20 10 42
30 7 70 13 27 86 28 87 24 51 96 86
38 52 47 9 98 60 6 17 42 12 49 50
7 17 91 43 50 69 82 76 59 2 1 25
43 72 18 52 63 54 90 13 6 95 51 25
58 30 66 85 70 74 42 86 90 49 1 42
22 13 93 10 8 23 20 24 76 3 43 93
52 34 7 74 74 94 96 71 75 94 41 41
98 49 74 80 86 45 4 43 9 59 24 47
35 9 5 43 34 18 28 41 85 45 73 11
25 92 76 89 55 66 89 69 36 89 24 85
91 34 55 7 62 18 53 86 41 45 13 32
34 8 98 58 13 49 2 11 55 62 32 21
12 10 43 54 84 28 42 21 3 7 92 96
84 16 38 4 10 20 11 41 54 90 75 72
47 50 38 14 58 52 8 81 31 10 71 75
8 56 12 34 83 86 43 53 31 64 73 36
26 29 38 16 9 8 93 41 39 78 34 3
92 34 73 53 38 96 2 5 31 89 36 75
3 89 41 75 64 1 11 58 80 71 14 54
58 1 96 59 50 56 11 59 70 33 11 31
28 29 95 23 46 92 82 4 69 28 33 82
62 67 50 5 10 89 58 63 70 80 29 69
58 69 88 8 29 36 80 93 27 51 81 53
93 63 81 81 46 50 83 23 5 41 12 88
96 27 66 16 51 70 14 23 42 42 97 27
58 98 93 92 81 26 68 5 70 82 62 78
37 45 31 90 26 97 54 32 63 90 39 53
33 26 14 50 36 23 62 36 27 80 42 69
98 68 45 37 67 26 67 63 33 42 37 63
56 84 58 64 33 97 68 88 10 88 96 84
69 62 56 10 46 27 79 73 81 96 83 97
51 16 97 56 81 66 3 97 45 16 59 14
51 62 56 63 30 83 68 51 67 3 96 39
32 46 27 88 98 56 73 30 83 72 39 83
62 81 72 46 16 79 46 31 23 30 98 59
62 84 23 68 79 59 98 84 98 30 16 39
39 83 68 83 23 83 30 39 68 56 39 23
Test 6 :
100 1
70
82
66
14
78
50
3
58
31
57
87
29
4
21
19
12
83
69
36
42
8
22
96
52
13
61
64
76
1
86
60
35
63
49
59
97
65
73
32
24
85
89
23
94
41
40
18
80
16
38
15
30
72
27
91
77
55
17
25
67
46
28
10
44
2
95
51
56
62
71
84
99
20
90
39
74
26
81
53
88
7
98
43
54
33
68
79
48
75
9
45
11
92
100
6
37
93
5
47
34
Test 7 :
100 5
34 50 2 71 15
57 53 20 45 10
20 51 36 33 84
61 26 89 25 70
69 73 85 88 92
89 43 65 2 35
28 25 97 41 9
88 10 37 31 13
88 52 89 36 93
54 52 68 75 5
89 85 45 71 58
36 54 18 44 27
61 95 81 71 41
58 83 20 65 20
54 3 50 7 84
41 77 55 23 21
100 95 3 42 12
98 49 63 46 77
91 21 2 74 83
4 51 75 81 86
55 29 30 61 85
73 73 40 50 75
86 96 54 65 83
62 51 96 63 30
60 68 85 97 64
8 93 60 99 81
30 55 17 78 11
86 77 8 44 10
79 94 22 40 74
34 15 13 100 98
50 24 24 57 51
8 94 70 66 53
36 76 26 47 43
68 94 6 43 38
6 28 40 30 10
82 79 37 57 19
57 26 6 60 95
77 31 6 48 72
52 72 100 77 35
37 85 90 23 72
33 49 86 74 18
39 21 22 71 22
35 52 76 91 71
79 65 22 88 48
89 65 97 83 7
14 97 48 50 24
86 63 30 96 33
28 5 18 26 42
35 47 37 70 91
31 47 59 52 7
42 42 29 60 17
55 5 41 16 49
93 15 73 99 3
87 98 39 98 61
8 16 17 60 33
92 87 20 31 24
29 43 74 87 75
97 93 72 41 21
24 93 8 67 63
33 55 14 23 19
44 6 37 22 67
4 75 1 74 80
23 49 17 21 40
40 80 25 67 48
23 10 51 26 16
31 90 25 15 2
98 45 61 53 48
64 42 9 28 95
96 13 2 25 82
46 7 62 64 99
44 35 34 56 83
53 67 3 72 57
66 18 64 5 70
4 34 39 58 28
81 78 81 95 4
1 7 29 18 70
76 46 79 9 67
92 11 39 27 82
43 68 27 9 38
66 66 87 13 15
38 99 80 64 4
47 29 68 16 66
80 62 69 45 1
46 99 88 92 59
5 27 14 78 94
58 13 84 54 76
39 62 79 17 34
53 56 96 27 100
100 91 46 19 59
38 82 47 87 12
58 14 38 9 3
16 69 69 12 73
59 14 45 1 63
32 19 78 11 12
36 76 92 78 32
59 82 91 44 84
56 49 1 56 19
12 84 56 32 32
69 11 90 80 32
62 11 94 90 90
Test 9 :
88 3
13 49 11
13 33 60
66 43 74
45 83 55
41 23 19
50 59 84
1 82 32
7 43 8
60 87 49
70 72 80
72 81 73
19 13 30
87 34 73
22 18 46
75 27 65
56 46 34
82 83 51
81 73 76
46 7 88
50 63 19
70 10 57
39 75 55
15 6 65
5 75 42
72 41 55
56 80 70
35 8 25
61 42 3
33 60 36
34 16 49
74 52 31
76 35 15
50 56 6
54 52 38
67 38 84
6 29 33
64 28 80
29 1 59
24 67 24
29 79 61
24 84 36
40 61 78
88 30 58
51 26 37
76 53 26
5 53 45
59 39 58
53 68 57
85 79 65
86 5 38
15 37 74
30 45 82
8 67 87
26 71 78
40 22 7
3 25 22
18 51 85
31 16 39
86 37 9
20 58 52
88 23 20
3 66 78
12 71 86
1 36 77
47 57 64
31 68 48
9 9 23
77 27 17
62 28 44
32 18 83
77 16 28
20 2 63
41 2 48
71 62 14
2 48 85
10 17 54
11 17 81
4 64 69
42 14 44
63 69 25
79 43 66
21 11 69
10 21 35
68 54 62
21 44 27
40 14 32
4 47 4
47 12 12