A2.

#include "A2.h" FILE *in, *out; int n, k, data_num, maximum, minimum; int **data; int init() { in = fopen("hopscotch.in", "rt"); if(in == NULL) { return 0; } out = fopen("hopscotch.out", "wt"); if(out == NULL) { return 0; } fscanf(in, "%d", &data_num); data = new int*[MAXNUM]; for(int i = 0;i<100;i++) data[i] = new int[MAXNUM]; return 1; } int getInput() { fscanf(in, "%d %d", &n, &k); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { fscanf(in, "%d", &data[i][j]); } } return 1; } int uninit() { fclose(in); fclose(out); for(int i=0;i<100;i++) delete []data[i]; delete []data; return 1; } void main() { if(!init()) { printf("Error while initlizing.\n"); return; } for(int i=0;i<data_num;i++) { getInput(); fprintf(out, "%d\n", findMaxCriticalPath(data, n, k, 0, n*n)); } if(!uninit()) { printf("Error while uninitlizing.\n"); return; } }     /////////////////////////////////////////////////////////////////////////////////////

//imcc add //A2.h //end #include <stdio.h> #define UNDEFINED -1 #define MAXNUM 101 #define INVALID_WEIGHT -1 int findMaxCriticalPath(int **data, int n, int k, int start, int end); void topologicalSort(int **data, int *table, int n); int findMaxCriticalPath(int **data, int n, int k, int start, int end) { int size = n*n + 1; int** g = new int*[size]; for(int i=0;i<size;i++) { g[i] = new int[size]; for(int j=0;j<size;j++) g[i][j] = INVALID_WEIGHT; } for(i=0;i<n;i++) for(int j=0;j<n;j++) { int IsEndPoint = 1; for(int a=1;a<=k;a++) for(int b=0;b<4;b++) { int x, y; switch(b) { case 0: x = - a; y = 0; break; case 1: x = a; y = 0; break; case 2: x = 0; y = -a; break; case 3: x = 0; y = a; break; default: x = y = 0; break; } if(i+x>=0 && j+y>=0 && i+x<n && j+y<n && data[i][j] < data[i+x][j+y]) { g[i*n + j][(i+x)*n +j+y] = data[i][j]; IsEndPoint = 0; } } if(IsEndPoint) { g[i*n + j][n*n] = data[i][j]; } } for(i=0;i<size;i++) g[i][0] = INVALID_WEIGHT; int *table = new int[size]; //debug info /* FILE *f = fopen("temp.txt", "wt"); for(i=0;i<size;i++) table[i] = i; for(i=0;i<size;i++) { for(int j=0;j<size;j++) fprintf(f, "%2d ", g[i][j]); fprintf(f, "\n"); } for(i=0;i<size;i++) fprintf(f, "%2d ", table[i]); fprintf(f, "\n\n");*/ topologicalSort(g, table, size); /* for(i=0;i<size;i++) { for(int j=0;j<size;j++) fprintf(f, "%2d ", g[i][j]); fprintf(f, "\n"); } for(i=0;i<size;i++) fprintf(f, "%2d ", table[i]); fprintf(f, "\n\n");*/ int *c = new int[size]; c[0] = 0; int index = size - 1; for(i=1;i<size;i++) { c[i] = INVALID_WEIGHT; for(int j=0;j<i;j++) if(g[j][i]!=INVALID_WEIGHT && c[i] < g[j][i]+c[j]) c[i] = g[j][i] + c[j]; if(table[i] == end) { index = i; break; } } /* for(i=0;i<size;i++) fprintf(f, "%2d ", c[i]); fprintf(f, "\n");*/ int maximum = c[index]; delete []c; delete []table; //fclose(f); for(i=0;i<size;i++) delete []g[i]; delete []g; return maximum; } void topologicalSort(int **data, int *table, int n) { for(int i=0;i<n-1;i++) for(int j=i;j<n;j++) { int noOut = 1; for(int k=i;k<n;k++) if(data[k][j]!=INVALID_WEIGHT) { noOut = 0; break; } if(noOut && j!=i) { for(int k=0;k<n;k++) { int temp = data[k][j]; data[k][j] = data[k][i]; data[k][i] = temp; } for(k=i+1;k<n;k++) { int temp = data[i][k]; data[i][k] = data[j][k]; data[j][k] = temp; } int temp = table[j]; table[j] = table[i]; table[i] = temp; } else if(noOut) break; } }

A4.

#include <stdio.h> #include <fstream.h> #include "LargeInteger.h" #define UNDEFINED NULL typedef CULongInt<> LongInt; //input and output file FILE *in; ofstream out("ticket.out"); LongInt *c[100][100][100]; //init function int init() { in = fopen("ticket.in", "rt"); if(in == NULL) { return 0; } for(int i=0;i<100;i++) for(int j=0;j<100;j++) for(int k=0;k<100;k++) c[i][j][k] = UNDEFINED; return 1; } //uninit function int uninit() { fclose(in); //fclose(out); for(int i=0;i<100;i++) for(int j=0;j<100;j++) for(int k=0;k<100;k++) { if(c[i][j][k]) delete c[i][j][k]; } return 1; } //get the next input from input file int getNextInput(int *m, int *n) { fscanf(in, "%d %d\n", m, n); if(*m == 0 && *n == 0) { return 0; } return 1; } //recursive factorial function LongInt f(int x) { LongInt ans = 1; for(int i=0;i<x;i++) { ans = ans * (x-i); } return ans; } //recursive counting function LongInt C(int m, int n, int k) { if(c[m][n][k] == UNDEFINED) { c[m][n][k] = new LongInt(); if(n == 0) *c[m][n][k] = f(m); else if(m == 0 && n <= k) *c[m][n][k] = f(n); else if(k == 0) { *c[m][n][k] = C(m-1, n, k+1) * m; } else { *c[m][n][k] = C(m-1, n, k+1) * m + C(m, n-1, k-1) * n; } } return *c[m][n][k]; } //main function void main() { //init first if(!init()) { printf("Error while initializing.\n"); return; } //main loop int m, n, counter = 0; while(getNextInput(&m, &n)) { counter ++; if(m < n) { printf("Invalid input, can't arrange in this case.\n"); return; } out<<"Test #"<<counter<<":\n"; out<<C(m, n, 0)<<endl; } //uninit at last uninit(); }

/////////////////////////////////////////////////////////////////////////////////////

//imcc add //LargeInteger.h //add end //CULongInt, based on the CLargeUInteger writtten by WindCat9 //bow to WindCat9~~ #include <MEMORY.H> #define MAX_DIGIT 1000000000 template <unsigned int length = 128> class CULongInt { public: CULongInt(){ memset(data, 0, sizeof(data)); } CULongInt(const CULongInt& right) { for(unsigned int i = 0; i < length; i++) data[i] = right.data[i]; } CULongInt(unsigned __int32 right) { memset(data, 0, sizeof(data)); data[0] = right % MAX_DIGIT; data[1] = right / MAX_DIGIT; for(unsigned int i = 2; i < length; i++) data[i] = 0; } virtual ~CULongInt() {} friend ostream & operator << ( ostream & out, const CULongInt& right) { int index = length - 1; while (index >= 0 && right.data[index] == 0) index --; if(index < 0) out << 0; else for(; index >= 0; index --) { if(right.data[index] == 0) out << "000000000"; else out << (unsigned int)right.data[index]; } return out; } CULongInt& operator = (const CULongInt & right) { for(unsigned int i = 0; i < length; i++) data[i] = right.data[i]; return *this; } CULongInt operator + (const CULongInt & right) const { CULongInt integer; for(unsigned int i = 0; i < length; i++) integer.data[i] = data[i] + right.data[i]; for(i = 0; i < length; i++) if(integer.data[i] >= MAX_DIGIT) { integer.data[i + 1] += integer.data[i] / MAX_DIGIT; integer.data[i] = integer.data[i] % MAX_DIGIT; } return integer; } CULongInt operator * (const CULongInt & right) const { CULongInt integer; //for every right number unsigned length1 = length - 1; while(length1 > 0 && right.data[length1 - 1] == 0) length1 --; unsigned length2 = length - 1; while(length2 > 0 && data[length2 - 1] == 0) length2 --; for(unsigned int i = 0; i < length1; i++) { for(unsigned int j = 0; j < length2; j++) { if(i + j < length) { __int64 temp = (__int64)data[j] * (__int64)right.data[i]; integer.data[j + i] += (__int32) (temp % MAX_DIGIT); integer.data[j + i + 1] += (__int32) (temp / MAX_DIGIT); } } } return integer; } CULongInt operator * (unsigned __int32 right) const { CULongInt integer; //for every right number unsigned length1 = length - 1; while(length1 > 0 && data[length1 - 1] == 0) length1 --; for(unsigned int i = 0; i < length1; i++) { __int64 temp = (__int64)data[i] * (__int64)right; integer.data[i] += (__int32) (temp % MAX_DIGIT); integer.data[i + 1] += (__int32) (temp / MAX_DIGIT); } return integer; } protected: private: unsigned __int32 data[length + 1]; };

A5.

#pragma warning(disable:4786) #include <stdio.h> #include <map> #include <string> #define BUFSIZE 256 #define MAXTIME 32768 using namespace std; FILE *in=NULL, *out=NULL; map< string, int > table; int event[MAXTIME+1]; int init() { if(in) fclose(in); in = fopen("power.in", "rt"); if(!in) { return 0; } if(out) fclose(out); out = fopen("power.out", "wt"); if(!out) { fclose(in); return 0; } int n; char buf[BUFSIZE]; fscanf(in, "%d\n", &n); for(int i=0;i<n;i++) { fgets(buf, BUFSIZE, in); char str[BUFSIZE]; int val; sscanf(buf, "%s %d", str, &val); table.insert( pair<string, int>(string(str), val) ); } /* //debug info map< string, int>::iterator iter; for(iter=table.begin();iter!=table.end();iter++) { printf("(%s, %d) ", (*iter).first.c_str(), (*iter).second); } printf("\n");*/ return 1; } int uninit() { fclose(in); fclose(out); return 1; } int calc() { int line, maxpow; fscanf(in, "%d %d\n", &line, &maxpow); if(feof(in)) return 0; char buf[BUFSIZE], str[BUFSIZE]; int start, end, maxtime = 0; memset(event, 0, sizeof event); while(line && !feof(in)) { fgets(buf, BUFSIZE, in); sscanf(buf, "%s %d %d", str, &start, &end); map< string, int >::iterator iter = table.find(string(str)); int val = (*iter).second; event[start] += val; event[end] -= val; if(end>maxtime) maxtime = end; line--; } int pow = 0, overload = 0, overloadtime, overloadpow, maxpowneed = 0; for(int i=0;i<=maxtime;i++) { pow += event[i]; if(pow > maxpow) { overload = 1; overloadtime = i; overloadpow = pow; break; } else if(pow > maxpowneed) { maxpowneed = pow; } } if(overload) { fprintf(out, "The power will be out at time %d because the power is %d Watts and overloaded.\n", overloadtime, overloadpow); } else { fprintf(out, "The maximum power needed is %d Watts.\n", maxpowneed); } return 1; } void main() { if(!init()) { printf("Error while initializing.\n"); return; } while(calc()==1) ; uninit(); }