From ad4e2420e822b8a115aac6124307b89447578782 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Mon, 16 Apr 2018 19:06:32 +0800
Subject: 1.2~1.5

---
 1.5/ariprog-alt.c |  78 ++++++++++++++++++++++++++++
 1.5/ariprog.c     |  72 ++++++++++++++++++++++++++
 1.5/milk3.c       | 148 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 298 insertions(+)
 create mode 100644 1.5/ariprog-alt.c
 create mode 100644 1.5/ariprog.c
 create mode 100644 1.5/milk3.c

(limited to '1.5')

diff --git a/1.5/ariprog-alt.c b/1.5/ariprog-alt.c
new file mode 100644
index 0000000..68e437e
--- /dev/null
+++ b/1.5/ariprog-alt.c
@@ -0,0 +1,78 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: ariprog
+*/
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+int cmp(const void* a, const void* b)
+{
+    return *(int*)a - *(int*)b;
+}
+
+int main()
+{
+    FILE *fin, *fout;
+    int n,m,setSize,i,j,diff,step,maxdiff,count=0;
+    int myset[251*251];
+    
+    fin = fopen("ariprog.in", "r");
+    fout = fopen("ariprog.out", "w");
+    
+    fscanf(fin, "%d%d", &n, &m);
+    fclose(fin);
+    
+    setSize = 0;
+    for (i=0; i<=m; i++){
+        myset[i] = i*i;
+    }
+    setSize = m+1;
+    for (i=1; i<=m; i++){
+        for (j=i; j<=m; j++){
+            myset[setSize] = myset[i]+myset[j];
+            setSize++;
+        }
+    }
+    qsort(myset, setSize, sizeof(myset[0]), cmp);
+    maxdiff = myset[setSize-1]/(n-1);
+
+    if (n>=6){
+        step = 12;
+    }else if (n>=4){
+        step = 4;
+    }else{
+        step = 1;
+    }
+    
+    for (diff=step; diff<=maxdiff; diff+=step){
+        for (i=0; i<setSize; i++){
+            if (i>0 && myset[i]==myset[i-1]){
+                continue;
+            }
+            int curr = myset[i];
+            for (j=1; j<n; j++){
+                curr += diff;
+                if (bsearch(&curr, myset, setSize, sizeof(myset[0]), cmp)==NULL){
+                    break;
+                }
+            }
+            if (j<n){
+                continue;
+            }else{
+                count++;
+                fprintf(fout, "%d %d\n", myset[i], diff);
+            }
+        }
+    }
+    if (count==0){
+        fprintf(fout, "NONE\n");
+    }
+    
+    fclose(fout);
+    return 0;
+}
+
+            
diff --git a/1.5/ariprog.c b/1.5/ariprog.c
new file mode 100644
index 0000000..385fe8a
--- /dev/null
+++ b/1.5/ariprog.c
@@ -0,0 +1,72 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: ariprog
+*/
+
+#include <stdio.h>
+
+int squares[251];
+int notpass[251*251*2+1]={};
+int n,m;
+
+int check(int x) //check if x is p^2+q^2
+{
+	int i,j;
+	if (notpass[x]==1)
+		return 0;
+	if (notpass[x]==-1)
+		return 1;
+	for (i=0; i<=m&&squares[i]<=x/2; i++){
+		for (j=m; j>=i; j--){
+			if (squares[i]+squares[j]==x){
+				notpass[x]=-1;
+				return 1;
+			}
+			if (squares[i]+squares[j]<x)
+				break;
+		}
+	}
+	notpass[x]=1;
+	return 0;
+}
+
+int test(int a, int b) //test if a to a+nb can pass the ckecks
+{
+//	printf("test %d %d\n",a,b);
+	int i;
+	for (i=0; i<=n; i++){
+		if (!check(a)){
+//			printf("%d failed\n",a);
+			return 0;
+		}
+		a += b;
+	}
+	return 1;
+}
+
+int main()
+{
+	int a,b;
+	int found=0;
+	FILE *fin=fopen("ariprog.in","r");
+	FILE *fout=fopen("ariprog.out","w");
+	fscanf(fin, "%d%d", &n, &m);
+	for (a=0;a<=m;a++)
+		squares[a]=a*a;
+	n--;
+	fclose(fin);
+	for (b=1; b*n<=squares[m]*2; b++){
+		for (a=0; a+b*n<=squares[m]*2; a++){
+			if (test(a,b)){
+				fprintf(fout,"%d %d\n",a,b);
+				found=1;
+			}
+		}
+	}
+	if (!found)
+		fprintf(fout,"NONE\n");
+	fclose(fout);
+	return 0;
+}
+
diff --git a/1.5/milk3.c b/1.5/milk3.c
new file mode 100644
index 0000000..f50a61d
--- /dev/null
+++ b/1.5/milk3.c
@@ -0,0 +1,148 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: milk3
+*/
+
+#include <stdio.h>
+#include <string.h>
+
+int possible[21];
+int searched[21][21][21][3];
+
+typedef struct
+{
+    int amount;
+    int capacity;
+}bucket;
+
+void test_0(bucket, bucket, bucket);
+void test_1(bucket, bucket, bucket);
+void test_2(bucket, bucket, bucket);
+
+void pour(const bucket *a, const bucket *b, bucket *_a, bucket *_b)
+{
+    _a->capacity = a->capacity;
+    _b->capacity = b->capacity;
+    
+    if (b->amount+a->amount<=b->capacity){
+        _a->amount = 0;
+        _b->amount = a->amount+b->amount;
+    }else{
+        _a->amount = a->amount-(b->capacity-b->amount);
+        _b->amount = b->capacity;
+    }
+}
+    
+void test_0(bucket a, bucket b, bucket c)
+{
+    if (a.amount==0){
+        possible[c.amount] = 1;
+        return;
+    }
+    
+    if (searched[a.amount][b.amount][c.amount][0]){
+        return;
+    }else{
+        searched[a.amount][b.amount][c.amount][0] = 1;
+    }
+    
+    bucket _a,_b,_c;
+    if (b.amount!=b.capacity){
+        pour(&a, &b, &_a, &_b);
+        if (_a.amount==0){
+            possible[c.amount] = 1;
+        }
+        test_1(_a, _b, c);
+        test_2(_a, _b, c);
+    }
+    if (c.amount!=c.capacity){
+        pour(&a, &c, &_a, &_c);
+        if (_a.amount==0){
+            possible[_c.amount] = 1;
+        }
+        test_1(_a, b, _c);
+        test_2(_a, b, _c);
+    }
+}
+
+void test_1(bucket a, bucket b, bucket c)
+{
+    if (b.amount==0){
+        return;
+    }
+    
+    if (searched[a.amount][b.amount][c.amount][1]){
+        return;
+    }else{
+        searched[a.amount][b.amount][c.amount][1] = 1;
+    }
+    
+    bucket _a,_b,_c;
+    if (a.amount!=a.capacity){
+        pour(&b, &a, &_b, &_a);
+        test_0(_a, _b, c);
+        test_2(_a, _b, c);
+    }
+    if (c.amount!=c.capacity){
+        pour(&b, &c, &_b, &_c);
+        test_0(a, _b, _c);
+        test_2(a, _b, _c);
+    }
+}
+
+void test_2(bucket a, bucket b, bucket c)
+{
+    if (c.amount==0){
+        return;
+    }
+    
+    if (searched[a.amount][b.amount][c.amount][2]){
+        return;
+    }else{
+        searched[a.amount][b.amount][c.amount][2] = 1;
+    }
+    
+    bucket _a,_b,_c;
+    if (a.amount!=a.capacity){
+        pour(&c, &a, &_c, &_a);
+        test_0(_a, b, _c);
+        test_1(_a, b, _c);
+    }
+    if (b.amount!=b.capacity){
+        pour(&c, &b, &_c, &_b);
+        test_0(a, _b, _c);
+        test_1(a, _b, _c);
+    }
+}
+
+int main()
+{
+    FILE *fin, *fout;
+    bucket a, b, c;
+    int i;
+    
+    a.amount = b.amount = 0;
+    
+    fin = fopen("milk3.in", "r");
+    fout = fopen("milk3.out", "w");
+    fscanf(fin, "%d%d%d", &a.capacity, &b.capacity, &c.capacity);
+    fclose(fin);
+    
+    c.amount = c.capacity;
+
+    memset(possible, 0, sizeof(possible));
+    memset(searched, 0, sizeof(searched));
+
+    possible[c.amount] = 1;
+    test_2(a, b, c);
+
+    for (i=0; i<c.amount; i++){
+        if (possible[i]){
+            fprintf(fout, "%d ", i);
+        }
+    }
+    fprintf(fout, "%d\n", c.amount);
+    fclose(fout);
+    return 0;
+}
-- 
cgit v1.2.3