summaryrefslogtreecommitdiff
path: root/1.5
diff options
context:
space:
mode:
Diffstat (limited to '1.5')
-rw-r--r--1.5/ariprog-alt.c78
-rw-r--r--1.5/ariprog.c72
-rw-r--r--1.5/milk3.c148
3 files changed, 298 insertions, 0 deletions
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;
+}