Cele mai bune solutii
pentru problema "Clone"
(ziua1, problema1)
Punctaj Maxim : 50 puncte
Solutii :
Carcu Adrian - Bistrita Nasaud - 50 puncte
Batog Bogdan - Bucuresti - 50 puncte;
Stanciu Adrian - Bucuresti - 49 puncte;
Moraru Dalian - Ilfov - 49 puncte;
Pietraroiu Marius - Prahova- 49 puncte.
Comisia Centrala
Fisierele de teste
Program realizat de elevul Batog Bogdan - rezultat final : premiu I - 147 puncte
type mult=set of byte;
var
fil :text;
n,m,k,i,j,C,S,s2 :integer;
L,d,nc,snc,Gi,DIN,T,li :array[1..200] of integer;
G :array[1..200] of mult;
temp :mult;
Procedure NS;
begin
writeln(fil,'NU EXISTA SOLUTIE');
close(fil);
halt
end;
Procedure swap(var s1,s2:integer);
var f:integer;
begin
f:=s1; s1:=s2; s2:=f;
end;
Procedure QS(li,ls:integer);
var i,j,k:integer;
begin
i:=li; j:=ls; k:=NC[(li+ls) div 2];
repeat
while NC[i]>k do inc(i);
while NC[j]<k do dec(j);
if i<=j then
begin
Swap(NC[i],NC[j]);
Swap(SNC[i],SNC[j]);
inc(i);
dec(j);
end
until i>j;
if i<ls then QS(i,ls);
if j>li then QS(li,j)
end;
Procedure QS2(li,ls:integer);
var i,j,k:integer;
begin
i:=li; j:=ls; k:=Gi[(li+ls) div 2];
repeat
while Gi[i]<k do inc(i);
while Gi[j]>k do dec(j);
if i<=j then
begin
Swap(Gi[i],Gi[j]);
Swap(SNC[i],SNC[j]);
temp:=G[i]; G[i]:=G[j]; G[j]:=temp;
inc(i);
dec(j);
end
until i>j;
if i<ls then QS2(i,ls);
if j>li then QS2(li,j)
end;
Function Include(var s1,s2:mult):boolean; { s1 se include in s2 }
var i:integer;
begin
for i:=1 to N do
if (i in s1) and (not (i in s2)) then begin include:=false; exit end;
include:=true
end;
Procedure Print(j:integer);
var i:integer;
begin
if j=0 then exit;
Print(T[j]);
for i:=1 to N do if i in G[j] then write(fil,i,' ');
writeln(fil);
end;
begin
assign(fil,'CLONE.INP');
reset(fil);
readln(fil,n);
readln(fil,m);
readln(fil,k);
for i:=1 to m do read(fil,L[i]);
readln(fil);
fillchar(D,sizeof(D),0);
for i:=1 to k do begin read(fil,j); d[j]:=1 end;
readln(fil);
fillchar(nc,sizeof(nc),0);
while not seekeof(fil) do readln(fil,C,nc[C]);
close(fil);
assign(fil,'CLONE.OUT'); rewrite(fil);
S:=N-k;
for i:=1 to N do S:=S+nc[i];
s2:=0;
for i:=1 to M do s2:=s2+L[i];
if (S<>S2) then NS;
for i:=1 to N do Snc[i]:=i;
QS(1,N);
for i:=1 to N do if (NC[i]+1>M) and (D[SNC[i]]<>1) then NS;
fillchar(Gi,sizeof(Gi),0);
fillchar(G,sizeof(G),0);
k:=0;
for i:=1 to N do
if D[SNC[i]]<>1 then
for j:=1 to NC[i]+1 do
begin
inc(k);
while (gi[k]=L[k]) do if k>=M then K:=1 else inc(k);
G[k]:=G[k]+[SNC[i]];
inc(Gi[k])
end;
for i:=1 to M do
begin
for j:=1 to N do
if j in G[i] then write(fil,j,' ');
writeln(fil)
end;
QS2(1,M);
fillchar(DIN,sizeof(DIN),0);
for i:=1 to M do
begin
DIN[i]:=1;
T[i]:=0;
for j:=1 to i-1 do
if (DIN[j]+1>DIN[i]) and Include(G[j],G[i]) then
begin DIN[i]:=DIN[j]+1; T[i]:=j end
end;
i:=1;
for j:=1 to M do if DIN[j]>DIN[i] then i:=j;
writeln(fil,DIN[j]);
Print(j);
close(fil)
end.
Program realizat de elevul Carcu Adrian - rezultat final : premiu II - 127 puncte
#include <stdio.h>
#include <process.h>
#define M 200
char n,m,k,l[M],d[M],c[M],e[M][M],o[M],o1[M];int max;
char in[M],sf[M],v[M],leg[M];
void main(void)
{
FILE*f;
int i,j,t,t1,t2;
f=fopen("clone.inp","rt");
fscanf(f,"%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)fscanf(f,"%d",&l[i]);
for(i=0;i<m;i++)o[i]=i;
for(i=0;i<n;i++)o1[i]=i;
for(i=0;i<n;i++)d[i]=1;
for(i=0;i<k;i++){fscanf(f,"%d",&j);d[j-1]=0;}
while(fscanf(f,"%d%d",&i,&j)==2)d[i-1]+=j;
fclose(f);
for(i=0;i<m;i++)for(j=0;j<n;j++)e[i][j]=0;
for(i=0;i<m-1;i++)for(j=i+1;j<m;j++)
if(l[i]>l[j]){t=l[i];l[i]=l[j];l[j]=t;t=o[i];o[i]=o[j];o[j]=t;}
for(i=0;i<n-1;i++)for(j=i+1;j<n;j++)
if(d[i]<d[j]){t=d[i];d[i]=d[j];d[j]=t;t=o1[i];o1[i]=o1[j];o1[j]=t;}
t=0;while(!l[t])t++;
for(i=0;i<n;i++)
{t1=t;in[i]=t;
for(j=0;j<d[i];j++)
{e[o[t1]][o1[i]]=1;l[t1]--;t2=t1;
t1++;while(!l[t1])t1++;}
sf[i]=t2;while(!l[t])t++;}
for(i=0;i<n;i++)
{v[i]=1;leg[i]=i;
for(j=0;j<i;j++)if(in[j]<=in[i]&&sf[j]>=sf[i]&&v[j]+1>v[i])
{v[i]=v[j]+1;leg[i]=j;}
}
// for(i=0;i<n;i++)printf("in%d sf%d v%d\n",in[i],sf[i],v[i]);
max=0;for(i=0;i<n;i++)if(v[i]>max){max=v[i];t=i;}
fprintf(f,"%d\n",max);
while(leg[t]!=t)
{for(i=in[t];i<sf[t];i++)
fprintf(f,"%d ",o[i]+1);fprintf(f,"\n");
t=leg[t];}
f=fopen("clone.out","wt");
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
if(e[i][j])fprintf(f,"%d ",j+1);
fprintf(f,"\n");
}
fclose(f);
}
Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica
Program Colonizarea_Planetei;
Uses Crt;
CONST MAXIM = 200;
Type Grup = Array[1..MAXIM] Of Set Of Byte;
Vector = Array[1..MAXIM] Of Byte;
Var G : Grup;
f, Out : Text;
Clone, CardM, Contor : Vector;
E, Index, Poz : Vector;
n, m, k, i, j, Aux : Byte;
Echipaj, X : Set Of Byte;
Mort, Pozitie : Byte;
Colonist, NumarClone : Byte;
V : Array[1..MAXIM] Of String;
Max, PozMax : Byte;
Test : String;
Procedure Quicksort(Lo, Hi, Ce: Byte);
Procedure Sort(l, r: Byte);
Var
i, j, m : Byte;
y, z : Byte;
s, t : String;
Begin
i := l; j := r; m := (l + r) DIV 2;
If Ce = 1 Then
y := Clone[m]
Else
s := V[m];
Repeat
If Ce = 1 Then
While Clone[i] > y Do Inc(i)
Else
While V[i] < s Do Inc(i);
If Ce = 1 Then
While y > Clone[j] Do Dec(j)
Else
While s < V[j] Do Dec(j);
If i <= j Then
Begin
If Ce = 1 Then
Begin
z := Clone[i];
Clone[i] := Clone[j];
Clone[j] := z;
z := E[i];
E[i] := E[j];
E[j] := z;
End
Else
Begin
t := V[i];
V[i] := V[j];
V[j] := t;
y := Index[i];
Index[i] := Index[j];
Index[j] := y
End;
Inc(i); Dec(j)
End
Until i > j;
If l < j Then Sort(l, j);
If i < r Then Sort(i, r);
End;
Begin {quicksort};
Sort(Lo, Hi);
End;
Function Vi_In_Vj(p, q : Byte) : Boolean;
Var r : Byte;
Begin
Vi_In_Vj := True;
For r := 1 To n - k Do
If V[p][r] > V[q][r] Then
Begin
Vi_In_Vj := False;
Exit
End
End;
Function Suma(x : Vector; Cat : Byte) : Word;
Var i : Byte;
s : Word;
Begin
s := x[1];
For i := 2 To Cat Do s:= s + x[i];
Suma := s
End;
Procedure NU_EXISTA_SOLUTIE;
Begin
ReWrite(Out);
WriteLn(Out, 'NU EXISTA SOLUTIE');
Close(Out);
{ ReadKey; }
Halt(1)
End;
Procedure Afiseaza_Grupuri;
Begin
For i := 1 To m Do
Begin
{ Write('{'); }
For j := 1 To n Do
If j In G[i] Then Write(Out, j, ' ');
WriteLn(Out, ' ')
End
End;
Begin
ClrScr;
Write('Test : '); ReadLn(Test);
Assign(f, Test); Reset(f);
Assign(Out, 'Clone.out'); ReWrite(Out);
ReadLn(f, n);
ReadLn(f, m);
ReadLn(f, k);
Echipaj := [];
For i := 1 To n Do Echipaj := Echipaj + [i]; {echipaj initial}
For i := 1 To n Do Clone[i] := 1; {daca nu se cloneaza = 1}
For i := 1 To m Do Read(f, CardM[i]); {capacitate supravietuire}
For i := 1 To k Do
Begin
Read(f, Mort); {au murit la aterizare}
Echipaj := Echipaj - [Mort];
Clone[Mort] := 0;
End;
While Not(SeekEof(f)) Do {numar de clone }
Begin
ReadLn(f, Colonist, NumarClone);
If (NumarClone >= m) Or Not (Colonist In Echipaj) Then
NU_EXISTA_SOLUTIE;
Clone[Colonist] := NumarClone + 1;
End;
Close(f);
i := 1; {colonisti ramasi - elimin zerourile}
While i < n - k + 1 Do
If Clone[i] = 0 Then
Begin
For j := i To n-1 Do Clone[j] := Clone[j + 1];
Clone[n] := 0
End
Else
Inc(i);
If Suma(Clone, n - k) > Suma(CardM, m) Then {daca sunt mai multi }
NU_EXISTA_SOLUTIE; {colonisti decat capacitatea}
{de supravietuire totala a }
{planetei }
{ pastrez Echipaj in X }
X := Echipaj;
{ mut Echipaj in E ca sa-l pot sorta descrescator pentru }
{ formarea grupurilor }
i := 1; j := 0;
While Echipaj <> [] Do
Begin
If i In Echipaj Then
Begin
Inc(j);
E[j] := i;
Echipaj := Echipaj - [i]
End;
Inc(i)
End;
{ ordonez descrescator dupa numar de clone}
QuickSort(1, n - k, 1);
{ formez grupurile ... pot fi diferite, depinde de algoritmul de sortare}
For i := 1 To m Do
Begin
For j := 1 To n-k Do
If (Clone[j] > 0) And (Contor[i] < CardM[i]) Then
Begin
G[i] := G[i] + [E[j]];
Dec(Clone[j]);
Inc(Contor[i])
End;
{ QuickSort(1, n - k, 1);}
For j := n-k DownTo 2 Do
If Clone[j] > Clone[j-1] Then
Begin
Aux := Clone[j];
Clone[j] := Clone[j-1];
Clone[j-1] := Aux;
Aux := E[j];
E[j] := E[j-1];
E[j-1] := Aux
End;
End;
For i := 1 To m Do {daca un grup nu are nici}
If G[i] = [] Then {o persoana => nu se pot }
NU_EXISTA_SOLUTIE; {regasi ca si clone in }
{alt grup - nu are cine}
Echipaj := X; { refac echipaj }
Afiseaza_Grupuri;
{ formez vectori caracteristici pentru fiecare grup / fata de multimea totala}
For i := 1 To m Do
Begin
V[i] := ''; Index[i] := i; {Index[i] - indexul grupului i; pt afisare}
For j := 1 To n Do
If j In Echipaj Then
If j In G[i] Then V[i] := V[i] + '1'
Else V[i] := V[i] + '0'
End;
{ ordonez lexicografic vectorii caracteristici }
QuickSort(1, m, 2);
{ acum daca grupul G[i] este inclus in grupul G[j] =>
vectorul V[i] este "inaintea" lui V[j] in sirul ordonat}
{ deci pentru rezolvarea problemei....................}
{ determin un subsir crescator de lungime maxima -> programare dinamica}
For i := 1 To m Do E[i] := 0;
For i := m - 1 DownTo 1 Do
Begin
Max := 0;
For j := i + 1 To m Do
If (Vi_In_Vj(i, j)) And (Max < E[j] + 1) Then
Begin
Max := 1 + E[j];
PozMax := j
End;
E[i] := Max; Poz[i] := PozMax
End;
Max := E[1]; PozMax := 1;
For i := 2 To m Do
If E[i] > Max Then
Begin
Max := E[i];
PozMax := i;
End;
{ If Max = 0 Then } {nu sunt minim 2 grupuri}
{ NU_EXISTA_SOLUTIE; }
WriteLn(Out, Max + 1); {numarul de grupuri}
i := PozMax;
While i <> 0 Do
Begin
{ Write(V[i], ' =====> Grupul ', Index[i], ' {');} { se afiseaza Grupul G[i]}
For j := 1 To n Do If j In G[Index[i]] Then Write(Out, j, ' '); WriteLn(Out, ' ');
i := Poz[i];
End;
Close(Out)
{ ReadKey }
End.
Fisierele de teste :
Test 1 :
9
4
4
3 4 1 2
3 4 7 8
2 3
6 2
Test 2 :
3
2
1
2 1
2
1 1
Test 3 :
3
2
1
1 1
2
Test 4 :
3
2
1
3 1
2
1 2
Test 5 :
3
1
0
3
Test 6 :
4
4
0
4 4 4 4
1 3
2 3
3 3
4 3
Test 7 :
6
4
0
4 6 5 5
1 2
5 3
3 4
4 3
6 3
Test 8 :
9
4
4
2 4 3 1
3 4 7 8
2 2
6 2
Test 9 :
7
3
7
2 3 2
1 2 3 4 5 6 7