1.2~1.5

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;
+}