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.

[BACK]


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.

[BACK]


 

 

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

[BACK]