| ACM International Collegiate Programming Contest |
Czech Republic, CTU Prague, |
|
 | ||
Řešení úloh Školního kola FEL ČVUT, 1999
Protože se minulé kolo konalo v jediný den, nezbyl čas na prezentaci algoritmů vhodných pro řešení úloh. Z tohoto důvodu byla zveřejněny zdrojové programy všech ukázkových řešení, která napsali organizátoři. Tato řešení nebyla většinou žádným způsobem upravena, proto jen málokdy obsahují nějaké vysvětlující komentáře. Matice
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXCT 20
int dim1[MAXCT][MAXCT];
int dim2[MAXCT][MAXCT];
int l1[MAXCT][MAXCT];
int e[MAXCT][MAXCT];
#define NOO(A,B,C,D) (dim1[A][B]*dim2[A][B]*dim2[C][D] + e[A][B] + e[C][D])
void Print(int i, int j)
{
if (i)
{
printf("(");
Print(l1[i][j], j);
printf(" x ");
Print(i - l1[i][j] - 1, j + l1[i][j] + 1);
printf(")");
}
else printf("A%d", j + 1);
}
int main(void)
{
int n, m, i, j, k, l;
scanf("%d", &n);
while (n--)
{
scanf("%d", &m);
for (i = 0; i < m; ++i) scanf("%d%d", &dim1[0][i], &dim2[0][i]);
memset(l1[0], -1, sizeof(l1[0]));
memset(e[0], 0, sizeof(e[0]));
for (i = 1; i < m; ++i)
for (j = 0; j < m - i; ++j)
{
e[i][j] = NOO(0, j, i - 1, j + 1);
l1[i][j] = 0;
for (k = 1; k < i; ++k)
{
l = NOO(k, j, i - k - 1, j + k + 1);
if (l <= e[i][j])
{
e[i][j] = l;
l1[i][j] = k;
}
}
dim1[i][j] = dim1[0][j];
dim2[i][j] = dim2[0][i + j];
}
Print(m - 1, 0);
printf("\n");
}
return 0;
}
Var
slo:array[0..50, 1..50] of integer;
vzni:array[0..50, 1..50] of integer;
r:array[0..50, 1..50] of integer;
s:array[0..50, 1..50] of integer;
i,j,k,l,m,n,ss,p:integer;
Procedure output(oper, prvni:integer);
Var i,j,k:Integer;
Begin
if oper=0 then write('A', prvni:1)
else begin
Write('(');
k:=vzni[oper, prvni];
output(k-prvni,prvni);
Write(' x ');
output(oper-k+prvni-1,k+1);
Write(')');
end;
End;
Begin
read(n);
for i:=1 to n do Begin
read(m);
for j:=1 to m do Begin
read(r[0, j]); read(s[0, j]);
End;
for k:=1 to m-1 do slo[0, k]:=0;
for j:=1 to m-1 do begin {pocet uvazovanych operaci}
for k:=1 to m-j do Begin {pocatecni matice (oerace)}
ss:=$3fffffff;
for l:=1 to j do Begin {c. posledni provadene operace ve skupine}
p := slo[l-1,k]+slo[j-l,k+l]+r[l-1, k]*s[l-1, k]*s[j-l,k+l];
if p<ss then Begin
ss:=p;
vzni[j, k] := k+l-1;
r[j, k] := r[l-1, k];
s[j, k] := s[j-l, k+l];
End;
End;
slo[j, k] := ss;
End;
End;
Output(m-1, 1);
Writeln;
End;
end.
Plot
/* Uloha: Stromy by Jaroslav Volsicky */
#include <stdio.h>
#include <math.h>
#define MAX_N 1000
#define INF 200000000.0
int P[MAX_N];
float D[MAX_N];
int m,n;
float DirectC (int x1, int y1, int x2, int y2) {
float r;
if (x1!=x2) r=(float)(y2-y1)/(float)(x2-x1);
else if (y2>y1) r=INF; else r=-INF;
return r;
}
float Distance(int startpoint, int lastpoint) {
return (sqrt((P[startpoint]-P[lastpoint])*(P[startpoint]-P[lastpoint])+
(startpoint-lastpoint)*(startpoint-lastpoint)));
}
float MDifrence1(int startpoint, int * lastpoint) {
int I,MaxN;
float Max;
* lastpoint=startpoint;
for (I=0;I<n;I++) D[I]=-INF;
for (I=0;I<n;I++)
if (I!=startpoint && P[startpoint]<=P[I])
D[I]=DirectC(P[startpoint],startpoint,P[I],I);
Max=INF; MaxN=0;
for (I=0;I<n;I++)
if (D[I]>0 && D[I]<Max) { Max=D[I]; MaxN=I; }
if (Max==INF) return 0.0;
else return (Distance(startpoint,MaxN)+MDifrence1(MaxN,lastpoint));
}
float MDifrence2(int startpoint, int * lastpoint) {
int I,MaxN;
float Max;
* lastpoint=startpoint;
for (I=0;I<n;I++) D[I]=-INF;
for (I=0;I<n;I++)
if (I!=startpoint && P[startpoint]<=P[I])
D[I]=DirectC(P[startpoint],startpoint,P[I],I);
Max=-INF; MaxN=0;
for (I=0;I<n;I++)
if (D[I]<0 && D[I]>Max) { Max=D[I]; MaxN=I; }
if (Max==-INF) return 0.0;
else return (Distance(startpoint,MaxN)+MDifrence2(MaxN,lastpoint));
}
float SDifrence1(int startpoint, int * lastpoint) {
int I,MinN;
float Min;
* lastpoint=startpoint;
for (I=0;I<n;I++) D[I]=INF;
for (I=0;I<n;I++)
if (I!=startpoint && P[startpoint]>=P[I])
D[I]=DirectC(P[startpoint],startpoint,P[I],I);
Min=-INF; MinN=0;
for (I=0;I<n;I++)
if (D[I]>Min && D[I]<0) { Min=D[I]; MinN=I; }
if (Min==-INF) return 0.0;
else return (Distance(startpoint,MinN)+SDifrence1(MinN,lastpoint));
}
float SDifrence2(int startpoint, int * lastpoint) {
int I,MinN;
float Min;
* lastpoint=startpoint;
for (I=0;I<n;I++) D[I]=INF;
for (I=0;I<n;I++)
if (I!=startpoint && P[startpoint]>=P[I])
D[I]=DirectC(P[startpoint],startpoint,P[I],I);
Min=INF; MinN=0;
for (I=0;I<n;I++)
if (D[I]<Min && D[I]>0) { Min=D[I]; MinN=I; }
if (Min==INF) return 0.0;
else return (Distance(startpoint,MinN)+SDifrence2(MinN,lastpoint));
}
int main () {
int a,b,lastMin1,lastMin2,lastMax1,lastMax2;
float l;
scanf("%i\n",&m);
for (a=0;a<m;a++) {
scanf("%i\n",&n);
for (b=0;b<n;b++) scanf("%i",&P[b]); scanf("\n");
l=MDifrence1(0,&lastMin1)+
SDifrence1(0,&lastMax1)+
MDifrence2(n-1,&lastMin2)+
SDifrence2(n-1,&lastMax2)+
Distance(lastMax1,lastMax2)+
Distance(lastMin1,lastMin2);
/* if ((l-floor(l))>.5) l++; */
printf("%.0f\n",l);
}
return 0;
}
program Stromy;
const MaxN=1000;
var Y : array[1..MaxN] of integer;
M, N, mm, nn, X, OldX, NewX, MaxX, MinX : integer;
Slope, MaxSlope, MinSlope, Sum : real;
begin
Readln(M);
for mm:=1 to M do
begin
Readln(N); for nn:=1 to N do Read(Y[nn]); Readln;
Sum:=0; OldX:=1;
while OldX<N do
begin
MinSlope:=1000000;
for X:=OldX+1 to N do begin
Slope:=(Y[X]-Y[OldX])/(X-OldX);
if Slope<MinSlope then begin
MinSlope:=Slope;
MinX:=X;
end;
end;
Sum:=Sum+sqrt(sqr(MinX-OldX)+sqr(Y[MinX]-Y[OldX]));
OldX:=MinX;
end;
OldX:=1;
while OldX<N do
begin
MaxSlope:=-1000000;
for X:=OldX+1 to N do begin
Slope:=(Y[X]-Y[OldX])/(X-OldX);
if Slope>MaxSlope then begin
MaxSlope:=Slope;
MaxX:=X;
end;
end;
Sum:=Sum+sqrt(sqr(MaxX-OldX)+sqr(Y[MaxX]-Y[OldX]));
OldX:=MaxX;
end;
writeln(round(Sum):1);
end;
end.
Stavitel
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MIN(A,B) ((A)<(B))?(A):(B)
#define MAXDIM 100
int front[MAXDIM];
int right[MAXDIM];
int Cmp(const void * ptr1, const void * ptr2)
{
int a, b;
a = *((const int *)ptr1);
b = *((const int *)ptr2);
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
int main(void)
{
int i, j, k, n, max, min;
scanf("%d", &n);
while (n--)
{
scanf("%d", &i);
for (j = 0; j < i; ++j)
scanf("%d", front + j);
for (j = 0; j < i; ++j)
scanf("%d", right + j);
max = 0;
for (j = 0; j < i; ++j)
for (k = 0; k < i; ++ k)
max += MIN(right[j], front[k]);
if (i > 1)
{
qsort(front, i, sizeof(int), Cmp);
qsort(right, i, sizeof(int), Cmp);
}
min = j = k = 0;
while ((j < i) && (k < i))
{
if (front[j] == right[k])
{
min += front[j++];
++k;
}
else if (front[j] < right[k])
min += front[j++];
else
min += right[k++];
}
while (j < i)
min += front[j++];
while (k < i)
min += right[k++];
printf("Minimalni budova obsahuje %d kostek, maximalni %d kostek.\n",
min, max);
}
return 0;
}
program builder;
const MAXC = 100;
var FrontView: array [1..MAXC] of Integer;
SideView: array [1..MAXC] of Integer;
SeenTwice: array [1..MAXC] of Boolean;
n: Integer;
x: Integer;
i, j, k: Integer;
s1, s2: Integer;
s: Boolean;
function min(a, b: Integer): Integer;
begin
if a < b then min := a else min := b;
end;
function max(a, b: Integer): Integer;
begin
if a > b then max := a else max := b;
end;
begin
readln(n);
for i := 1 to n do
begin
readln(x);
for j:=1 to x do read(SideView[j]);
for j:=1 to x do read(FrontView[j]);
for j:=1 to x do SeenTwice[j] := false;
s1 := 0;
for j := 1 to x do
s1 := s1 + SideView[j] + FrontView[j];
for j := 1 to x do
begin
s := false;
for k := 1 to x do
if (SideView[j] = FrontView[k]) and not SeenTwice[k] and not s then
begin
SeenTwice[k] := true;
s := true;
s1 := s1 - FrontView[k];
end
end;
s2 := 0;
for j := 1 to x do
for k := 1 to x do
s2 := s2 + min(SideView[j], FrontView[k]);
write('Minimalni budova obsahuje ');
write(s1:1);
write(' kostek, maximalni ');
write(s2:1);
write(' kostek.');
writeln;
end
end.
Tolary
/* By Jaroslav Volsicky */
#include <stdio.h>
int PP[1000][10];
int HOW;
int CT[10]={5,10,20,50,100,200,500,1000,2000,5000};
float c;
void expr (int run, int idx) {
int del,z,how_r;
for (z=idx;z>=0;z--) {
del=run-CT[z];
if (!del) HOW++;
else if (del>0) { if (PP[(del-5)/5][z]) HOW+=PP[(del-5)/5][z];
else {
how_r=HOW;
expr (del,z);
PP[(del-5)/5][z]=HOW-how_r;
}
}
}
}
int main () {
int run,n,a;
scanf("%i\n",&n);
for (a=0;a<n;a++) {
scanf("%f\n",&c);
HOW=0;
run=(int)(c*100.00);
if (run%5) {
run++;
if (run%10) run-=5;
}
if (run) expr(run,9); else HOW=1;
printf("Pocet ruznych sestaveni je %i.\n",HOW);
}
return 0;
}
program Tolary;
const hodnota:array[1..10] of integer =
(1, 2, 4, 10, 20, 40,100,200,400,1000);
MaxCena=1000;
var Pole:array[1..10,1..MaxCena] of integer;
Moznosti:array[1..MaxCena] of integer;
function GetPole(mince,cena:integer):integer;
begin
if cena<0 then GetPole:=0
else if cena=0 then GetPole:=1
else GetPole:=Pole[mince,cena];
end;
var castka:integer;
castkar:real;
mince,cena,c,d:integer;
max:integer;
n,i : integer;
begin
readln(n);
for cena:=1 to MaxCena do
begin
pole[1,cena]:=1;
for mince:=2 to 10 do pole[mince,cena]:=0;
end;
for mince:=2 to 10 do
for cena:=1 to MaxCena do
pole[mince,cena]:=pole[mince-1,cena]+
GetPole(mince,cena-hodnota[mince]);
for cena:=1 to MaxCena do
begin
max:=0;
for mince:=1 to 10 do
if Pole[mince,cena]>max then max:=Pole[mince,cena];
Moznosti[cena]:=max;
end;
for i:=1 to n do
begin
readln(castkar);
castka:=round(20*castkar);
writeln('Pocet ruznych sestaveni je ',Moznosti[castka]:1,'.');
end;
end.
Uvozovky
#include<stdio.h>
int main() {
int n;
char c;
n=0;
while ((c=getchar())!=EOF) {
if (c=='\"')
if ((n++) & 0x01) printf("''");
else printf(",,");
else putchar(c);
}
return 0;
}
program T (input,output);
var ch: char;
b: boolean;
begin
b:=false;
while (not EOF) do begin
while (not EOLN) do begin
read(ch);
if ch='"' then begin
if b then write('''''') else write(',,');
b:=not b;
end else write(ch);
end;
writeln;
read(ch);
end;
end.
ZávislostiK této poslední úloze je hotov i popis algoritmu. Druhé vzorové řešení však není v Pascalu, ale v Pythonu. ;-) Bylo použito pouze pro kontrolu správnosti prvního řešení, nikoli pro stanovení timeoutu.
Popis řešeníNejprve se interpretují všechny příkazy DEPEND a vytvoří se graf komponent (uzel odpovídá komponentě, orientovaná hrana od komponenty ci ke komponentě cj odpovídá závislosti ci na cj).Komponenty jsou umístěny v poli v pořadí, v jakém do něj byly přidávány příkazy DEPEND a INSTALL. Navíc jsou zřetězeny podle abecedního pořadí. Algoritmus pro přidání komponenty c
Algoritmus pro odebrání komponenty c
Algoritmus vypsání seznamu komponent c
Projdi seznam komponent podle zřetězení a vypiš jejich jména.
#include <stdio.h>
#include <string.h>
#define MAX_COMPONENTS 6000
#define MAX_DEPENDENCIES (MAX_COMPONENTS * 60) + MAX_COMPONENTS
#define MAX_NAME 10
struct {
int depends; // index to 'components' array
int next;
} dependencies[MAX_DEPENDENCIES];
struct {
int depends; // temporary inverted dependencies for installing
components
int next;
} idependencies[MAX_DEPENDENCIES];
struct {
char name[MAX_NAME + 1];
int depends; // index to 'dependencies' array
int idepends; // index to 'idependencies' array
int installed;
int autoinstall;
int next;
const char *lowest_leaf;
int dependencies; // number of components dependent on this component
int idependencies; // number of components this component depends on
// (in inverted subgraph)
int iopen;
} components[MAX_COMPONENTS];
int queue[MAX_COMPONENTS];
int nd, // number of dependencies
nc, // number of components
nid,// number of inverted dependencies
nq; // number of components in the queue
void init_queue()
{
nq = 1;
}
void swap(int *i, int *j)
{
int k = *i;
*i = *j;
*j = k;
}
// put component 'c' to the priority queue
// (components in the queue are sorted accornign component names)
void enqueue(int c)
{
int n, n2;
queue[nq] = c;
n = nq;
while (n > 1)
{
n2 = n/2;
if (strcmp(components[queue[n]].name, components[queue[n2]].name) < 0)
swap(&queue[n], &queue[n2]);
else
break;
n = n2;
}
nq++;
}
// dequeue component and return it's index
int dequeue()
{
int r, n, n2, n3, nn;
if (nq == 1) return -1;
r = queue[1];
nq--;
queue[1] = queue[nq];
n = 1;
while (1)
{
n2 = n * 2;
n3 = n2 + 1;
if (n3 < nq)
{
if (strcmp(components[queue[n2]].name, components[queue[n3]].name) < 0)
nn = n2;
else
nn = n3;
if (strcmp(components[queue[n]].name, components[queue[nn]].name) < 0)
break;
else
swap(&queue[n], &queue[nn]);
n = nn;
}
else
if (n2 < nq)
{
if (strcmp(components[queue[n]].name, components[queue[n2]].name) < 0)
break;
else
swap(&queue[n], &queue[n2]);
n = n2;
}
else
break;
}
return r;
}
void init_inverted_subgraph()
{
int i;
for (i=0; i<nc; i++)
{
components[i].idepends = -1;
components[i].idependencies = 0;
components[i].iopen = 0;
}
}
// go through all not-installed components needed for component c
// and construct inverted dependencies; enqueue all roots of
// inverted-dependency graph (i.e. leaves of dependency subgraph)
void construct_inverted_subgraph(int c)
{
int d, dc;
components[c].iopen = 1;
d = components[c].depends;
while (d != -1)
{
dc = dependencies[d].depends;
// construct inverted vertices
if (!components[dc].installed)
{
components[c].idependencies++;
idependencies[nid].depends = c;
idependencies[nid].next = components[dc].idepends;
components[dc].idepends = nid;
nid++;
if (!components[dc].iopen)
construct_inverted_subgraph(dc);
}
d = dependencies[d].next;
}
if (!components[c].idependencies) enqueue(c);
}
void chain_last_component()
{
int i;
i = 0;
while (components[i].next != -1 &&
strcmp(components[nc].name, components[components[i].next].name) > 0)
i = components[i].next;
components[nc].next = components[i].next;
components[i].next = nc;
nc++;
}
void chain_last_dependency(int c)
{
dependencies[nd].next = components[c].depends;
components[c].depends = nd;
nd++;
}
// lookup component, or add it if it doesn't exist; return its index
int lookup_component(const char *name)
{
int i;
for (i=0; i<nc; i++)
if (strcmp(name, components[i].name) == 0) return i;
if (i == MAX_COMPONENTS) printf("Components limit exceeded\n");
strcpy(components[nc].name, name);
components[nc].depends = -1;
components[nc].installed = 0;
components[nc].dependencies = 0;
chain_last_component();
return nc - 1;
}
int get_word(char *buffer, const char **s)
{
if (**s == 0) return 0;
(*s)++;
while (**s && **s != ' ')
{
*buffer++ = **s;
(*s)++;
}
*buffer = 0;
return 1;
}
// install all components for component 'c' (in correct order) and
// then install component c
void install_component(int c)
{
int n, d, dc;
nid = 0;
init_queue();
init_inverted_subgraph();
construct_inverted_subgraph(c);
while ((n = dequeue()) != -1)
{
printf("Instaluji %s.\n", components[n].name);
components[n].installed = 1;
components[n].autoinstall = 1;
d = components[n].idepends;
while (d != -1)
{
dc = idependencies[d].depends;
components[dc].idependencies--;
if (components[dc].idependencies == 0) enqueue(dc);
d = idependencies[d].next;
}
d = components[n].depends;
while (d != -1)
{
dc = dependencies[d].depends;
components[dc].dependencies++;
d = dependencies[d].next;
}
}
}
// uninstall all components needed just for component 'c' and then
// uninstall 'c'
void uninstall_component(int c)
{
int d, dc, n;
components[c].installed = 0;
init_queue();
enqueue(c);
while ((n = dequeue()) != -1)
{
printf("Odstranuji %s.\n", components[n].name);
components[n].installed = 0;
d = components[n].depends;
while (d != -1)
{
dc = dependencies[d].depends;
components[dc].dependencies--;
if (!components[dc].dependencies &&
components[dc].autoinstall) enqueue(dc);
d = dependencies[d].next;
}
}
}
// list all components in alphabetical order
void list_components()
{
int c;
c = components[0].next;
while (c != -1)
{
if (components[c].installed)
printf("%s\n", components[c].name);
c = components[c].next;
}
}
void doit()
{
char buffer[80];
char word[MAX_NAME + 1];
const char *s;
int c, ic;
nd = 0;
nc = 1;
// insert component head
components[0].name[0] = 0;
components[0].next = -1;
while (1)
{
gets(buffer);
if (strcmp(buffer, "END") == 0) break;
if (strncmp(buffer, "DEPEND", 6) == 0)
{
s = buffer + 6;
get_word(word, &s);
ic = lookup_component(word);
while (get_word(word, &s))
{
c = lookup_component(word);
dependencies[nd].depends = c;
chain_last_dependency(ic);
}
}
else
if (strncmp(buffer, "INSTALL", 7) == 0)
{
s = buffer + 7;
get_word(word, &s);
c = lookup_component(word);
if (components[c].installed)
printf("%s je jiz nainstalovan.\n", components[c].name);
else
install_component(c);
components[c].autoinstall = 0;
}
else
if (strncmp(buffer, "REMOVE", 6) == 0)
{
s = buffer + 6;
get_word(word, &s);
c = lookup_component(word);
if (!components[c].installed)
printf("%s neni instalovan.\n", components[c].name);
else
if (components[c].autoinstall || components[c].dependencies)
printf("%s je stale potreba.\n", components[c].name);
else
{
uninstall_component(c);
}
}
else
if (strncmp(buffer, "LIST", strlen("LIST")) == 0)
{
list_components();
}
}
}
int main()
{
int i, n;
scanf("%i\n", &n);
for (i=0; i<n; i++) doit();
return 0;
}
#!/lhome/contest/bin/python
#
# Vzorove reseni ulohy zavislosti v Pythonu
# JK, verze 1, 21. dubna
# MT 1.1, 4. kvetna
import sys
import string
class component:
""" Tato trida obsahuje informace o jedne komponente """
explicit='#Explicit#' # konstanta znamenajici explicitni nacteni
def __init__(self):
# definuj promenne instance
self.needed=[] # seznam tech, ktere potrebujeme
self.supports=[] # seznam tech, kvuli kterym tu jsme
# vcetne specialni hodnoty '#Explicit#'
# supports==[] <=> komponenta neni nainstalovana
self.installed=0 # 0 neni, 1 je
def main():
# precti pocet zadani
line=sys.stdin.readline()
n=string.atoi(line)
while n>0:
vyres() # res jedno zadani
n=n-1
pkgs={} # prazdny slovnik. globalni promenna kam budeme ukladat
# prvky tridy component - komponenty o kterych neco vime
def vyres():
global pkgs # pristup ke globalni promenne
line=''
pkgs={}
while line!='END': # cti az k END
line=sys.stdin.readline() # cti jeden radek ze vstupu
line=string.strip(line) # odstran whitespace zepredu i zezadu
parts=string.split(line) # rozdel na pole
# print 'read %s' % line
if parts[0]=='DEPEND': # zavolej prislusny prikaz
command_depend(parts[1:])
elif parts[0]=='INSTALL':
command_install(parts[1]) ;
elif parts[0]=='REMOVE':
command_remove(parts[1]) ;
elif parts[0]=='LIST':
command_list() ;
elif parts[0]!='END': # neni-li to END, chyba, vyhod vyjimku
raise ValueError, '!!! unsupported command'
def command_depend(args): # realizuje prikaz depend
if pkgs.has_key(args[0]): # uz znama -> chyba
raise ValueError, '!!! %s already known' % args[0]
nc=component() # nova komponenta - konstruktor
seznam=args[1:]
seznam.sort() # setrid zavislosti podle abecedy
for i in seznam:
nc.needed.append(i) # pridej je do seznamu
pkgs[args[0]]=nc # pridej komponentu do pkgs
def isinstalled(arg): # vrat 1, pokud je komponenta nainstalovana
if not pkgs.has_key(arg):
return 0
return pkgs[arg].installed
def needs(arg): # vrat seznam komponent bezprostredne nutnych
if not pkgs.has_key(arg): # pro komponentu arg
return []
seznam=[]
seznam=pkgs[arg].needed
return seznam
def allneeds(arg): # seznam komponent, ktere je potreba nainstalovat pro
seznam=needs(arg) # komponentu arg, ve spravnem poradi
vse=[]
for i in seznam:
if not isinstalled(i):
vse.append(i)
dalsi=allneeds(i)
for j in dalsi:
if not j in vse:
vse.append(j)
vse.sort()
return vse
def install(arg):
if not pkgs.has_key(arg):
nc=component()
pkgs[arg]=nc
else:
nc=pkgs[arg]
for i in nc.needed:
if not arg in pkgs[i].supports:
pkgs[i].supports.append(arg)
nc.installed=1
def installexplicit(arg):
install(arg)
pkgs[arg].supports.append(component.explicit)
def isinstallable(arg):
seznam=needs(arg)
for i in seznam:
if not isinstalled(i):
# print 'Cannot install %s, %s is missing' % (arg,i)
return 0
return 1
def command_install(arg):
if isinstalled(arg):
print '%s je jiz nainstalovan.' % arg
if not component.explicit in pkgs[arg].supports:
pkgs[arg].supports.append(component.explicit)
return
seznam=allneeds(arg)
while len(seznam)>0:
# print 'seznam', seznam
for i in range(0,len(seznam)):
q=seznam[i]
if isinstallable(q):
if not isinstalled(q):
print 'Instaluji %s.' % q
install(q)
del seznam[i]
break
print 'Instaluji %s.' % arg
installexplicit(arg)
def command_list():
seznam=pkgs.keys()
seznam.sort()
for i in seznam:
if isinstalled(i):
print i
def command_remove(arg):
if not isinstalled(arg):
print '%s neni instalovan.' % arg
return
seznam=pkgs[arg].supports
if len(seznam)==0:
raise ValueError, '%s should have already be removed'
if len(seznam)!=1 or component.explicit!=seznam[0]:
print '%s je stale potreba.' % arg
return
pkgs[arg].supports=[]
remove(arg)
def remove(arg):
seznam=[arg] # v seznam jsou odstranitelne komponenty
# print '@ remove ', arg
while len(seznam)>0: # je jeste co odstranovat
i=seznam[0] # tuhle budeme odstranovat
del seznam[0]
sup=pkgs[i].supports # kdo nas potrebuje ?
if len(sup)>0:
# print '@ %s podporuje' % i, sup
continue # jeste nekdo -> zustan
print 'Odstranuji %s.' % i
kand=pkgs[i].needed # kandidati na odstraneni
for j in kand:
l=pkgs[j].supports
del l[l.index(i)] # odstran i ze seznamu
if len(l)==0: seznam.append(j)
pkgs[i].installed=0
seznam.sort()
# call the main function
main()
| ||
| ||