diff options
Diffstat (limited to '1.4')
-rw-r--r-- | 1.4/barn1.c | 60 | ||||
-rw-r--r-- | 1.4/combo.c | 51 | ||||
-rw-r--r-- | 1.4/milk.c | 52 | ||||
-rw-r--r-- | 1.4/skidesign.c | 60 | ||||
-rw-r--r-- | 1.4/wormhole.c | 108 |
5 files changed, 331 insertions, 0 deletions
diff --git a/1.4/barn1.c b/1.4/barn1.c new file mode 100644 index 0000000..65039b3 --- /dev/null +++ b/1.4/barn1.c @@ -0,0 +1,60 @@ +/* +ID: mytbk921 +LANG: C +TASK: barn1 +*/ + +#include <stdio.h> +#define MAXS 200 + +int main() +{ + int MBoards,nStalls,nCows; + int l,r,ngaps,occupied; + int stalls[MAXS+10]={},gaps[MAXS]; + int i,j; + + FILE *fin=fopen("barn1.in","r"); + FILE *fout=fopen("barn1.out","w"); + fscanf(fin,"%d%d%d",&MBoards,&nStalls,&nCows); + l=nStalls; r=0; //initial the left&right bound + for (i=0;i<nCows;++i){ + fscanf(fin,"%d",&j); + stalls[j]=1; + if (j<l) //update the bound + l=j; + if (j>r) + r=j; + } + fclose(fin); + + ngaps=0; + for (i=l;i<=r;i++){ + if (!stalls[i]){ //have a gap + for (j=i;!stalls[j];j++) + ; + gaps[ngaps++]=j-i; + i=j; //the i will continue + } + } + //selection sort + for (i=0;i<ngaps&&i<MBoards-1;i++){ //select the largest gaps + int max=i; //form gaps[i] to gaps[ngaps-1] + for (j=i+1;j<ngaps;j++){ + if (gaps[j]>gaps[max]) + max=j; + } + int tmp=gaps[max]; + gaps[max]=gaps[i]; + gaps[i]=tmp; //swap finished + } + + //calculate + occupied=r-l+1; + for (i=0;i<MBoards-1&&i<ngaps;i++) + occupied-=gaps[i]; + + fprintf(fout,"%d\n",occupied); + return 0; +} + diff --git a/1.4/combo.c b/1.4/combo.c new file mode 100644 index 0000000..7c5b3d1 --- /dev/null +++ b/1.4/combo.c @@ -0,0 +1,51 @@ +/* +ID: mytbk921 +LANG: C +TASK: combo +*/ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +int matches(int a[], int b[], int N) +{ + int i; + for (i = 0; i < 3; i++) { + if (abs(a[i]-b[i]) <= 2 || + N - abs(a[i]-b[i]) <= 2) + continue; + else + return 0; + } + return 1; +} + +int main() +{ + FILE *fin, *fout; + int farmer[3], master[3], test[3]; + int N, i, count = 0; + + fin = fopen("combo.in", "r"); + fout = fopen("combo.out", "w"); + + fscanf(fin, "%d", &N); + for (i = 0; i<3; i++) + fscanf(fin, "%d", &farmer[i]); + for (i = 0; i<3; i++) + fscanf(fin, "%d", &master[i]); + fclose(fin); + + for (test[0] = 1; test[0] <= N; test[0]++) + for (test[1] = 1; test[1] <= N; test[1]++) + for (test[2] = 1; test[2] <= N; test[2]++) + if (matches(farmer, test, N) || matches(master, test, N)) + count++; + + fprintf(fout, "%d\n", count); + fclose(fout); + return 0; +} + + diff --git a/1.4/milk.c b/1.4/milk.c new file mode 100644 index 0000000..f256d72 --- /dev/null +++ b/1.4/milk.c @@ -0,0 +1,52 @@ +/* +ID: mytbk921 +LANG: C +TASK: milk +*/ + +#include <stdio.h> +#include <stdlib.h> +#define MAXF 5000 + +typedef struct +{ + int price; + int amount; +}FARMER; + +int cmp(const void* x,const void* y) +{ + return ((FARMER*)x)->price-((FARMER*)y)->price; +} + +int main() +{ + int Total,nFarmers,minPrice; + FARMER farmers[MAXF]; + int i; + FILE *fin=fopen("milk.in","r"); + FILE *fout=fopen("milk.out","w"); + + fscanf(fin,"%d%d",&Total,&nFarmers); + for (i=0;i<nFarmers;i++) + fscanf(fin,"%d%d",&farmers[i].price,&farmers[i].amount); + fclose(fin); + qsort(farmers,nFarmers,sizeof(FARMER),cmp); + + minPrice=0; + for (i=0;Total&&i<nFarmers;i++){ + if (farmers[i].amount>Total){ + minPrice+=Total*farmers[i].price; + Total=0; + } + else{ + minPrice+=farmers[i].price*farmers[i].amount; + Total-=farmers[i].amount; + } + } + + fprintf(fout,"%d\n",minPrice); + fclose(fout); + return 0; +} + diff --git a/1.4/skidesign.c b/1.4/skidesign.c new file mode 100644 index 0000000..349d304 --- /dev/null +++ b/1.4/skidesign.c @@ -0,0 +1,60 @@ +/* + ID: mytbk921 + LANG: C + TASK: skidesign +*/ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +int compare(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +int calc_sum(int min, int N, int a[]) +{ + int sum = 0; + int i; + + for (i = 0; i < N && a[i] < min; i++) { + int diff = min - a[i]; + sum += diff * diff; + } + + for (i = N-1; i >= 0 && a[i] - min > 17; i--) { + int diff = a[i] - min - 17; + sum += diff * diff; + } + return sum; +} + +int main() +{ + FILE *fin, *fout; + int N; + int m[1000]; + int sum, ans; + int i; + + fin = fopen("skidesign.in", "r"); + fout = fopen("skidesign.out", "w"); + + fscanf(fin, "%d", &N); + for (i = 0; i<N; i++) + fscanf(fin, "%d", &m[i]); + fclose(fin); + qsort(m, N, sizeof(int), compare); + + ans = calc_sum(m[0], N, m); + for (i = m[N-1]; i > 0; i--) { + sum = calc_sum(m[0]+i, N, m); + if (sum < ans) + ans = sum; + } + + fprintf(fout, "%d\n", ans); + fclose(fout); + return 0; +} diff --git a/1.4/wormhole.c b/1.4/wormhole.c new file mode 100644 index 0000000..551616a --- /dev/null +++ b/1.4/wormhole.c @@ -0,0 +1,108 @@ +/* + ID: mytbk921 + LANG: C + TASK: wormhole +*/ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +int compare(const void *a, const void *b) +{ + return *(int*)a - *(int*)b; +} + +int willstuck(int n, int holes[][2], int hmap[]) +{ + int i, j; + int time, cur; + for (i = 0; i < n; i++) { + /* try to enter hole i */ + time = 0; + cur = i; + while (time < n) { + cur = hmap[cur]; + for (j = cur+1; j < n; j++) { + if (holes[j][1] == holes[cur][1]) { + cur = j; + break; + } + } + if (j == n) + break; + else + time++; + } + if (time == n) + return 1; + } + return 0; +} + +int nextmap(int n, int hmap[]) +{ + int i, j; + int has_next = 0; + for (i = n-1; i >= 0; i--) { + if (hmap[i] > i) { + for (j = hmap[i]+1; j < n; j++) { + if (hmap[j] == -1) { + has_next = 1; + hmap[hmap[i]] = -1; + hmap[i] = j; + hmap[j] = i; + break; + } + } + if (!has_next) { + hmap[hmap[i]] = -1; + hmap[i] = -1; + } + } + if (has_next) + break; + } + for (i++; i < n; i++) { + if (hmap[i] == -1) { + for (j = i+1; hmap[j] != -1; j++) + ; + hmap[i] = j; + hmap[j] = i; + } + } + return has_next; +} + +int main() +{ + FILE *fin, *fout; + int N; + int holes[12][2]; + int hmap[12]; + int count = 0; + int i; + + fin = fopen("wormhole.in", "r"); + fout = fopen("wormhole.out", "w"); + + fscanf(fin, "%d", &N); + for (i = 0; i<N; i++) + fscanf(fin, "%d%d", &holes[i][0], &holes[i][1]); + fclose(fin); + qsort(holes, N, sizeof(int)*2, compare); + + for (i = 0; i < N; i += 2) { + hmap[i] = i+1; + hmap[i+1] = i; + } + + do { + if (willstuck(N, holes, hmap)) + count++; + } while (nextmap(N, hmap)); + + fprintf(fout, "%d\n", count); + fclose(fout); + return 0; +} |