summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--1.2/beads.c64
-rw-r--r--1.2/friday.c48
-rw-r--r--1.2/ride.c32
-rw-r--r--1.3/dualpal.c50
-rw-r--r--1.3/milk2.c58
-rw-r--r--1.3/namenum.c58
-rw-r--r--1.3/palsquare.c56
-rw-r--r--1.3/transform.c109
-rw-r--r--1.4/barn1.c60
-rw-r--r--1.4/combo.c51
-rw-r--r--1.4/milk.c52
-rw-r--r--1.4/skidesign.c60
-rw-r--r--1.4/wormhole.c108
-rw-r--r--1.5/ariprog-alt.c78
-rw-r--r--1.5/ariprog.c72
-rw-r--r--1.5/milk3.c148
16 files changed, 1104 insertions, 0 deletions
diff --git a/1.2/beads.c b/1.2/beads.c
new file mode 100644
index 0000000..9f21528
--- /dev/null
+++ b/1.2/beads.c
@@ -0,0 +1,64 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: beads
+*/
+
+#include <stdio.h>
+#define MAXL 360
+
+int next(int t,int n)
+{
+ return (t==n-1)?0:(t+1);
+}
+
+int last(int t,int n)
+{
+ return (t==0)?(n-1):(t-1);
+}
+
+int main()
+{
+ FILE *fin=fopen("beads.in","r");
+ FILE *fout=fopen("beads.out","w");
+
+ int n;
+ int i,l,r;
+ int count,countr,max=0;
+ char beads[MAXL],color;
+ fscanf(fin,"%d%s",&n,beads);
+
+ for (i=0;i<n;i++){ //break between i-1 and i
+ count=0;countr=0;
+ for (l=last(i,n);l!=i;l=last(l,n)){ //search left
+ if (count==0){ //the first bead
+ color=beads[l];
+ ++count;
+ }
+ else if (beads[l]=='w'||color=='w'||beads[l]==color){ //have a white or is the same color
+ ++count;
+ if (color=='w') color=beads[l];
+ continue;
+ }
+ else break;
+ }
+ l=next(l,n); //the final leftmost
+ for (r=i;r!=l;r=next(r,n)){ //search right
+ if (countr==0){
+ color=beads[r];
+ ++countr;
+ }
+ else if (beads[r]=='w'||color=='w'||beads[r]==color){
+ ++countr;
+ if (color=='w') color=beads[r];
+ continue;
+ }
+ else break;
+ }
+ if (countr+count>max)
+ max=countr+count;
+ }
+ fprintf(fout,"%d\n",max);
+ return 0;
+}
+
diff --git a/1.2/friday.c b/1.2/friday.c
new file mode 100644
index 0000000..c0b2ceb
--- /dev/null
+++ b/1.2/friday.c
@@ -0,0 +1,48 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: friday
+*/
+
+#include <stdio.h>
+
+int isleap(int year)
+{
+ if (year%4==0 && (year%100!=0 || year%400==0))
+ return 1;
+ else
+ return 0;
+}
+
+const int DaysOfMonth[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
+
+int main()
+{
+ int n; //years eclipsed
+ int year;
+ int nDays[7]={0}; //number of Sat. to Fri.
+ int wDay=2+12; //the week day,1900.01.01 is Monday(2)
+ int i;
+ FILE *fin=fopen("friday.in","r");
+ FILE *fout=fopen("friday.out","w");
+
+ fscanf(fin,"%d",&n);
+ for (year=1900;year<1900+n;year++){
+ int type=isleap(year);
+ for (i=0;i<12;i++){
+ wDay%=7;
+ nDays[wDay]++;
+ wDay+=DaysOfMonth[type][i];
+ }
+ }
+ for (i=0;i<7;i++){
+ if (i)
+ fputc(' ',fout);
+ fprintf(fout,"%d",nDays[i]);
+ }
+ fputc('\n',fout);
+ fclose(fin);
+ fclose(fout);
+ return 0;
+}
+
diff --git a/1.2/ride.c b/1.2/ride.c
new file mode 100644
index 0000000..2a68239
--- /dev/null
+++ b/1.2/ride.c
@@ -0,0 +1,32 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: ride
+*/
+
+#include <stdio.h>
+#define MODN 47
+
+int main()
+{
+ FILE *fin=fopen("ride.in","r");
+ FILE *fout=fopen("ride.out","w");
+ int p[2]={1,1}; //2 products
+ char str[2][8];
+
+ int i,j;
+ fscanf(fin,"%s%s",str[0],str[1]);
+ for (i=0;i<2;i++){
+ for (j=0;str[i][j];j++){
+ p[i]*=str[i][j]-'A'+1;
+ p[i]%=MODN;
+ }
+ }
+ if (p[0]==p[1])
+ fprintf(fout,"GO\n");
+ else
+ fprintf(fout,"STAY\n");
+
+ return 0;
+}
+
diff --git a/1.3/dualpal.c b/1.3/dualpal.c
new file mode 100644
index 0000000..caa516e
--- /dev/null
+++ b/1.3/dualpal.c
@@ -0,0 +1,50 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: dualpal
+*/
+
+#include <stdio.h>
+
+int dualpal(int a) //check if a is dualpal
+{
+ int chk[32];
+ int l,base,i;
+ int count=0;
+ for (base=10;base>=2;base--){
+ l=0;
+ for (chk[0]=a;chk[l];++l){
+ chk[l+1]=chk[l]/base; //when chk[l+1]=0,the conversion is over
+ chk[l]%=base;
+ }
+ for (i=0;i<l/2;i++){
+ if (chk[i]!=chk[l-1-i])
+ break;
+ }
+ if (i>=l/2)
+ ++count;
+ if (count==2)
+ return 1;
+ }
+ return 0;
+}
+
+int main()
+{
+ int n,s;
+ FILE *fin=fopen("dualpal.in","r");
+ FILE *fout=fopen("dualpal.out","w");
+ fscanf(fin,"%d%d",&n,&s);
+ fclose(fin);
+
+ while (n){
+ ++s;
+ if (dualpal(s)){
+ fprintf(fout,"%d\n",s);
+ --n;
+ }
+ }
+
+ return 0;
+}
+
diff --git a/1.3/milk2.c b/1.3/milk2.c
new file mode 100644
index 0000000..4573334
--- /dev/null
+++ b/1.3/milk2.c
@@ -0,0 +1,58 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: milk2
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#define MAXN 5000
+#define max(a,b) ((a)>(b))?(a):(b)
+
+typedef struct
+{
+ int begin,end;
+}TimeTab,*pTimeTab;
+
+int comp(pTimeTab a,pTimeTab b)
+{
+ return a->begin-b->begin;
+}
+
+int main()
+{
+ int N;
+ int max_milk,max_nomilk;
+ int tBegin,tEnd;
+ int i;
+ TimeTab milktime[MAXN];
+
+ FILE *fin=fopen("milk2.in","r");
+ FILE *fout=fopen("milk2.out","w");
+ fscanf(fin,"%d",&N);
+ for (i=0;i<N;++i)
+ fscanf(fin,"%d%d",&milktime[i].begin,&milktime[i].end);
+ fclose(fin); //input complete
+ qsort(milktime,N,sizeof(TimeTab),(int(*)(const void*,const void*))comp);
+
+ max_milk=milktime[0].end-milktime[0].begin;
+ max_nomilk=0;
+ tBegin=milktime[0].begin;tEnd=milktime[0].end;
+ for (i=0;i<N;i++){
+ if (tEnd>=milktime[i].begin)
+ tEnd=max(tEnd,milktime[i].end);
+ else{
+ max_milk=max(tEnd-tBegin,max_milk);
+ max_nomilk=max(milktime[i].begin-tEnd,max_nomilk);
+ tBegin=milktime[i].begin;
+ tEnd=milktime[i].end;
+ }
+ if (i==N-1)
+ max_milk=max(tEnd-tBegin,max_milk);
+ }
+ fprintf(fout,"%d %d\n",max_milk,max_nomilk);
+ fclose(fout); //output complete
+ return 0;
+}
+
+
diff --git a/1.3/namenum.c b/1.3/namenum.c
new file mode 100644
index 0000000..dac1f44
--- /dev/null
+++ b/1.3/namenum.c
@@ -0,0 +1,58 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: namenum
+*/
+
+#include <stdio.h>
+#include <string.h>
+#define MAXL 16
+
+const char map[]="ABCDEFGHIJKLMNOPRSTUVWXYZ"; //use a 'Z' to map the end
+
+int mapped(int i,char c) //if mapped,return 0,otherwise return smaller(-1),or bigger(+1)
+{
+ int j;
+ if (i>=sizeof(map)/3) //i invalid
+ return 1;
+ for (j=i*3;j<(i+1)*3;j++){
+ if (map[j]==c) //mapped
+ return 0;
+ }
+ if (c>=map[j]) //c is too big
+ return 1;
+ else return -1;
+}
+
+int main()
+{
+ char target[MAXL],numstr[MAXL];
+ FILE *fin=fopen("namenum.in","r");
+ FILE *dict=fopen("dict.txt","r");
+ FILE *fout=fopen("namenum.out","w");
+ int has_answer=0;
+ fscanf(fin,"%s",numstr);
+ fclose(fin);
+ while (fscanf(dict,"%s",target)!=EOF){
+ int i;
+ if (mapped(numstr[0]-'2',target[0])==1) //too big
+ break;
+ for (i=0;numstr[i];++i){
+ if (mapped(numstr[i]-'2',target[i])!=0)
+ break;
+ }
+ if (numstr[i]||target[i]) //not matched
+ continue;
+ else{
+ has_answer=1;
+ fprintf(fout,"%s\n",target);
+ }
+ }
+ if (!has_answer)
+ fprintf(fout,"NONE\n");
+
+ fclose(dict);
+ fclose(fout);
+ return 0;
+}
+
diff --git a/1.3/palsquare.c b/1.3/palsquare.c
new file mode 100644
index 0000000..47f7593
--- /dev/null
+++ b/1.3/palsquare.c
@@ -0,0 +1,56 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: palsquare
+*/
+
+#include <stdio.h>
+
+const char numMap[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+int convert(int x,int base,int dest[])
+ //convert integer x to an array,return the length
+{
+ int i=0;
+ while (x){
+ dest[i++]=x%base;
+ x/=base;
+ }
+ return i;
+}
+
+int isReverse(int a[],int len) //check is an array is pan
+{
+ int i;
+ for (i=0;i<len/2;i++){
+ if (a[i]!=a[len-1-i])
+ return 0;
+ }
+ return 1;
+}
+
+int main()
+{
+ int i,j;
+ int base;
+ int origNum[32],aNum[32],origLen,len;
+ FILE *fin=fopen("palsquare.in","r");
+ FILE *fout=fopen("palsquare.out","w");
+ fscanf(fin,"%d",&base);
+ fclose(fin);
+ for (i=1;i<=300;i++){
+ len=convert(i*i,base,aNum);
+ if (isReverse(aNum,len)){
+ origLen=convert(i,base,origNum); //used to print i
+ for (j=origLen-1;j>=0;j--)
+ fprintf(fout,"%c",numMap[origNum[j]]);
+ fputc(' ',fout);
+ for (j=len-1;j>=0;j--) //print i*i
+ fprintf(fout,"%c",numMap[aNum[j]]);
+ fputc('\n',fout);
+ }
+ }
+ fclose(fout);
+ return 0;
+}
+
diff --git a/1.3/transform.c b/1.3/transform.c
new file mode 100644
index 0000000..cb12725
--- /dev/null
+++ b/1.3/transform.c
@@ -0,0 +1,109 @@
+/*
+ID: mytbk921
+LANG: C++
+TASK: transform
+*/
+
+#include <iostream>
+#include <fstream>
+#define MAXN 10
+
+using namespace std;
+
+typedef struct
+{
+ int n;
+ char pattern[MAXN][MAXN];
+}Tile,*pTile;
+
+void Rotate(pTile src,pTile dest)
+{
+ //to rotate 90 degrees
+ //(i,j) -> (j,n-1-i)
+ int tmp[MAXN][MAXN];
+ int n=src->n;
+ for (int i=0;i<n;i++){
+ for (int j=0;j<n;j++){
+ tmp[j][n-1-i]=src->pattern[i][j];
+ }
+ }
+ for (int i=0;i<n;i++){
+ for (int j=0;j<n;j++)
+ dest->pattern[i][j]=tmp[i][j];
+ }
+}
+
+void reflect(pTile src,pTile dest)
+{
+ int tmp[MAXN][MAXN];
+ int n=src->n;
+ for (int i=0;i<n;i++){
+ for (int j=0;j<n;j++)
+ tmp[i][n-1-j]=src->pattern[i][j];
+ }
+ for (int i=0;i<n;i++){
+ for (int j=0;j<n;j++)
+ dest->pattern[i][j]=tmp[i][j];
+ }
+}
+
+int isequal(pTile a,pTile b)
+{
+ if (a->n != b->n)
+ return 0;
+ int n=a->n;
+ for (int i=0;i<n;i++)
+ for (int j=0;j<n;j++)
+ if (a->pattern[i][j]!=b->pattern[i][j])
+ return 0;
+ return 1;
+}
+
+int main()
+{
+ int n;
+ Tile a[2];
+ ifstream fin("transform.in");
+ fin >> n;
+ for (int i=0;i<2;i++){
+ for (int j=0;j<n;j++)
+ for (int k=0;k<n;k++)
+ fin >> a[i].pattern[j][k];
+ a[i].n=n;
+ }
+ fin.close(); //input complete
+
+ ofstream fout("transform.out");
+ for (int i=1;i<=3;i++){
+ Rotate(a+0,a+0);
+ if (isequal(a,a+1)){
+ fout << i << endl;
+ return 0;
+ }
+ }
+ Rotate(a+0,a+0); //recover a
+ reflect(a+0,a+0);
+ if (isequal(a+0,a+1)){
+ fout << 4 << endl;
+ return 0;
+ }
+ for (int i=0;i<3;i++){
+ Rotate(a+0,a+0);
+ if (isequal(a+0,a+1)){
+ fout << 5 << endl;
+ return 0;
+ }
+ }
+ Rotate(a+0,a+0);
+ reflect(a+0,a+0);
+ if (isequal(a+0,a+1)){
+ fout << 6 << endl;
+ return 0;
+ }
+ else{
+ fout << 7 << endl;
+ return 0;
+ }
+ fout.close();
+}
+
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;
+}
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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-03 18:13:31 +0000