第22次ITSA答案參考

題目連結: https://db.tt/tg3FeNrb (右鍵開新視窗)
1

#include<stdio.h>
void minheap(int *n[1000],int size){
int i;
while(1){
    int flag=1;
    for(i=1;i<=size;i++){
        if(n[i]>n[i*2+1]){int t; t=n[i],n[i]=n[i*2+1],n[i*2+1]=t; flag=0;}
        if(n[i]>n[i*2]){int t; t=n[i],n[i]=n[i*2],n[i*2]=t; flag=0;}
    }
    if(flag) break;
}

}

int main(){
int n[1000],size=0,num,i;
for(i=0;i<1000;i++) n[i]=500;
char order;
while(scanf("%c",&order)!=EOF){
    if(order=='a'){
        scanf("%d",&num);
        n[++size]=num;
        minheap(n,size);
        printf("The min-heap is of size %d and the current minimum is %d a\n",size,n[1]);
    }else if(order=='b'){
        n[1]=n[size];
        n[size]=500;
        --size;
        minheap(n,size);
        printf("The min-heap is of size %d and the current minimum is %d b\n",size,n[1]);
    }else if(order=='c'){
        for(i=1;i<=size;i++) {
            if(i!=1) printf(" ");
            printf("%d",n[i]);
        }
    }else if(order=='d'){
        break;
    }
}

return 0;
}

2

#include<stdio.h>
int n[90000],top=0,min=1e9;
int search(int s,int sum){
int ns,nsum,i;
if(s==top-1||s==top-2) { /* printf("*%d\n",sum)*/; if(sum<=min) min=sum; return 0;}

for(i=1;i<=3;i++){
    if((s+i)<top){
        //printf("i=%d s=%d sum=%d\n",i,s,sum);
        ns=s+i,nsum=sum+n[s+i];
        //printf("          n s=%d sum=%d,top=%d\n",ns,nsum,top);
        search(ns,nsum);

    }
}
    return 0;
}

int main(){
    int tmp;
    while(scanf("%d",&tmp)&&tmp) n[top++]=tmp;
    //while(scanf("%d",&tmp)!=EOF) n[top++]=tmp;
    search(0,n[0]);
    search(1,n[1]);
    printf("%d\n",min);
    return 0;
}

3

#include<stdio.h>
#include<string.h>
int n,map[5000][5000]={0},time[5000]={0},top=0;
int max=0;
void search(int mask,int sum,int size){
    if(size>=top) return;
    if(sum>max) max=sum;
    //printf("mask=%d sum %d size %d\n",mask,sum,size);
    int i,j;
    int max=0;
    for(i=0;i<top;i++){
        int ch=-1,max=0;
        for(j=0;j<top;j++){
            if(map[i][j]!=0&&(mask&(1<<j))&&(mask&(1<<i))){
                if(time[j]>max) max=time[j],ch=j;
            }
        }
        if(ch!=-1){
            mask-=1<<i;
            mask-=1<<ch;
            //printf(" (%d,%d) ",i,ch);
            search(mask,time[ch]+time[i],++size);
        }
    }




    return ;
}

void task (char t[100]){
    //printf("task\n");
    int c=0,tt=0,tn=0;
    while(t[++c]!=','){
        tt*=10;
        tt+=t[c]-'0';
    }

    while(t[++c]){
        tn*=10;
        tn+=t[c]-'0';
    }

    time[tt-1]=tn;
    top++;
    //printf("**task=%d time=%d\n",tt,time);

}

void prec (char p[100]){
    //printf("prec\n");
    int c=0,tb=0,ta=0;
    while(p[++c]!=','){
        tb*=10;
        tb+=p[c]-'0';
    }
    c++;
    while(p[++c]){
        ta*=10;
        ta+=p[c]-'0';
    }

    map[ta-1][tb-1]=1;
    //printf("  pp %d %d\n",tb,ta);
}

int main(){
    char input[100];
    int i,j;

    while(gets(input)){
        if(strcmp(input,"end")==0) break;
        char left[100],right[100]={0};
        int n1=0,n2=0;
        while(input[n1]!=':') left[n1]=input[n1],n1++;
        left[n1++]='\0';
        while(input[n1]) right[n2++]=input[n1++];
        right[n2]='\0';

        if(strcmp(left,"Process")==0){
            int sum=0,n3=0;
            while(right[n3]) sum*=10,sum+=right[n3++]-'0';
            n=sum;
            //printf("sum=%d\n",sum);
        }else if(strcmp(left,"Task")==0){
            task(right);
        }else if(strcmp(left,"Prec")==0){
            prec(right);
        }
    }

    /*for(i=0;i<top;i++) printf("%d ",time[i]);
    printf("  top=%d\n",top);

    for(i=0;i<top;i++){
        for(j=0;j<top;j++)
            printf("%d ",map[i][j]);
        puts("");
    }*/

    int mask=~(~0<<top);
    search(mask,0,0);
    printf("%d\n",max);
    return 0;
}

4

#include<stdio.h>
char ans[100][100];
int top=0;
int map[100][100],n,min=1e9;
int star,end;

int search(int a[n],int p,int size,int mask){
    int i,c;
    mask|=1<<p;
    a[size++]=p;

    if(size>=n) return 1;
/*
printf("p=%d size=%d mark=%d\n",p,size+1,mask);
for(i=0;i<size;i++) printf("%d ",a[i]);
puts("");*/
    if(p==end) {
        if(size<min){
            min=size;
            top=0;
            c=0;
            for(i=0;i<size;i++){
                if(i!=0) ans[top][c++]=',';
                ans[top][c++]=a[i]+'0';
            }
            ans[top++][c]='\0';
        }else if(size==min){
            c=0;
            for(i=0;i<size;i++){
                if(i!=0) ans[top][c++]=',';
                ans[top][c++]=a[i]+'0';
            }
            ans[top++][c]='\0';
        }
            /*printf("ans min=%d ",min);
            for(i=0;i<size;i++) printf("%d ",a[i]);
            puts("");*/

        return 0;
    }

    for(i=0;i<n;i++){
        if(map[p][i]==1&&(mask&(1<<i))==0)
            search(a,i,size,mask);
    }

}


int main(){
    scanf("%d,%d,%d",&n,&star,&end);
    int i,j;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&map[i][j]);

    int a[n];
    search(a,star,0,0);

    for(i=0;i<top;i++)
        printf("%s\n",ans[i]);

    return 0;
}

5

#include<stdio.h>
int main(){
while(1){
int n[100],top=0,num;
while(scanf("%d",&num)==1){
if(num==-999999) break;
n[top++]=num;
}
int i,j,max=n[0];
for(i=0;i<top;i++){
    int r=n[i];
    for(j=i+1;j<top;j++){
        r*=n[j];
        if(r>=max) max=r;
    }
}
printf("%d\n",max);
}
return 0;
}