<repo_name>legaldev/USACO_Practice<file_sep>/section2/frac1.cpp
/*
ID: luglian1
PROG: frac1
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>

using namespace std;

#define MAXSIZE 160
#define PV(v) 	cout << #v << " = " << v << endl;

struct Fraction
{
	int numerator;
	int	denominator;
	float value;
	Fraction(int inumerator=0, int idenominator=1): 
		numerator(inumerator), denominator(idenominator)
	{
		value = (float)numerator / (float)idenominator;
	}
};

int gcd(int a, int b)
{
	if(a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}

	while(b != 0)
	{
		int reminder = a % b;
		a = b;
		b = reminder;
	}

	return a;
}

int main(){
	ifstream file_in("frac1.in");
	ofstream file_out("frac1.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}
	int n = 0;
	file_in >> n;

	int pre_size = 0;
	int n_size = 0;
	int total_size = 0;

	Fraction pre[MAXSIZE * MAXSIZE];
	Fraction cur[MAXSIZE * MAXSIZE];
	Fraction ncur[MAXSIZE];

	// initialize
	total_size = 2;
	cur[0] = Fraction(0, 1);
	cur[1] = Fraction(1, 1);
	PV(sizeof(Fraction));
	for(int i=2; i<=n; i++)
	{
		// create n
		n_size = 1;
		ncur[0] = Fraction(1, i);
		for(int p=2; p<i; p++)
		{
			if(gcd(i, p) > 1)
				continue;
			ncur[n_size] = Fraction(p, i);
			++n_size;
		}

		// cout << "n_size = " << n_size << endl;
		// for(int j=0; j<n_size; j++)
		// {
		// 	cout << ncur[j].numerator << "/" << ncur[j].denominator << endl;
		// }

		// copy cur to pre
		memcpy(pre, cur, sizeof(Fraction) * total_size);

		// for (int j = 0; j < total_size; ++j)
		// {
		// 	cout << pre[j].numerator << "/" << pre[j].denominator << endl;
		// }

		pre_size = total_size;
		total_size += n_size;

		// merge n to next
		int pre_pos=0;
		int n_pos=0;
		int cur_pos=0;
		while(n_pos < n_size)
		{
			if(pre[pre_pos].value < ncur[n_pos].value)
			{
				cur[cur_pos] = pre[pre_pos];
				++pre_pos;
			}
			else
			{
				cur[cur_pos] = ncur[n_pos];
				++n_pos;
			}
			++cur_pos;
		}
		cur[cur_pos] = pre[pre_pos];
		++cur_pos;

		if(total_size != cur_pos)
		{
			cout << "error: total size is not correct." << endl;
			cout << "total_size = " << total_size << endl;
			cout << "cur_pos = " << cur_pos << endl;
		}
	}

	for(int i=0; i<total_size; i++)
	{
		// cout << cur[i].numerator << "/" << cur[i].denominator << endl;
		file_out << cur[i].numerator << "/" << cur[i].denominator << endl;
	}

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/butter.cpp
/*
ID: luglian1
PROG: butter
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
#include <set>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << (v)[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "butter"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define INF 0x7fffffff
#define MAXP 801

using namespace std;

int N, P, C;
unsigned int dist[801][801] = {0};
int cow[500] = {0};
int mind = INF;
map<int, vector<int> > edges;

bool load();
void save(ostream& out);
bool save();
void solve();
void solve2();
void solve3();

int main(){
	load();
	//solve();
	//solve2();
	solve3();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N >> P >> C;

	for(int i=0; i<N; ++i)
	{
		file_in >> cow[i];
	}

	for(int i=0; i<=P; ++i)
	{
		for(int j=0; j<=P; ++j)
			dist[i][j] = INF;
		dist[i][i] = 0;
	}

	int a, b, d;
	for(int i=0; i<C; ++i)
	{
		file_in >> a >> b >> d;
		dist[a][b] = d;
		dist[b][a] = d;

		if(edges.count(a) == 0)
			edges.insert(pair<int, vector<int> >(a, vector<int>()));

		if(edges.count(b) == 0)
			edges.insert(pair<int, vector<int> >(b, vector<int>()));		

		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	return true;
}

void save(ostream& out)
{
	out << mind << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	// for(int i=1; i<=P; ++i)
	// {
	// 	PVL(dist[i], P+1)
	// }
	// cout << endl;

	for(int k=1; k<=P; ++k)
		for(int i=1; i<=P; ++i)
			for(int j=1; j<=P; ++j)
			{
				if(dist[i][k] + dist[k][j] < dist[i][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}

	// for(int i=1; i<=P; ++i)
	// {
	// 	PVL(dist[i], P+1)
	// }

	mind = INF;
	int minid = 0;
	for(int i=1; i<=P; ++i)
	{
		int newd = 0;
		bool fail = false;
		for(int j=0; j<N; ++j)
		{
			if(dist[i][cow[j]] == INF)
			{
				fail = true;
				continue;
			}
			newd += dist[i][cow[j]];
		}
		if(fail)
			continue;
		if(newd < mind)
		{
			mind = newd;
		}
	}
	PV(mind)
}

void dijkstra(unsigned int* q, int src)
{
	int s[MAXP] = {0};
	
	s[src] = 1;

	for(int i=1; i<= P; ++i)
	{
		int minid = -1;
		int minq = INF;
		for(int j=1; j <= P; ++j)
		{
			if(s[j] == 0 && q[j] < minq)
			{
				minid = j;
				minq = q[j];
			}
		}

		//PV(minid)

		if(minid < 0)
			break;

		s[minid] = 1;
		for(int j=1; j<=P; ++j)
		{
			if(s[j] == 0 && dist[minid][j] < INF)
			{
				int newq = minq + dist[minid][j];
				if(newq < q[j])
					q[j] = newq;
			}
		}

	}

	// PVL(q, P+1)
	return;
}

void solve2()
{
	// for(int i=1; i<=P; ++i)
	// {
	// 	PVL(dist[i], P+1)
	// }
	// cout << endl;

	//for(int i=0; i<N; ++i)
		dijkstra(dist[cow[0]], cow[0]);

	PVL(dist[cow[0]], P+1)

	// for(int i=1; i<=P; ++i)
	// {
	// 	PVL(dist[i], P+1)
	// }

	mind = INF;
	int minid = 0;
	for(int i=1; i<=P; ++i)
	{
		int newd = 0;
		bool fail = false;
		for(int j=0; j<N; ++j)
		{
			if(dist[cow[j]][i] == INF)
			{
				fail = true;
				continue;
			}
			newd += dist[cow[j]][i];
		}
		if(fail)
			continue;
		if(newd < mind)
		{
			mind = newd;
		}
	}
	PV(mind)
}

int cur_src;

struct compare
{
	bool operator()(const int& n1, const int& n2)
	{
		return dist[cur_src][n1] > dist[cur_src][n2];
	};
};

int vn[800];
int mark[801];
int vton[801];
compare c;
set<int> ss;

inline void my_swap(int i, int j)
{
	swap(vn[i], vn[j]);
	swap(vton[vn[i]], vton[vn[j]]);
}

void update_heap(int i, int n)
{
	if(n <= 0)
		return;
	int p=i;
	if(i > 0)
	{
		do
		{

			p = (i - 1) / 2;
			if(p >=0 && c(vn[p], vn[i]))
			{
				my_swap(p, i);
				i = p;
			}
			else
			{
				break;
			}

		}while(i > 0);
	}
	else
	{
		p = i;
		do
		{
			int ch1 = 2 * p + 1;
			int ch2 = 2 * p + 2;
			int min = p;

			if(ch2 < n)
			{
				if(c(vn[p], vn[ch1]) && c(vn[ch2], vn[ch1]))
					min = ch1;
				else if(c(vn[p], vn[ch2]))
					min = ch2;
			}
			else if(ch1 < n)
			{
				if(c(vn[p], vn[ch1]))
					min = ch1;
			}
			else
			{
				break;
			}

			if(min == p || min >= n)
			{
				break;
			}

			assert(dist[cur_src][vn[min]] < dist[cur_src][vn[p]]);
			my_swap(p, min);

			p = min;
		}while(p < n);
	}

}

void my_pop_heap(int n)
{
	my_swap(0, n-1);
	update_heap(0, n-1);
}

void dijkstra_fast(int src)
{
	cur_src = src;
	for(int i=0; i<P; ++i)
	{
		vn[i] = i+1;
	}

	make_heap(vn, vn+P, c);

	for(int i=0; i<P; ++i)
	{
		vton[vn[i]] = i;
	}

	for(int i=P; i>0; --i)
	{
		int n = vn[0];

		my_pop_heap(i);
		// pop_heap(vn, vn+i, c);

		if(edges.count(n) > 0)
		{
			const vector<int>& e = edges[n];
			for(vector<int>::const_iterator it=e.begin(); it!=e.end(); ++it)
			{
				if(vton[*it] <= i-1 && dist[src][n] + dist[n][*it] < dist[src][*it])
				{
					dist[src][*it] = dist[src][n] + dist[n][*it];
					// make_heap(vn, vn+i-1, compare());

					assert(vn[vton[*it]] == *it);
					update_heap(vton[*it], i-1);
					assert(vn[vton[*it]] == *it);
				}
			}
		}

	}
	// PV(ss.size())
}

void solve3()
{
	// int myints[] = {10,20,30,5,15};
	// make_heap (myints, myints+5, greater<int>());
	// for (unsigned i=0; i<5; i++) cout << " " << myints[i];
	//   cout << endl;

	// for(int i=5; i>0; --i)
	// {
	// 	cout << endl;
	// 	pop_heap(myints, myints+i, greater<int>());
	// 	for (unsigned j=0; j<i-1; j++) cout << " " << myints[j];
	//   	cout << endl;
	// }

	// for(int i=1; i<=P; ++i)
	// {
	// 	PVL(dist[i], P+1)
	// }
	// cout << endl;

	for(int i=0; i<N; ++i)
		dijkstra_fast(cow[i]);

	// PVL((dist[cow[14]] + 1), P)

	// for(int i=0; i<N; ++i)
	// {
	// 	PVL((dist[cow[i]] + 1), P)
	// }

	mind = INF;
	int minid = 0;
	for(int i=1; i<=P; ++i)
	{
		int newd = 0;
		bool fail = false;
		for(int j=0; j<N; ++j)
		{
			if(dist[cow[j]][i] == INF)
			{
				fail = true;
				continue;
			}
			newd += dist[cow[j]][i];
		}
		if(fail)
			continue;
		if(newd < mind)
		{
			mind = newd;
		}
	}
	PV(mind)
}

// We approach this problem directly, by calculating the distance from each cow to each pasture. Once this is done, we will simply have to sum the distances for each cow to get the total cost of putting the sugar cube at a given pasture. The key to a fast distance calculation is that our graph is quite sparse. Thus, we use Dijkstra with a heap to calculate the distance from a given cow to all pastures. This requires on the order of N*C*log(P), or about 7,000,000, operations.
// #include <stdio.h>
// #include <string.h>

// const int BIG = 1000000000;

// const int MAXV = 800;
// const int MAXC = 500;
// const int MAXE = 1450;


// int cows;
// int v,e;


// int cow_pos[MAXC];
// int degree[MAXV];
// int con[MAXV][MAXV];
// int cost[MAXV][MAXV];

// int dist[MAXC][MAXV];


// int heapsize;
// int heap_id[MAXV];
// int heap_val[MAXV];
// int heap_lookup[MAXV];


// bool validheap(void){
//   for(int i = 0; i < heapsize; ++i){
//     if(!(0 <= heap_id[i] && heap_id[i] < v)){
//       return(false);
//     }
//     if(heap_lookup[heap_id[i]] != i){
//       return(false);
//     }
//   }
//   return(true);
// }


// void heap_swap(int i, int j){
//   int s;

//   s = heap_val[i];
//   heap_val[i] = heap_val[j];
//   heap_val[j] = s;

//   heap_lookup[heap_id[i]] = j;

//   heap_lookup[heap_id[j]] = i;

//   s = heap_id[i];
//   heap_id[i] = heap_id[j];
//   heap_id[j] = s;

// }


// void heap_up(int i){
//   if(i > 0 && heap_val[(i-1) / 2] > heap_val[i]){
//     heap_swap(i, (i-1)/2);
//     heap_up((i-1)/2);
//   }
// }


// void heap_down(int i){
//   int a = 2*i+1;
//   int b = 2*i+2;

//   if(b < heapsize){
//     if(heap_val[b] < heap_val[a] && heap_val[b] < heap_val[i]){
//       heap_swap(i, b);
//       heap_down(b);
//       return;
//     }
//   }
//   if(a < heapsize && heap_val[a] < heap_val[i]){
//     heap_swap(i, a);
//     heap_down(a);
//   }
// }




// int main(){


//   FILE *filein = fopen("butter.in", "r");
//   fscanf(filein, "%d %d %d", &cows, &v, &e);
//   for(int i = 0; i < cows; ++i){
//     fscanf(filein, "%d", &cow_pos[i]);
//     --cow_pos[i];
//   }
//   for(int i = 0; i < v; ++i){
//     degree[i] = 0;
//   }
//   for(int i = 0; i < e; ++i){
//     int a,b,c;
//     fscanf(filein, "%d %d %d", &a, &b, &c);
//     --a;
//     --b;

//     con[a][degree[a]] = b;
//     cost[a][degree[a]] = c;
//     ++degree[a];

//     con[b][degree[b]] = a;
//     cost[b][degree[b]] = c;
//     ++degree[b];

//   }
//   fclose(filein);


//   for(int i = 0; i < cows; ++i){
//     heapsize = v;
//     for(int j = 0; j < v; ++j){
//       heap_id[j] = j;
//       heap_val[j] = BIG;
//       heap_lookup[j] = j;
//     }
//     heap_val[cow_pos[i]] = 0;
//     heap_up(cow_pos[i]);

//     bool fixed[MAXV];
//     memset(fixed, false, v);
//     for(int j = 0; j < v; ++j){
//       int p = heap_id[0];
//       dist[i][p] = heap_val[0];
//       fixed[p] = true;
//       heap_swap(0, heapsize-1);
//       --heapsize;
//       heap_down(0);

//       for(int k = 0; k < degree[p]; ++k){
// 	int q = con[p][k];
// 	if(!fixed[q]){
// 	  if(heap_val[heap_lookup[q]] > dist[i][p] + cost[p][k]){
// 	    heap_val[heap_lookup[q]] = dist[i][p] + cost[p][k];
// 	    heap_up(heap_lookup[q]);
// 	  }
// 	}
//       }

//     }
//   }

//   int best = BIG;
//   for(int i = 0; i < v; ++i){
//     int total = 0;
//     for(int j = 0; j < cows; ++j){
//       total += dist[j][i];
//     }
//     best <?= total;
//   }


//   FILE *fileout = fopen("butter.out", "w");
//   fprintf(fileout, "%d\n", best);
//   fclose(fileout);


//   return(0);
// }
<file_sep>/section3/agrinet.cpp
/*
ID: luglian1
PROG: agrinet
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "agrinet"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAXN 100
#define INF 99999999
using namespace std;


int n;
int edge[MAXN][MAXN] = {0};

int dis[MAXN];
int tree[MAXN] = {0};
int res = INF;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> n;
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			file_in >> edge[i][j];

	for(int i=0; i<n; ++i)
	{
		PVL(edge[i], n)
	}

	return true;
}

void save(ostream& out)
{
	out << res << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

int solve_one(int src)
{
	for(int i=0; i<n; ++i)
	{
		tree[i] = 0;
		if(edge[src][i])
			dis[i] = edge[src][i];
		else
			dis[i] = INF;
	}

	dis[src] = 0;
	tree[src] = 1;
	for(int i=0; i<n-1; ++i)
	{
		int mind = INF;
		int minid = -1;
		for(int j=0; j<n; ++j)
		{
			if(tree[j] == 0 && dis[j] < mind)
			{
				mind = dis[j];
				minid = j;
			}
		}

		tree[minid] = 1;
		for(int j=0; j<n; ++j)
		{
			if(tree[j] == 0)
				dis[j] = min(dis[j], edge[minid][j]);
		}
	}

	PVL(dis, n)

	int totald = 0;
	for(int i=0; i<n; ++i)
		totald += dis[i];

	PV(totald)

	return totald;
}

void solve()
{
	for(int i=0; i<1; ++i)
	{
		int d = solve_one(i);
		res = min(d, res);
	}
}


// This problem requires finding the minimum spanning tree of the given graph. We use an algorithm that, at each step, looks to add to the spanning tree the closest node not already in the tree.

// Since the tree sizes are small enough, we don't need any complicated data structures: we just consider every node each time.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXFARM	100

// int nfarm;
// int dist[MAXFARM][MAXFARM];
// int isconn[MAXFARM];

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, j, nfarm, nnode, mindist, minnode, total;

//     fin = fopen("agrinet.in", "r");
//     fout = fopen("agrinet.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d", &nfarm);
//     for(i=0; i<nfarm; i++)
//     for(j=0; j<nfarm; j++) 
// 	fscanf(fin, "%d", &dist[i][j]);

//     total = 0;
//     isconn[0] = 1;
//     nnode = 1;
//     for(isconn[0]=1, nnode=1; nnode < nfarm; nnode++) {
// 	mindist = 0;
// 	for(i=0; i<nfarm; i++)
// 	for(j=0; j<nfarm; j++) {
// 	    if(dist[i][j] && isconn[i] && !isconn[j]) {
// 	    	if(mindist == 0 || dist[i][j] < mindist) {
// 		    mindist = dist[i][j];
// 		    minnode = j;
// 		}
// 	    }
// 	}
// 	assert(mindist != 0);
		
// 	isconn[minnode] = 1;
// 	total += mindist;
//     }

//     fprintf(fout, "%d\n", total);

//     exit(0);
// }
// Here is additional analysis from <NAME>:

// The solution given is O(N3); however, we can obtain O(N2) if we modify it by storing the distance from each node outside of the tree to the tree in an array, instead of recalculating it each time. Thus, instead of checking the distance from every node in the tree to every node outside of the tree each time that we add a node to the tree, we simply check the value in the array for each node outside of the tree.

// #include <fstream.h>
// #include <assert.h>

// const int BIG = 20000000;

// int     n;
// int     dist[1000][1000];
// int     distToTree[1000];
// bool    inTree[1000];

// main ()
// {
//     ifstream filein ("agrinet.in");
//     filein >> n;
//     for (int i = 0; i < n; ++i) {
// 	for (int j = 0; j < n; ++j) {
// 	    filein >> dist[i][j];
// 	}
// 	distToTree[i] = BIG;
// 	inTree[i] = false;
//     }
//     filein.close ();

//     int     cost = 0;
//     distToTree[0] = 0;

//     for (int i = 0; i < n; ++i) {
// 	int     best = -1;
// 	for (int j = 0; j < n; ++j) {
// 	    if (!inTree[j]) {
// 		if (best == -1 || distToTree[best] > distToTree[j]) {
// 		    best = j;
// 		}
// 	    }
// 	}
// 	assert (best != -1);
// 	assert (!inTree[best]);
// 	assert (distToTree[best] < BIG);

// 	inTree[best] = true;
// 	cost += distToTree[best];
// 	distToTree[best] = 0;
// 	for (int j = 0; j < n; ++j) {
// 	    if (distToTree[j] > dist[best][j]) {
// 		distToTree[j] = dist[best][j];
// 		assert (!inTree[j]);
// 	    }
// 	}
//     }
//     ofstream fileout ("agrinet.out");
//     fileout << cost << endl;
//     fileout.close ();
//     exit (0);
// }<file_sep>/section 1/crypt1.cpp
/*
ID: luglian1
PROG: crypt1
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

bool checknum(int num, const vector<int>& nums){
	while(num > 0){
		int final = num % 10;
		int i;
		for(i=0; i!=nums.size(); ++i){
			if(final == nums[i]){
				break;
			}
		}
		if(i == nums.size())
			return false;
		num /= 10;
	}
	return true;
}


int main(){
	ifstream file_in("crypt1.in");
	ofstream file_out("crypt1.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	file_in >> n;
	vector<int> nums(n);
	for(int i=0; i!=n; ++i){
		file_in >> nums[i];
	}

	sort(nums.begin(), nums.end());
	for(int i=0; i!=nums.size(); ++i)
		cout << nums[i] << endl;
	// complete search
	int count=0;
	for(int i=0; i!=n; ++i){
		for(int j=0; j!=n; ++j){
			for(int k=0; k!=n; ++k){
				int num1 = nums[i]*100 + nums[j]*10 + nums[k];

				for(int s=0; s!=n; ++s){
					int pro2 = (num1 * nums[s]);
					if(pro2 > 999 || !checknum(pro2, nums))
						continue;

					for(int t=0; t!=n; ++t){
						
						int pro1 = (num1 * nums[t]);
						if(pro1 > 999 || !checknum(pro1, nums))
							continue;

						int sum = (pro2 * 10 + pro1);
						if(sum > 9999 || !checknum(sum, nums))
							continue;
						++count;
						//cout << sum << endl;
					}
				}
			}
		}
	}


	cout << count << endl;

	file_out << count << endl;
	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/milk2.cpp
/*
ID: luglian1
PROG: milk2
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <list>

using namespace std;

typedef pair<int, int> timeInv;

// 0 no overlap, -1 t1 left overlap t2, 1 t1 right overlap t2
bool checkOverlap(const timeInv& t1, const timeInv& t2){
	if(t1.second < t2.first || t1.first > t2.second)
		return false;
	return true;
}

// merge t1 into t2
void mergeTimeInv(timeInv& t1, timeInv& t2){
	t2.first = t2.first < t1.first ?  t2.first : t1.first;
	t2.second = t2.second > t1.second ? t2.second : t1.second; 
}

int main(){
	ifstream file_in("milk2.in");
	ofstream file_out("milk2.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	list<timeInv > milk_interval;



	int n;
	file_in >> n;
	timeInv onetime;
	for(int i=0; i!=n; ++i){
		file_in >> onetime.first >> onetime.second;
		list<timeInv>::iterator it;
		bool overlap = false;
		for( it=milk_interval.begin(); it != milk_interval.end(); ++it){
			if( checkOverlap(onetime, *it) ){
				overlap = true;
				list<timeInv>::iterator itmp = it;
				mergeTimeInv(onetime, *it);
				
				for(int j=-1; j < 2; j+=2){
					int newmeger = true;
					while(newmeger){
					newmeger = false;
					itmp = it;
					if(j<0)
						--itmp;
					else
						++itmp;
					if(itmp != milk_interval.end())
						if( checkOverlap(*itmp, *it) ){
							mergeTimeInv(*itmp, *it);
							milk_interval.erase(itmp);
							newmeger = true;
						}
					}
				}
			}
			else{	// no overlap, insert
				if(onetime.second < it->first){
					break;
				}
			}
		}	// for

		if(!overlap ){
			milk_interval.insert(it, onetime);
		}
		
	}

	cout << n << " " << milk_interval.size() << endl;

	int milk=0, nomilk=0;
	for(list<timeInv>::iterator it=milk_interval.begin(); it != milk_interval.end(); ++it){
		cout << it->first << " " << it->second << endl;
		if(milk < it->second - it->first)
			milk = it->second - it->first;
		list<timeInv>::iterator next = it;
		++next;
		if(next != milk_interval.end())
			if(nomilk < next->first - it->second)
				nomilk = next->first - it->second;
	}

	file_out << milk <<" "  << nomilk << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section2/ttwo.cpp
/*
ID: luglian1
PROG: ttwo
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "ttwo"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

bool load();
void save(ostream& out);
bool save();
void solve();

int farm[10][10] = {0};
int fp[2] = {0};
int fd = 0;
int cp[2] = {0};
int cd = 0;
int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int res = 0;

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	for(int i=0; i<10; ++i)
	{
		string line;
		file_in >> line;
		for(int j=0; j<10; ++j)
		{
			char c = line[j];
			switch(c)
			{
				case '*':
					farm[i][j] = 1;
					break;
				case 'F':
					fp[0] = i;
					fp[1] = j;
					break;
				case 'C':
					cp[0] = i;
					cp[1] = j;
					break;
				default:
					break;
			}
		}
	}

	return true;
}

void save(ostream& out)
{
	out << res << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void tick(int* pos, int* dir)
{
	int nx = pos[0] + dirs[*dir][0];
	int ny = pos[1] + dirs[*dir][1];

	if(nx < 0 || nx > 9 || ny < 0 || ny > 9 || farm[nx][ny])
	{
		*dir = (*dir + 1) % 4;
	}
	else
	{
		pos[0] = nx;
		pos[1] = ny;
	}
}

void solve()
{
	// find 1,000,000 times
	for(int t=0; t< 1000000; ++t)
	{
		tick(fp, &fd);
		tick(cp, &cd);
		if(fp[0] == cp[0] && fp[1] == cp[1])
		{	
			res = t + 1;
			break;
		}

	}
}


// analysis
// We can simply simulate the movement of <NAME> and the two cows, but we need to find a way to detect loops. There are only 100 places where the cows can be, and 4 directions they can face. The same goes for <NAME>. This multiplies out to 400*400 = 160,000 different (place, direction) configurations for <NAME> and the cows. If we ever happen upon a configuration we have been in before, we are in an infinite loop, and John and the cows will never meet.

// In fact, we don't even need to keep track of which configurations we've seen. If they're going to meet, they're going to meet in fewer than 160,000 steps. Otherwise, they have to repeat some configuration, in which case they'll never meet.

// We take care of the simulation by keeping track of the position and direction of each. Direction is a number from 0 to 3, 0 = north, 1 = east, 2 = south, 3 = west. So turning clockwise is incrementing one. We calculate how to move given the direction by looking up offsets in the deltax and deltay arrays.

// /*
// PROG: ttwo
// ID: rsc001
// */

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// char grid[10][10];

// /* delta x, delta y position for moving north, east, south, west */
// int deltax[] = { 0, 1, 0, -1 };
// int deltay[] = { -1, 0, 1, 0 };

// void
// move(int *x, int *y, int *dir)
// {
// 	int nx, ny;

// 	nx = *x+deltax[*dir];
// 	ny = *y+deltay[*dir];

// 	if(nx < 0 || nx >= 10 || ny < 0 || ny >= 10 || grid[ny][nx] == '*')
// 		*dir = (*dir + 1) % 4;
// 	else {
// 		*x = nx;
// 		*y = ny;
// 	}
// }

// void
// main(void)
// {
// 	FILE *fin, *fout;
// 	char buf[100];
// 	int i, x, y;
// 	int cowx, cowy, johnx, johny, cowdir, johndir;


// 	fin = fopen("ttwo.in", "r");
// 	fout = fopen("ttwo.out", "w");
// 	assert(fin != NULL && fout != NULL);

// 	cowx = cowy = johnx = johny = -1;

// 	for(y=0; y<10; y++) {
// 		fgets(buf, sizeof buf, fin);
// 		for(x=0; x<10; x++) {
// 			grid[y][x] = buf[x];
// 			if(buf[x] == 'C') {
// 				cowx = x;
// 				cowy = y;
// 				grid[y][x] = '.';
// 			}
// 			if(buf[x] == 'F') {
// 				johnx = x;
// 				johny = y;
// 				grid[y][x] = '.';
// 			}
// 		}
// 	}

// 	assert(cowx >= 0 && cowy >= 0 && johnx >= 0 && johny >= 0);

// 	cowdir = johndir = 0;	/* north */

// 	for(i=0; i<160000 && (cowx != johnx || cowy != johny); i++) {
// 		move(&cowx, &cowy, &cowdir);
// 		move(&johnx, &johny, &johndir);
// 	}

// 	if(cowx == johnx && cowy == johny)
// 		fprintf(fout, "%d\n", i);
// 	else
// 		fprintf(fout, "0\n");
// 	exit(0);
// }<file_sep>/section 1/skidesign.cpp
/*
ID: luglian1
PROG: skidesign
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "skidesign"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
using namespace std;
bool load();
void save(ostream& out);
bool save();
void solve();
void anothersolve();

int N = 0;
vector<int> hs;
vector<int> curmove;
int sum = 0;

int main(){
	load();
	solve();
	//anothersolve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;
	int n;
	for(int i=0; i<N; i++)
	{
		file_in >> n;
		hs.push_back(n);
		curmove.push_back(0);
	}


	return true;
}

void save(ostream& out)
{
	out << sum << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

int findnextlow(int curlow)
{
	for(int i=0; i<N; i++)
	{
		if (hs[i] > curlow)
			return hs[i];
	}
}

int findnexthigh(int curhigh)
{
	for(int i=N-1; i>=0; i--)
	{
		if (hs[i] < curhigh)
			return hs[i];
	}
}

int findcountlow(int low)
{
	for(int i=0; i<N; i++)
	{
		if (hs[i] > low)
			return i+1;
	}	
}

int findcounthigh(int high)
{
	for(int i=N-1; i>=0; i--)
	{
		if (hs[i] < high)
			return i;
	}
}

template <typename T>
T dosum(std::vector<T>& list, int begin, int end)
{
	T sum = 0;
	for (int i=begin; i<end; i++)
	{
		sum += list[i];
	}

	return sum;
}

void updatecurmove(int low, int high)
{
	for(int i=0; i<N; i++)
	{
		if(hs[i] < low)
			curmove[i] = low - hs[i];
		else if(hs[i] > high)
			curmove[i] = hs[i] - high;
		else
			curmove[i] = 0;
	}
}

void solve()
{
	sort(hs.begin(), hs.end());
	//PVL(hs, N)

	int maxdiff = hs[N-1] - hs[0];

	if (maxdiff <= 17)
		return;

	int curdiff = maxdiff;
	int low = hs[0], high = hs[N-1];
	PVL(curmove, N)
	while (high - low > 17)
	{
		int nextlow = findnextlow(low);

		int nexthigh = findnexthigh(high);

		PV(nexthigh)
		PV(nextlow)
		int n = min(nextlow-low, min(high-nexthigh, curdiff-17));
		PV(n)
		int countlow = findcountlow(low);

		int counthigh = findcounthigh(high);

		int sumlow = dosum(curmove, 0, countlow);
		int sumhigh = dosum(curmove, N-1-counthigh, N);
		PV(sumhigh)
		PV(sumlow)
		int nexthighmove = max((n + sumlow - sumhigh) / 2, 0);
		int realhighmove = min(n, min(nexthighmove, high-nexthigh));

		int nextlowmove = max((n + sumhigh - sumlow) / 2, 0);
		int reallowmove = min(n, min(nextlowmove, nextlow-low));

		PV(nexthighmove)
		PV(nextlowmove)

		if (realhighmove == 0 && reallowmove == 0)
		{
			realhighmove = 1;
			reallowmove = 1;
		}

		high -= realhighmove;
		low += reallowmove;
		PV(high)
		PV(low)
		updatecurmove(low, high);

		cout << "==============" << endl;
	}


	PV(high)
	PV(low)
	PVL(curmove, N)
	int countlow = findcountlow(low);
	int counthigh = findcounthigh(high);

	for(int i=0; i<N; i++)
	{
		sum += curmove[i] * curmove[i];
	}
}

void anothersolve()
{
	int minsum = 0x7fffffff;
	int minlow=0, minhigh=100;
	for (int low=0; low<=83; low++)
	{
		int high = low + 17;
		//for (int high=low + 17; high <= 100; high++)
		{
			int onesum = 0;
			for(int i=0; i<N; i++)
			{
				if(hs[i] < low)
					onesum += (low - hs[i]) * (low - hs[i]);
				else if(hs[i] > high)
					onesum += (hs[i] - high) * (hs[i] - high);
			}
			
			if (onesum < minsum)
			{
				minsum = onesum;
				minlow = low;
				minhigh = high;
			}
		}
	}
	PV(minsum)
	PV(minlow)
	PV(minhigh)
	sum = minsum;
}<file_sep>/section3/ratios.cpp
/*
ID: luglian1
PROG: ratios
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "ratios"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define INF 0x7fffffff

using namespace std;

int goal[3] = {0};
int other[3][3] = {0};
int mix[101][3][3] = {0};

int res[5] = {INF, INF, INF, INF, INF};
bool found = false;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> goal[0] >> goal[1] >> goal[2];
	for(int i=0; i<3; ++i)
	{
		for(int j=0; j<3; ++j)
			file_in >> other[i][j];
	}

	return true;
}

void save(ostream& out)
{
	if(found)
	{
		for(int i=0; i<3; ++i)
			out << res[i] << " ";
		out << res[3] << endl;
	}
	else{
		out << "NONE" << endl;
	}
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	for(int i=0; i<=100; ++i)
	{
		for(int j=0; j<3; ++j)
		{
			for(int k=0; k<3; ++k)
			{
				mix[i][j][k] = other[j][k] * i;
			}
		}
	}

	// for(int j=0; j<3; ++j)
	// 	{PVL(mix[4][j], 3)}

	int tmp[3];
	for(int i=0; i<=100; ++i)
	{
		for(int j=0; j<=100; ++j)
		{
			for(int k=0; k<=100; ++k)
			{
				if(i==0 && j==0 && k==0)
					continue;
				if(i+j+k > res[4])
					continue;

				for(int a=0; a<3; ++a)
				{
					tmp[a] = 0;
					tmp[a] += mix[i][0][a] + mix[j][1][a] + mix[k][2][a];
				}

				int ratio = tmp[0] / goal[0];

				if((tmp[0] == goal[0] *ratio) && (tmp[1] == goal[1] * ratio)&& (tmp[2] == goal[2] *ratio))
				{

					// cout << i <<", " <<  j <<", "<< k << endl;
					// PVL(tmp, 3)
					res[0] = i;
					res[1] = j;
					res[2] = k;
					res[3] = tmp[0] / goal[0];
					res[4] = i+j+k;
					found = true;
				}
			}
		}
	}

}

// As there are only 1013 = 1,030,301 ways to do this, try them all and pick the best.

// #include <stdio.h>

// /* the goal ratio */
// int goal[3];

// /* the ratio of the feeds */
// int ratios[3][3];

// /* the best solution found so far */
// int min;
// int mloc[4]; /* amounts of ratio 1, 2, and 3, and the amount of ratio 4 prod */

// /* the amount of each type of component in the feed */
// int sum[3];

// int main(int argc, char **argv)
//  {
//   FILE *fout, *fin;
//   int lv, lv2, lv3; /* loop variables */
//   int t, s; /* temporary variables */
//   int gsum; /* the sum of the amounts of components in the goal mixture */

//   if ((fin = fopen("ratios.in", "r")) == NULL)
//    {
//     perror ("fopen fin");
//     exit(1);
//    }
//   if ((fout = fopen("ratios.out", "w")) == NULL)
//    {
//     perror ("fopen fout");
//     exit(1);
//    }

//   /* read in data */
//   fscanf (fin, "%d %d %d", &goal[0], &goal[1], &goal[2]);
//   for (lv = 0; lv < 3; lv++)
//     fscanf (fin, "%d %d %d", ratios[lv]+0, ratios[lv]+1, ratios[lv]+2);

//   gsum = goal[0] + goal[1] + goal[2];

//   min = 301; /* worst than possible = infinity */

//   /* boundary case (this ensures gsum != 0) */
//   if (gsum == 0)
//    {
//     fprintf (fout, "0 0 0 0\n");
//     return 0;
//    }

//   for (lv = 0; lv < 100; lv++)
//     for (lv2 = 0; lv2 < 100; lv2++)
//      { /* for each amout of the first two types of mixtures */
//       sum[0] = lv*ratios[0][0] + lv2*ratios[1][0];
//       sum[1] = lv*ratios[0][1] + lv2*ratios[1][1];
//       sum[2] = lv*ratios[0][2] + lv2*ratios[1][2];

//       if (lv + lv2 > min) break;

//       for (lv3 = 0; lv3 < 100; lv3++)
//        {
//         s = lv + lv2 + lv3;
// 	if (s >= min) break; /* worse than we've found already */

//         /* calculate a guess at the multiples of the goal we've obtained */
// 	/* use gsum so we don't have to worry about divide by zero */
//         t = (sum[0] + sum[1] + sum[2]) / gsum;
// 	if (t != 0 && sum[0] == t*goal[0] && 
// 	        sum[1] == t*goal[1] && sum[2] == t*goal[2])
// 	 {  we've found a better solution! 
// 	  /* update min */
// 	  min = s;

// 	  /* store the solution */
// 	  mloc[0] = lv;
// 	  mloc[1] = lv2;
// 	  mloc[2] = lv3;
// 	  mloc[3] = t;
// 	 }

//         /* add another 'bucket' of feed #2 */
//         sum[0] += ratios[2][0];
//         sum[1] += ratios[2][1];
//         sum[2] += ratios[2][2];
//        }
//      }
//   if (min == 301) fprintf (fout, "NONE\n"); /* no solution found */
//   else fprintf (fout, "%d %d %d %d\n", mloc[0], mloc[1], mloc[2], mloc[3]);
//   return 0;
//  }
// <NAME> Solution

// When you combine multiples of mixtures, you can look at it as a multiplication of a matrix by a vector. For example, 8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5) can be seen as

// [ 1 3 2 ]   [ 8 ]            
// [ 2 7 1 ] * [ 1 ] = 7 [3 4 5]
// [ 3 1 2 ]   [ 5 ]           
// The matrix and the goal ratio vector (3:4:5 in this case) are given; what we have to find is the multiple vector (8:1:5 in this case) and the proportionality costant (7 here). This is like solving a system of linear equations. We can write it as

// AX = kB.
// Now, if we use Cramer's Rule, and let D = determinant of A, then

// X_1 = k D_1 / D
// X_2 = k D_2 / D
// X_3 = k D_3 / D,
// where D_1 is the determinant of the matrix A with the 1st column is replaced by B, D_2 is the determinant of the matrix A with the 2nd column is replaced by B, D_3 is the determinant of the matrix A with the 3rd column is replaced by B. (see a Linear Algebra textbook on why this works.) ,P> We are looking for integral solutions. If D = 0, no solutions. Otherwise, let k = D, and then X_1 = D_1, etc. If these values (X_1,X_2,X_3, _and_ k) all have a greatest common factor above 1, divide them all by that factor, as we are looking for the smallest possible solutions.
// Now, if some of the numbers is greater than 100, we have not found a feasible solution, so we output `NONE'. Otherwise, the triple (X_1,X_2,X_3) is output, as well as the value k. <file_sep>/mytest/test.cpp
/*
ID: luglian1
PROG: beads
LANG: C++
*/

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;

struct MeshData
{
	int		nVertices;
	int		nIndices;
	int		vertexSize;	/// in byte

	char*	pVertexBuffer;
	int*	pIndexBuffer;
};

int main(){

	string s("010");
	int test;
	//cout << test << endl;
	stringstream ss;
	ss << 1 << " ";
	//ss >> test;
	int * ip = new int[0];
	cout << (int)ip <<endl;
	*ip = 1;
	cout << *ip <<endl;
	float a=0.f;
	a++;
	cout << ++a <<endl;

	char ca = -1;
	unsigned char uca = ca;
	cout << (int)uca << endl;

	cout << (unsigned char)1 - (unsigned char)3 << endl;

	cout << -1 % 50 << endl;

	return 0;
}
<file_sep>/section 1/pprime.cpp
/*
ID: luglian1
PROG: pprime
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

class PrimeGenerator{
	int cur;
	int begin;
	int over;
	int index;
public:
	static vector<int> prime;
	PrimeGenerator(int a, int b): begin(a), over(b), cur(3), index(1){
		prime.push_back(2);
		prime.push_back(3);
		int sq = sqrt((double)over) + 1;
		cur += 2;
		while( cur <= sq ){
			if( checkPrime(cur) ){
				prime.push_back(cur);
			}
			cur += 2;
		}
		cur = begin%2==0 ? begin -1 : begin-2;
	}

	int next(){
		if(prime[prime.size()-1]>=cur && index<=prime.size()-1){
			for(; prime[index]<cur && index<=prime.size()-1; ++index);
			if(index<=prime.size()-1){
				cur = prime[index];
				++index;
				return cur;
			}
		}


		cur += 2;
		while( cur <= over ){
			if( checkPrime(cur) ){
				//prime.push_back(cur);
				if(cur >= begin)
					return cur;
			}
			cur += 2;
		}
		return end();
	}

	int end(){
		return 0;
	}

	static bool checkPrime(int n){
		int sq = sqrt((double)n)+1;
		for(int i=0; i!=prime.size(); ++i){
			if(prime[i] > sq)
				break;
			if( n % prime[i] == 0)
				return false;
		}
		return true;
	}
};

vector<int> PrimeGenerator::prime;

class PalinGenerator{

	int min;
	int max;
	int test;
	string snum;
	stringstream ss;
public:

	PalinGenerator(int a, int b): min(a), max(b){}

	void findPP(int pos, int len, ostream& file_out){
		if(len <= 0){
			ss.clear();
			ss.str(snum);
			//ss << snum;
			ss >> test;
			//cout << snum << " " << test <<endl;

			if(test>=min && test <= max && PrimeGenerator::checkPrime(test))
				file_out << test << endl;
			return;
		}

		int i = pos == 0 ? 1 : 0;
		for(; i<=9; ++i){
			snum[pos] = snum[snum.size()-1-pos] = '0'+i;
			findPP(pos+1, len-2, file_out);
		}

	}

	void work(ostream& file_out){
		for(int len=1; len<=8; ++len){
			snum.resize(len);
			findPP(0, len, file_out);
		}
	}

	static bool checkPalin(int i){
		string s;
		while( i>0 ){
			s += i%10;
			i /= 10;
		}

		for(int k=0; k<s.size()/2; ++k){
			if(s[k] != s[s.size()-k-1])
				return false;
		}
		return true;
	}
};

int a, b;

void read(istream& file_in){
	file_in >> a >> b;
}

void palinwork(ostream& file_out){
	//cout << a << " " << b << endl;
	PrimeGenerator ppg(5, 100000000);
	//cout << ppg.prime.size() << endl;
	PalinGenerator pg(a, b);
	pg.work(file_out);
}

int main(){
	ifstream file_in("pprime.in");
	ofstream file_out("pprime.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	read(file_in);
	palinwork(file_out);

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section2/castle.cpp
/*
ID: luglian1
PROG: castle
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
using namespace std;

#define WEST 	0x01
#define NORTH 	0x02
#define EAST	0x04
#define SOUTH	0x08
typedef unsigned char byte;
const int max_size = 50;


struct Castle
{
	int num_rooms;
	int rooms_size[max_size*max_size];
	int largest_size;
	Castle(): num_rooms(0), largest_size(0) {}
};

byte wall[max_size][max_size];
int room_component[max_size][max_size];
int m, n;

Castle castle_flood_fill();
int castle_flood_fill(int i, int j, int roomId);

int main()
{
	ifstream file_in("castle.in");
	ofstream file_out("castle.out");
	if(!file_in || !file_out)
	{
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	file_in >> n >> m;
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<n; j++)
		{
			int temp;
			file_in >> temp;
			wall[i][j] = (byte)temp;
		}
	}

	Castle info = castle_flood_fill();
	file_out << info.num_rooms << endl << info.largest_size << endl;

	// for(int i=0; i<m; i++)
	// {
	// 	for(int j=0; j<n; j++)
	// 	{
	// 		cout << room_component[i][j] << " ";
	// 	}
	// 	cout<< endl;
	// }

	// find the wall to remove
	int moduleRowId = -1;
	int moduleColId = -1;
	byte wall_to_remove = 0;
	int merge_max_size = -1;
	byte wall_to_check[2] = {NORTH, EAST};
	byte wall_to_check_neighbor[2] = {SOUTH, WEST};
	printf("%x\n", ~wall_to_check[0]);
	for(int j=0; j < n; j++)
	{
		for(int i=m-1; i>=0; i--)
		{
			// north
			if(i > 0 && room_component[i][j] != room_component[i-1][j])
			{
				int size = 
					info.rooms_size[room_component[i][j]] + 
					info.rooms_size[room_component[i-1][j]];
				if(size > merge_max_size)
					{
						merge_max_size = size;
						moduleRowId = i;
						moduleColId = j;
						wall_to_remove = NORTH;
					}
			}
			// east
			if(j < n-1 && room_component[i][j] != room_component[i][j+1])
			{
				int size = 
					info.rooms_size[room_component[i][j]] + 
					info.rooms_size[room_component[i][j+1]];
				if(size > merge_max_size)
					{
						merge_max_size = size;
						moduleRowId = i;
						moduleColId = j;
						wall_to_remove = EAST;
					}
			}
			continue;

			byte wall_backup = wall[i][j];
			for(int wallId=0; 
				wallId < sizeof(wall_to_check)/sizeof(wall_to_check[0]); 
				wallId++)
			{
				if(j == n-1 && wall_to_check[wallId] == EAST)
					continue;
				if(i ==0 && wall_to_check[wallId] == NORTH)
					continue;
				if(wall[i][j] & wall_to_check[wallId])
				{
					byte* pNeighbor = 
						wall_to_check[wallId] == EAST ? 
						&wall[i][j+1] : &wall[i-1][j];
					byte neighbor_wall = *pNeighbor;
					*pNeighbor &= ~wall_to_check_neighbor[wallId];
					wall[i][j] = wall[i][j] & (~wall_to_check[wallId]);
					Castle remove_info = castle_flood_fill();
					cout << i << " " << j << " " << (wall_to_check[wallId] == EAST ? "E" : "N") << " ";
					cout << remove_info.num_rooms << " " << remove_info.largest_size << endl;;
					if(remove_info.largest_size > merge_max_size)
					{
						merge_max_size = remove_info.largest_size;
						moduleRowId = i;
						moduleColId = j;
						wall_to_remove = wall_to_check[wallId];
					}
					wall[i][j] = wall_backup;
					*pNeighbor = neighbor_wall;
				}				
			}
		}
	}
	file_out << merge_max_size << endl;
	file_out << moduleRowId+1 << " " << moduleColId+1 << " " 
			<< (wall_to_remove == EAST ? "E" : "N") << endl;

	cout <<	 m << " " << n << endl;
	cout << info.num_rooms << endl << info.largest_size << endl;
	cout << merge_max_size << endl;
	cout << moduleRowId << " " << moduleColId << " " << (int)wall_to_remove << endl;

	file_in.close();
	file_out.close();
	return 0;
}


Castle castle_flood_fill()
{
	// initial all room component
	memset(room_component, -1, max_size * max_size * sizeof(int));

	// flood fill find component
	Castle info;
	for(int i=0; i<m; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(room_component[i][j] == -1)
			{
				int size = castle_flood_fill(i, j, info.num_rooms);
				info.rooms_size[info.num_rooms] = size;
				++info.num_rooms;
				info.largest_size = max(size, info.largest_size);
			}
		}
	}
	return info;
}

int castle_flood_fill(int i, int j, int roomId)
{
	if(room_component[i][j] != -1)
	{
		return 0;
	}

	int size = 1;
	room_component[i][j] = roomId;
	if((wall[i][j] & WEST) == 0)
		size += castle_flood_fill(i, j-1, roomId);
	if((wall[i][j] & NORTH) == 0)
		size += castle_flood_fill(i-1, j, roomId);
	if((wall[i][j] & EAST) == 0)
		size += castle_flood_fill(i, j+1, roomId);
	if((wall[i][j] & SOUTH) == 0)
		size += castle_flood_fill(i+1, j, roomId);
	return size;
}<file_sep>/section 1/barn1.cpp
/*
ID: luglian1
PROG: barn1
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <list>

using namespace std;

struct board{
	int start;
	int end;
	board(int s, int e): start(s), end(e) {}
};

bool compareboard(const board& b1, const board& b2){
	return b1.start < b2.start;
}

typedef list<board>::iterator BoardIt;

list<board>::iterator findMinGap(list<board>& boardlist){
	list<board>::iterator minit;
	int mingap = 200;
	list<board>::iterator it = boardlist.begin();
	for(int i=0; i!=boardlist.size()-1; ++i){
		int prend = it->end;
		int curstart = (++it)->start;
		if(curstart - prend < mingap ){
			mingap = curstart - prend;
			minit = it;
		}
	}
	return minit;
}

void margeBoard(BoardIt& minit, list<board>& boardlist){
	BoardIt tmpit = minit;
	--tmpit;
	if(tmpit != boardlist.end()){
		tmpit->end = minit->end;
		boardlist.erase(minit);
	}

}

int main(){
	ifstream file_in("barn1.in");
	ofstream file_out("barn1.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int m, s, c;
	file_in >> m >> s >> c;

	list<board> boardlist;
	for(int i=0; i!=c; ++i){
		int t;
		file_in >> t;
		boardlist.push_back(board(t, t));
	}
	boardlist.sort(compareboard);


	while(boardlist.size() > m){
		BoardIt minit = findMinGap(boardlist);
		margeBoard(minit, boardlist);
	}

	cout << boardlist.size() << endl;

	int size=0;
	for(BoardIt it = boardlist.begin(); it!=boardlist.end(); ++it){
		cout << it->start << " " << it->end << endl;
		size += it->end-it->start+1;
	}
	cout << size << endl;
	file_out << size << endl;
	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/fence.cpp
/*
ID: luglian1
PROG: fence
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <algorithm>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "fence"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAXN 500

using namespace std;

struct compare
{
	string itos(int i) const
	{
		string s;
		s += char(i % 10 + '0');
		i = i / 10;
		while(i > 0)
		{
			s += char(i % 10 + '0');
			i = i / 10;
		};
		return s;
	};

	bool operator()(const int& i, const int& j) const
	{
		return i<j;
		string a = itos(i);
		string b= itos(j);
		return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	};
};

int F;
set<int, compare> node;
map<int, int, compare> edges[MAXN+1];
vector<int> steps;


int degree[MAXN+1] = {0};
int adjacent[MAXN+1][MAXN+1] = {0};

bool load();
void save(ostream& out);
bool save();
void solve();
void solve2();

int main(){
	load();
	// solve();
	solve2();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> F;
	for(int i=0; i<F; ++i)
	{
		int n1, n2;
		file_in >> n1 >> n2;
		node.insert(n1);
		node.insert(n2);
		if(edges[n1].count(n2))
		{
			++edges[n1][n2];
		}
		else
		{
			edges[n1].insert(pair<int, int>(n2, 1));
		}
		if(edges[n2].count(n1))
		{
			++edges[n2][n1];
		}
		else
		{
			edges[n2].insert(pair<int, int>(n1, 1));
		}

		degree[n1]++;
		degree[n2]++;
		adjacent[n1][n2]++;
		adjacent[n2][n1]++;
	}

	return true;
}

void save(ostream& out)
{
	for(vector<int>::reverse_iterator it=steps.rbegin(); it!=steps.rend(); ++it)
	{
		out << *it << endl;
	}
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void dfs(int i)
{
	// PV(i)

	if(edges[i].size() == 0)
	{
		steps.push_back(i);
		// cout << "save " << i << endl;
		return;
	}
	else
	{
		while(edges[i].size() > 0)
		{
			int en = edges[i].begin()->first;
			--(edges[i].begin()->second);
			if(edges[i].begin()->second == 0)
			{
				edges[i].erase(edges[i].begin());
			}

			map<int, int, compare>::iterator it = edges[en].find(i);
			--(it->second);
			if(it->second == 0)
				edges[en].erase(it);
			dfs(en);
		}
		steps.push_back(i);
		// cout << "save " << i << endl;
	}
}

void solve()
{
	// find odd node
	int start = 0;
	for(set<int, compare>::const_iterator it=node.begin(); it!=node.end(); ++it)
	{
		if(edges[*it].size() % 2 != 0)
		{
			start = *it;
			break;
		}
	}

	PV(start)
	PV(*--node.end());

	string a = "01";
	string b = "4";
	PV(lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()));

	PV(compare().itos(123))

	PV(compare()(1, 2))
	PV(*(node.begin()))

	if(!start)
		start = *(node.begin());

	dfs(start);
}


void dfs2(int i)
{
	if(degree[i] == 0)
	{
		steps.push_back(i);
		return;
	}
	else
	{
		for(int j=1; j<=MAXN; ++j)
		{
			if(adjacent[i][j] > 0)
			{
				degree[i]--;
				degree[j]--;
				adjacent[i][j]--;
				adjacent[j][i]--;
				dfs2(j);
			}
		}
		steps.push_back(i);
	}
}

void solve2()
{
	int start = 0;
	for(int i=1; i<=MAXN; ++i)
	{
		if(start == 0 && degree[i] > 0)
			start = i;
		if(degree[i] % 2 != 0)
		{
			start = i;
			break;
		}
	}

	dfs2(start);
}


// Assuming you pick the lowest index vertex connected to each node, the Eulerian Path algorithm actually determines the path requested, although in the reverse direction. You must start the path determination at the lowest legal vertex for this to work.

// /* Prob #5: Riding the Fences */
// #include <stdio.h>
// #include <string.h>

// #define MAXI 500
// #define MAXF 1200
// char conn[MAXI][MAXI];
// int deg[MAXI];
// int nconn;

// int touched[MAXI];

// int path[MAXF];
// int plen;

// /* Sanity check routine */
// void fill(int loc)
//  {
//   int lv;

//   touched[loc] = 1;
//   for (lv = 0; lv < nconn; lv++)
//     if (conn[loc][lv] && !touched[lv])
//       fill(lv);
//  }

// /* Sanity check routine */
// int is_connected(int st)
//  {
//   int lv;
//   memset(touched, 0, sizeof(touched));
//   fill(st);
//   for (lv = 0; lv < nconn; lv++)
//     if (deg[lv] && !touched[lv])
//       return 0;
//   return 1;
//  }

// /* this is exactly the Eulerian Path algorithm */
// void find_path(int loc)
//  {
//   int lv;

//   for (lv = 0; lv < nconn; lv++)
//     if (conn[loc][lv])
//      {
//       /* delete edge */
//       conn[loc][lv]--;
//       conn[lv][loc]--;
//       deg[lv]--;
//       deg[loc]--;

//       /* find path from new location */
//       find_path(lv);
//      }

//   /* add this node to the `end' of the path */
//   path[plen++] = loc;
//  }

// int main(int argc, char **argv)
//  {
//   FILE *fin, *fout;
//   int nfen;
//   int lv;
//   int x, y;

//   if (argc == 1) 
//    {
//     if ((fin = fopen("fence.in", "r")) == NULL)
//      {
//       perror ("fopen fin");
//       exit(1);
//      }
//     if ((fout = fopen("fence.out", "w")) == NULL)
//      {
//       perror ("fopen fout");
//       exit(1);
//      }
//    } else {
//     if ((fin = fopen(argv[1], "r")) == NULL)
//      {
//       perror ("fopen fin filename");
//       exit(1);
//      }
//     fout = stdout;
//    }

//   fscanf (fin, "%d", &nfen);
//   for (lv = 0; lv < nfen; lv++)
//    {
//     fscanf (fin, "%d %d", &x, &y);
//     x--; y--;
//     conn[x][y]++;
//     conn[y][x]++;
//     deg[x]++;
//     deg[y]++;
//     if (x >= nconn) nconn = x+1;
//     if (y >= nconn) nconn = y+1;
//    }

//   /* find first node of odd degree */
//   for (lv = 0; lv < nconn; lv++)
//     if (deg[lv] % 2 == 1) break;
//   /* if no odd-degree node, find first node with non-zero degree */
//   if (lv >= nconn)
//     for (lv = 0; lv < nconn; lv++)
//       if (deg[lv]) break;
// #ifdef CHECKSANE
//   if (!is_connected(lv)) /* input sanity check */
//    {
//     fprintf (stderr, "Not connected?!?\n");
//     return 0;
//    }
// #endif

//   /* find the eulerian path */
//   find_path(lv); 

//   /* the path is discovered in reverse order */
//   for (lv = plen-1; lv >= 0; lv--)
//     fprintf (fout, "%i\n", path[lv]+1);
//   return 0;
//  }<file_sep>/README.md
USACO_practise
=================

This is my practice program files on USACO TRAINING<file_sep>/section2/holstein.cpp
/*
ID: luglian1
PROG: holstein
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>

using namespace std;

#define MAX_V 25
#define MAX_G 15

int v_num;
int varray[MAX_V];
int g_num;
int garrry[MAX_G][MAX_V];

int best_scoop_count;
bool best_scoops[MAX_G];
bool scoops[MAX_G];
int v_temp[MAX_V];

bool load()
{
	ifstream file_in("holstein.in");
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> v_num;
	for (int i = 0; i < v_num; ++i)
	{
		file_in >> varray[i];
	}

	file_in >> g_num;
	for (int i = 0; i < g_num; ++i)
	{
		for (int j = 0; j < v_num; ++j)
		{
			file_in >> garrry[i][j];
		}
	}

	return true;
}

void save(ostream& out)
{
	out << best_scoop_count;
	for (int i = 0; i < g_num; ++i)
	{
		if(best_scoops[i])
			out << " " << i+1;
	}
	out << endl;
}

bool save()
{
	ofstream file_out("holstein.out");
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void dfs_solve(int type_id, int scoops_count)
{
	// check over
	if(scoops_count >= best_scoop_count) 
		return;
	bool find = true;
	for (int i = 0; i < v_num; ++i)
	{
		if(v_temp[i] > 0)
		{
			find = false;
			break;
		}
	}
	if(find)
	{
		if(scoops_count < best_scoop_count)
		{
			memmove(best_scoops, scoops, g_num * sizeof(scoops[0]));
			best_scoop_count = scoops_count;
		}
	}
	else if(type_id < g_num)
	{
		// feed[type_id] is on
		scoops[type_id] = true;
		for (int i = 0; i < v_num; ++i)
		{
			v_temp[i] -= garrry[type_id][i];
		}
		dfs_solve(type_id+1, scoops_count+1);

		// feed[type_id] is off
		scoops[type_id] = false;
		for (int i = 0; i < v_num; ++i)
		{
			v_temp[i] += garrry[type_id][i];
		}
		dfs_solve(type_id+1, scoops_count);
	}
}

void solve()
{
	best_scoop_count = g_num+2;
	for (int i = 0; i < MAX_G; ++i)
	{
		best_scoops[i] = false;
	}
	memmove(v_temp, varray, v_num * sizeof(varray[0]));

	dfs_solve(0, 0);
}


int main(){
	load();


	solve();


	save();

	return 0;
}




<file_sep>/section 1/calfflac.cpp
/*
ID: luglian1
PROG: calfflac
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
	ifstream file_in("calfflac.in");
	ofstream file_out("calfflac.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		//return 0;
	}

	string all;
	string line;
	while(getline(file_in, line)){
		all += "\n" + line;
	}
	all += "\n";

	// get the char in [a-z][A-Z]
	string origin;
	vector<int> pos;	// remember the char position
	for(int i=0; i!=all.size(); ++i){
		char c = all.at(i);
		if( c >= 'A' && c <= 'Z'){
			origin += 'a' + c - 'A';
			pos.push_back(i);
		}
		else if( c >= 'a' && c<= 'z'){
			origin += c;
			pos.push_back(i);
		}
	}

	cout << origin << endl;
	// // reverse it
	// string reverse(origin);
	// reverse_copy(origin.begin(), origin.end(), reverse.begin());

	// cout << reverse << endl;

	// check the pos where origin[pos-1] == origin[pos+1]
	int maxlength=0;
	int tmplength;
	int maxspos=0;
	int endpos = -1;
	int startpos=0;
	for(int i=0; i!=origin.size()-1; ++i){
		if(origin[i-1] == origin[i+1]){
			startpos = endpos = i;
			while(startpos >=-1 && endpos<=origin.size() &&
				origin[startpos] == origin[endpos]){
				--startpos;
				++endpos;
			}
			tmplength = endpos - startpos -1;
			if(tmplength > maxlength){
				maxlength = tmplength;
				maxspos = startpos+1;
			}
		}
		if(origin[i] == origin[i+1]){
			startpos = i;
			endpos = i+1;
			while(startpos >=-1 && endpos<=origin.size() &&
				origin[startpos] == origin[endpos]){
				--startpos;
				++endpos;
			}
			tmplength = endpos - startpos - 1;
			if(tmplength > maxlength){
				maxlength = tmplength;
				maxspos = startpos+1;
			}
		}
	}


	// // get the max equal in origin and reverse
	// while(startpos < origin.size()){
	// 	while(origin[startpos] != reverse[startpos] && startpos < origin.size())
	// 		++startpos;
	// 	for(endpos = startpos; 
	// 		endpos < origin.size() && origin[endpos] == reverse[endpos]; 
	// 		++endpos);
	// 	if(endpos - startpos > maxlength){
	// 		maxlength = endpos - startpos;
	// 		maxspos = startpos;
	// 	}
	// 	startpos = endpos;
	// }


	cout << startpos << endl;
	cout << maxlength << endl;
	// get the original string
	int reallength = pos[maxspos+maxlength-1] - pos[maxspos]+1;
	cout << all.substr(pos[maxspos], reallength) << endl;

	file_out << maxlength << endl << all.substr(pos[maxspos], reallength) << endl;
	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/sprime.cpp
/*
ID: luglian1
PROG: sprime
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

class PrimeRib{
	vector<int> prime;
	int N;
public:
	PrimeRib(int n): N(n){
		prime.push_back(2);
		prime.push_back(3);
		int sq = sqrt(pow(10, n)) + 1;
		int cur = 5;
		while( cur <= sq ){
			if( checkPrime(cur) ){
				prime.push_back(cur);
			}
			cur += 2;
		}
	}

	bool checkPrime(int n){
		if(n == 1) return false;
		int sq = sqrt((double)n)+1;
		for(int i=0; i!=prime.size(); ++i){
			if(n == prime[i])
				return true;
			if(prime[i] > sq)
				break;
			if( n % prime[i] == 0)
				return false;
		}
		return true;
	}

	bool checkPrimeRib(int n){
		while(n > 0){
			if(!checkPrime(n))
				return false;
			n /= 10;
		}
		return true;
	}

	void workByadd2(ostream& file_out){
		int i=pow(10, N-1)+1;
		int end = pow(10, N);
		for(; i < end; i+=2){
			if(checkPrimeRib(i))
				file_out << i << endl;
		}
	}

	void workBybfs(int len, int n, ostream& file_out){
		if(n == 0 || checkPrime(n)){
			if(len <= 0){
				file_out << n << endl;
				return;
			}
			for(int i = 1; i<=9; i+=1){
				workBybfs(len-1, n*10+i, file_out);
			}
		}

	}

	void work(ostream& file_out){
		//workByadd2(file_out);
		workBybfs(N, 0, file_out);
		//cout << checkPrime(2) << endl;
	}
};


int main(){
	ifstream file_in("sprime.in");
	ofstream file_out("sprime.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int N;
	file_in >> N;
	PrimeRib pr(N);
	pr.work(file_out);

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/template.cpp
/*
ID: luglian1
PROG: beads
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int main(){
	ifstream file_in("beads.in");
	ofstream file_out("beads.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}


	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/msquare.cpp
/*
ID: luglian1
PROG: msquare
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <deque>
#include <cassert>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "msquare"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

struct node
{
	int move;
	string parent;
	int change;
	node(int m=0, const string& p="", int c=0):move(m), parent(p), change(c) {};
};

const string start("12345678");
map<string, node> m;
string target;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	string s;
	for(int i=0; i<8; ++i)
	{
		file_in >> s;
		target += s;
	}

	PV(target)

	return true;
}

void save(ostream& out)
{
	if(m.count(target)==0)
		return;
	string s("ABC");
	string outs;
	string cur = target;
	out << m[cur].move << endl;
	while(cur != "12345678")
	{
		outs.push_back(s[m[cur].change]);
		cur = m[cur].parent;
	}
	for(int i=outs.length()-1; i>=0; --i)
		out << outs[i];
	out << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


string movea(const string& s)
{
	string news(s);
	for(int i=0; i<4; ++i)
	{
		swap(news[i], news[7-i]);
	}
	return news;
}


string moveb(const string& s)
{
	string news(8, '0');

	news[0] = s[3]; news[1] = s[0]; news[2] = s[1]; news[3] = s[2];
	news[4] = s[5]; news[5] = s[6]; news[6] = s[7]; news[7] = s[4];

	return news;
}

string movec(const string& s)
{
	string news(s);
	news[1] = s[6]; news[2] = s[1]; news[5] = s[2]; news[6] = s[5];
	return news;
}

string (*funcs[3])(const string& s) = {movea, moveb, movec};

void dfs(int move, const string& parent)
{
	if(move > 19)
		return;
	for(int i=0; i<3; ++i)
	{
		string s = (*(funcs[i]))(parent);

		if(m.count(s) == 0)
		{
			m.insert(pair<string, node>(s, node(move+1, parent, i)));
			dfs(move+1, s);
		}
		else if(m[s].move > move + 1)
		{
			m[s].move = move+1;
			m[s].parent = parent;
			m[s].change = i;
			dfs(move+1, s);
		}
	}
}

void bfs()
{
	deque<string> ds;
	ds.push_back(start);

	while(ds.size() > 0)
	{
		string cur = ds[0];
		ds.pop_front();
		const node& n = m[cur];
		for(int i=0; i<3; ++i)
		{
			string s = (*(funcs[i]))(cur);
			if(m.count(s) == 0)
			{
				ds.push_back(s);
				m.insert(pair<string, node>(s, node(n.move+1, cur, i)));
			}
			if(s == target)
				return;
		}
	}

}

int encode(int *board)
 {
  static int mult[8] = 
    {1, 8, 8*7, 8*7*6, 8*7*6*5,
     8*7*6*5*4, 8*7*6*5*4*3, 8*7*6*5*4*3*2};
  
  /* used to calculate the position of a number within the
     remaining ones */
  int look[8] = {0, 1, 2, 3, 4, 5, 6, 7};
  int rlook[8] = {0, 1, 2, 3, 4, 5, 6, 7};
  /* rlook[look[p]] = p and look[rlook[p]] = p */

  int lv, rv;
  int t;

  rv = 0;
  for (lv = 0; lv < 8; lv++)
   {
    t = look[board[lv]]; /* the rank of the board position */
    // PV(t)
    assert(t < 8-lv); /* sanity check */
    rv += t * mult[lv]; 

    assert(look[rlook[7-lv]] == 7-lv); /* sanity check */

    /* delete t */
    look[rlook[7-lv]] = t;
    rlook[t] = rlook[7-lv];
    // PVL(look, 8)
    // PVL(rlook, 8)
   }
  return rv;
 }

void stob(const string& s, int* board)
{
	for(int i=0; i<8; ++i)
	{
		board[i] = (s[i] - '0') % 8;
	}
}

void solve()
{
	node root(0);
	m.insert(pair<string, node>(start, root));
	int board[8] = {1,0,6,5,4,3,2,7};
	PV(encode(board))

	bfs();
	map<int, string> mi;
	for(map<string, node>::iterator it=m.begin(); it!=m.end(); ++it)
	{
		stob(it->first, board);
		mi.insert(pair<int, string>(encode(board), it->first));
	}

	PV(mi[0])
	PV(mi[1])
	PV(mi[2])

	//dfs(0, "12345678");

	//PV(m.size())

	// PV(m.count(target))
	//while(m.size() < 40320)

}


// This is a shortest path problem, where the nodes of the graph are board arrangements, and edges are transformations. There are 8! = 40,320 possible board arrangements, so the problem can be solved using breadth-first search (since all edges are of unit length.

// Number the boards in increasing order lexicographically, so that indexing is simpler.

// In order to simplify the calculations, walk the path backward (start at the ending arrangement given, find the minimum path to the initial configuration following reverse transformations). Then, walk backwards in the resulting tree to determine the path.

// #include <stdio.h>
// #include <assert.h>

// /* the distance from the initial configuration (+1) */
// /* dist == 0 => no know path */
// int dist[40320];

// /* calculate the index of a board */
// int encode(int *board)
//  {
//   static int mult[8] = 
//     {1, 8, 8*7, 8*7*6, 8*7*6*5,
//      8*7*6*5*4, 8*7*6*5*4*3, 8*7*6*5*4*3*2};
  
//   /* used to calculate the position of a number within the
//      remaining ones */
//   int look[8] = {0, 1, 2, 3, 4, 5, 6, 7};
//   int rlook[8] = {0, 1, 2, 3, 4, 5, 6, 7};
//   /* rlook[look[p]] = p and look[rlook[p]] = p */

//   int lv, rv;
//   int t;

//   rv = 0;
//   for (lv = 0; lv < 8; lv++)
//    {
//     t = look[board[lv]]; /* the rank of the board position */
//     assert(t < 8-lv); /* sanity check */
//     rv += t * mult[lv]; 

//     assert(look[rlook[7-lv]] == 7-lv); /* sanity check */

//     /* delete t */
//     look[rlook[7-lv]] = t;
//     rlook[t] = rlook[7-lv];
//    }
//   return rv;
//  }

// /* the set of transformations, in order */
// static int tforms[3][8] = { {8, 7, 6, 5, 4, 3, 2, 1},
//      {4, 1, 2, 3, 6, 7, 8, 5}, {1, 7, 2, 4, 5, 3, 6, 8} };

// void do_trans(int *inboard, int *outboard, int t)
//  { /* calculate the board (into outboard) that results from doing
//       the t'th transformation to inboard */
//   int lv;
//   int *tform = tforms[t];

//   assert(t >= 0 && t < 3);

//   for (lv = 0; lv < 8; lv++)
//     outboard[lv] = inboard[tform[lv]-1];
//  }

// void do_rtrans(int *inboard, int *outboard, int t)
//  { /* calculate the board (into outboard) that which would result
//       in inboard if the t'th transformation was applied to it */
//   int lv;
//   int *tform = tforms[t];

//   assert(t >= 0 && t < 3);

//   for (lv = 0; lv < 8; lv++)
//     outboard[tform[lv]-1] = inboard[lv];
//  }

//  queue for breadth-first search 
// int queue[40325][8];
// int qhead, qtail;

// /* calculate the distance from each board to the ending board */
// void do_dist(int *board)
//  {
//   int lv;
//   int t1;
//   int d, t;

//   qhead = 0;
//   qtail = 1;

//   /* the ending board is 0 steps away from itself */
//   for (lv = 0; lv < 8; lv++) queue[0][lv] = board[lv];
//   dist[encode(queue[0])] = 1; /* 0 steps (+ 1 offset for dist array) */

//   while (qhead < qtail)
//    {
//     t1 = encode(queue[qhead]);
//     d = dist[t1];

//     /* for each transformation */
//     for (lv = 0; lv < 3; lv++)
//      {
//       /* apply the reverse transformation */
//       do_rtrans(queue[qhead], queue[qtail], lv);

//       t = encode(queue[qtail]);
//       if (dist[t] == 0) 
//        { /* found a new board position!  add it to queue */
//         qtail++;
//         dist[t] = d+1;
//        }
//      }

//     qhead++;
//    }
//  }

// /* find the path from the initial configuration to the ending board */
// void walk(FILE *fout)
//  {
//   int newboard[8];
//   int cboard[8];
//   int lv, lv2;
//   int t, d;

//   for (lv = 0; lv < 8; lv++) cboard[lv] = lv;
//   d = dist[encode(cboard)];
//   /* start at the ending board */
//   while (d > 1)
//    {
//     for (lv = 0; lv < 3; lv++)
//      {
//       do_trans(cboard, newboard, lv);
//       t = encode(newboard);
//       if (dist[t] == d-1) /* we found the previous board! */
//        {
//         /* output transformatino */
//         fprintf (fout, "%c", lv+'A');

// 	/* find the rest of the path */
//         for (lv2 = 0; lv2 < 8; lv2++) cboard[lv2] = newboard[lv2];
// 	break;
//        }
//      }
//     assert(lv < 3);
//     d--;
//    }
//   fprintf (fout, "\n");
//  }

// int main(int argc, char **argv)
//  {
//   FILE *fout, *fin;
//   int board[8];
//   int lv;

//   if ((fin = fopen("msquare.in", "r")) == NULL)
//    {
//     perror ("fopen fin");
//     exit(1);
//    }
//   if ((fout = fopen("msquare.out", "w")) == NULL)
//    {
//     perror ("fopen fout");
//     exit(1);
//    }

//   for (lv = 0; lv < 8; lv++) 
//    {
//     fscanf (fin, "%d", &board[lv]);
//     board[lv]--; /* use 0-based instead of 1-based */
//    }

//   /* calculate the distance from each board to the ending board */
//   do_dist(board);

//   for (lv = 0; lv < 8; lv++) board[lv] = lv;

//   /* output the distance from and the path from the initial configuration */
//   fprintf (fout, "%d\n", dist[encode(board)]-1);
//   walk(fout);

//   return 0;
//  }<file_sep>/mytest/sequences.cpp
// print string sequence
#include <iostream>
#include <string>
#include <fstream>
#include <ctime>

using namespace std;

ofstream file_out("sequences.out");

ostream& out = cout;//file_out;//
int num_string = 0;

void print(char* s, int cur_pos, int n)
{
	if(cur_pos == n)
	{
		s[cur_pos] = '\0';
		// if(num_string != 0)
		// 	out << ",";
		// num_string++;
		// out << "(";
		// for(int i=0; i<n-1; i++)
		// {
		// 	out  << s[i] << ",";
		// }
		// out << s[n-1] << ")";
		return;
	}

	for(s[cur_pos] = s[cur_pos-1] + 1; s[cur_pos] <= 'z'; s[cur_pos]++)
	{
		// lop
		if(n - cur_pos - 1 > 'z' - s[cur_pos])
			return;
		print(s, cur_pos+1, n);
	}
}

void calc(int len)
{
    // 初始化字符串（性质1）
    char digs[27] = "abcdefghijklmnopqrstuvwxyz";
    digs[len] = 0;

    bool flag = true;
    while (flag)
    {
        //printf("%s,", digs);

        flag = false;
        for (int i = len-1; i >= 0; i --)
        {
            // 字符串从低位往高位增，满足字典序（性质3）
            digs[i] ++;

            //满足该条件的，才能使字符依次递增
            if (digs[i] <= 'z'-(len-1-i))
            {
                // 字符是依次递增的（性质2）
                for (int j = i+1; j < len; j ++)
                    digs[j] = digs[j-1] + 1;
                flag = true;
                break;
            }
        }
      
    }
    printf("1\n");
}

int main()
{
	clock_t begin = clock();
	char s[1024];
	for(int n=1; n<=26; n++)
	{
		num_string = 0;
		for(char c = 'a'; c<='z'; c++)
		{
			s[0] = c;
			print(s, 1, n);
		}
		printf("1\n");
		//out << endl;
	}

	// for(int i=0; i<=26; i++)
	// {
	// 	calc(i);
	// }

	clock_t end = clock();
	double time = (double)(end - begin) / CLOCKS_PER_SEC;
}<file_sep>/section2/subset.cpp
/*
ID: luglian1
PROG: subset
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;
bool load();
void save(ostream& out);
bool save();
void buildTable();
void solve();

int M;
unsigned int num;
unsigned int table[40][801] = {0};	// table for num of set of sum n in m, table[m][n]

int main(){
	load();
	buildTable();
	solve();
	save();
	return 0;
}

void buildTable()
{
	table[1][0] = 1;
	table[1][1] = 1;
	for(int m=2; m <= 39; ++m)
	{
		int max = (m+1) * m / 2;
		for(int n=0; n<=max; ++n)
		{
			unsigned int num = 0;
			if(n - m >= 0)
				num += table[m-1][n-m];
			num += table[m-1][n];
			table[m][n] = num;
		}
	}

	// output table
	// ofstream file_out("subset_table.txt");
	// for(int m=1; m<40; ++m)
	// {
	// 	int max = (m+1) * m / 2;
	// 	for(int n=1; n<=max; ++n)
	// 	{
	// 		file_out << table[m][n] << " ";
	// 	}
	// 	file_out << endl;
	// }
	// file_out.close();
}

void solve()
{
	int sum = (M+1) * M / 2;
	cout << sum << endl;
	if(sum % 2 == 1)
	{
		num = 0;
		return;
	}
	sum /= 2;
	cout << sum << endl;
	cout << table[M][sum] << endl;
	num = table[M][sum] / 2;
}

bool load()
{
	ifstream file_in("subset.in");
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}
	file_in >> M;
	return true;
}

void save(ostream& out)
{
	out << num << endl;
}

bool save()
{
	ofstream file_out("subset.out");
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}
<file_sep>/section2/runround.cpp
/*
ID: luglian1
PROG: runround
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <string>
#include <sstream>
#include <cstdlib>
#define PV(v) std::cout << #v << " = " << v << std::endl;
using namespace std;
bool load();
void save(ostream& out);
bool save();
void solve();

int N;


int main(){
	load();
	solve();
	save();
	return 0;
}

bool checkRunAround(int n)
{
	stringstream ss;
	for(int i=0; i<9; ++i)
	{
		ss << n;
	}
	string s;
	ss >> s;

	if(s.find('0') != s.npos) return false;

	int count[10] = {0};
	int length = s.length() / 9;

	int curpos = 0;
	for(int i=0; i<length+1; ++i)
	{
		//PV(curpos);
		int curi = s[curpos]-'0';
		if(i == length)
		{
			if(curpos != 0)
				return false;
		}
		else
		{
			//PV(curi);
			if(count[curi] != 0)
				return false;
			count[curi] = 1;			
		}	
		curpos = s.find_first_of(s[curpos + curi]);
	}
	int sum = 0;
	for(int i=0; i<10; ++i)
	{
		sum += count[i];
	}
	if(sum != length)
		return false;
	return true;
}

int findLeastLarge(int a, int* count)
{
	for(int i = a+1; i < 10; ++i)
	{
		//PV(count[i]);
		if(count[i] == 0)
			return i;
	}
	return 0;
}

int generateNext(int n)
{
	stringstream ss;
	ss << n;
	string s = ss.str();
	int count[10] = {0};
	int replace_pos=0;
	// find repeat and count each unique num
	for(; replace_pos < s.length(); ++replace_pos)
	{
		int i = s[replace_pos] - '0';
		if(i == 0)
			break;
		if(count[i] == 1)
			break;
		++count[i];
	}
	//PV(replace_pos);
	// all nums are unique
	if(replace_pos == s.length())
		--replace_pos;
	
	for(int i=replace_pos; i>=-1; --i)
	{
		replace_pos = i;
		if(i == -1)
			break;
		int curi = s[i] - '0';
		if(findLeastLarge(curi, count) != 0)
		{
			break;
		}
		count[curi] = 0;
		//PV(curi);
	}
	

	if(replace_pos == -1)
	{
		s = "0" + s;
		replace_pos = 0;
	}
	//PV(s)
	//PV(s.length())
	//PV(replace_pos);
	int curi = s[replace_pos] - '0';
	int replacei = findLeastLarge(curi, count);
	//PV(curi);
	//PV(replacei);
	s[replace_pos] = (char)(replacei + '0');
	count[curi] = 0;
	count[replacei] = 1;
	int curpos = replace_pos + 1;
	for(int i = 1; i< 10; ++i)
	{
		if(count[i] == 0)
		{
			s[curpos] = (char)(i + '0');
			++curpos;
			if(curpos >= s.length())
				break;
		}
	}
	//PV(s)

	ss.str("");
	ss << s;
	ss >> n;
	return n;
}

void solve()
{

	N = generateNext(N);
	//PV(N);
	while(!checkRunAround(N))
	{
		N = generateNext(N);
		//PV(N);
	}
	//cout << __FUNCTION__  << endl;
}

bool load()
{
	ifstream file_in("runround.in");
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}
	file_in >> N;
	return true;
}

void save(ostream& out)
{
	out << N << endl;
}

bool save()
{
	ofstream file_out("runround.out");
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	//save(cout);

	return true;
}
<file_sep>/section2/preface.cpp
/*
ID: luglian1
PROG: preface
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cmath>
using namespace std;

struct IV
{
	int i_num = 0;
	int v_num = 0;
	int num9s = 0;
};

bool load();
void save(ostream& out);
bool save();
void solve();
void initial();
IV calculateIV(int n, int pos);
void print(int id);
void print(IV);

int N;
int I_table[10] = {0};
int I_allIn10;
int V_table[10] = {0};
int V_allin10;

IV iv_num[4];

int main(){
	load();
	solve();
	save();
	return 0;
}

// void print(int id)
// {
// 	cout << id;
// 	for(int i=0; i<4; ++i)
// 	{
// 		cout << (int)iv_num[i].i_name;
// 		cout << (int)iv_num[i].v_name;
// 	}
// 	cout << endl;
// }

ostream& operator<<(ostream& out, IV iv)
{
	out << iv.i_num << " " << iv.v_num << " " << iv.num9s;
	return out;
}

void solve()
{
	initial();
	
	int i=0;
	int num9s=0;

	int length = 0;
	int n = N;
	while(n>0)
	{
		++length;
		n = n / 10;
	}

	for(int i=0; i<length; ++i)
	{
		iv_num[i] = calculateIV(N, i);
		cout << i << ": " << iv_num[i] << endl;
		if(i > 0)
			iv_num[i].i_num += iv_num[i-1].num9s;
		cout << i << ": " << iv_num[i] << endl;
	}
}

IV calculateIV(int n, int pos)
{
	int apow = pow(10, pos);
	int cutNum = (n / apow) % 10;
	int numof10 = n / apow / 10;
	int rest = n % apow + 1;

	cout << pos << ": " << numof10 << " " << cutNum << " " << rest << endl;

	IV iv;

	if(numof10 > 0)
	{
		iv.i_num += I_allIn10 * numof10;
		iv.v_num += V_allin10 * numof10;
	}

	for(int i=0; i<cutNum; ++i)
	{
		iv.i_num += I_table[i];
		iv.v_num += V_table[i];
	}

	iv.num9s = numof10;

	iv.i_num *= apow;
	iv.v_num *= apow;
	iv.num9s *= apow;
	cout << iv.i_num << endl;
	iv.i_num += I_table[cutNum] * rest;
	iv.v_num += V_table[cutNum] * rest;
	cout << iv.i_num << endl;
	if(cutNum == 9)
		iv.num9s += rest;

	return iv;
}

void initial()
{
	for(int i=0; i<4; ++i)
		I_table[i] = i;
	I_table[4] = 1;
	for(int i=5; i<10; ++i)
		I_table[i] = I_table[i-5];
	I_allIn10 = 14;

	for(int i=4; i<=8; ++i)
		V_table[i] = 1;
	V_allin10 = 5;
}

bool load()
{
	ifstream file_in("preface.in");
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}
	file_in >> N;
	return true;
}

void save(ostream& out)
{
	char names[] = "IVXLCDMM";
	for(int i=0; i<4; ++i)
	{
		if(iv_num[i].i_num > 0)
			out << names[i*2] << " " << iv_num[i].i_num << endl;
		if(iv_num[i].v_num > 0)
			out << names[i*2+1] << " " << iv_num[i].v_num << endl;
	}
}

bool save()
{
	ofstream file_out("preface.out");
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}
<file_sep>/section 1/clocks.cpp
/*
ID: luglian1
PROG: clocks
LANG: C++
*/

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

template <typename T>
void printVector(const vector<T>& order){
	for(int i=0; i!=order.size(); ++i)
		cout << order[i] << " ";
	cout << endl;
}

int move[9][9] = {
	{3,3,0,3,3,0,0,0,0},
	{3,3,3,0,0,0,0,0,0},
	{0,3,3,0,3,3,0,0,0},
	{3,0,0,3,0,0,3,0,0},
	{0,3,0,3,3,3,0,3,0},
	{0,0,3,0,0,3,0,0,3},
	{0,0,0,3,3,0,3,3,0},
	{0,0,0,0,0,0,3,3,3},
	{0,0,0,0,3,3,0,3,3},
};

bool checkClocks(const vector<int>& clocks){
	if(clocks.size() != 9){
		cerr << "Error: clocks size is not accepted." << endl;
		return false;
	}
	for(int i=0; i<clocks.size(); ++i){
		if(clocks[i]%12 != 0)
			return false;
	}
	return true;
}

void clockChange(vector<int>& clocks, int moveid){
	for(int i=0; i!=9; ++i)
		clocks[i] = clocks[i] + move[moveid][i];
}

void clockUnChange(vector<int>& clocks, int moveid){
	for(int i=0; i!=9; ++i)
		clocks[i] = clocks[i] + 12 - move[moveid][i];
}

vector<vector<int> > pathset;

bool DFSIDsearchPath(vector<int>& clocks, vector<int>& path, int depth){
	if(depth == 0){
		if(checkClocks(clocks)){
			pathset.push_back(path);
			return true;
		}
		else
			return false;
	}
	
	for(int i=0; i!=9; ++i){
		path.push_back(i);
		clockChange(clocks, i);
		if(DFSIDsearchPath(clocks, path, depth-1))
			return true;
		clockUnChange(clocks, i);
		path.pop_back();
	}
	return false;
}

void DFSIDsearch(vector<int>& clocks){
	int depth = 1;
	vector<int> path;
	while(true){
		DFSIDsearchPath(clocks, path, depth);
		if(pathset.size() != 0)
			break;
		++depth;
		cout << "depth: " << depth << endl;
	}
}

deque<vector<int> > pathqueue;

void BFSprocess(vector<int>& onepath){
	for(int i=0; i!=9; ++i){
		onepath.push_back(i);
		pathqueue.push_back(onepath);
		onepath.pop_back();
	}

}

void BFSsearch(vector<int>& clocks){
	vector<int> onepath;
	pathqueue.push_back(onepath);

	while(pathset.size() == 0){
		onepath.swap(pathqueue.front());
		pathqueue.pop_front();
		vector<int> tmpc(clocks);
		for(int i=0; i!=onepath.size(); ++i)
			clockChange(tmpc, i);
		if(checkClocks(tmpc))
			break;
		BFSprocess(onepath);
	}
}

string pathToString(const vector<int>& path){
	stringstream ss;
	for(int i=8; i>=0; --i){
		int t = path[i];
		while(t>0){
			ss << 8-i+1;
			--t;
		}
	}
	string result;
	ss >> result;
	return result;
}

bool compareStringPath(const string& p1, const string& p2){
	if(p1.size() != p2.size())
		return p1.size() < p2.size();
	else
		return p1 < p2;
}

bool checkClocks(const vector<int>& clocks, const vector<int>& path){
	if(path.size() != 9 || clocks.size() != 9){
		return false;
	}
	vector<int> tmpclocks(clocks);
	//printVector(path);
	for(int i=8; i>=0; --i){
		int t = path[i];
		while(t>0){
			clockChange(tmpclocks, 8-i);
			--t;
		}
	}
	if(checkClocks(tmpclocks))
		return true;
	return false;
}

vector<int> origin_clocks;
vector<string> pathSetIns;
void generatePath(vector<int>& path){ // path show the times of each move, path[0]->move[8], path[8]->move[0]
	if(path.size() >= 9){
		if(checkClocks(origin_clocks, path)){
			pathSetIns.push_back(pathToString(path));
			//cout << pathSetIns.back() << endl;
		}
	}
	else{
		for(int i=0; i!=4; ++i){
			path.push_back(i);
			generatePath(path);
			path.pop_back();
		}
	}
}

void OptimizedSearch(){
	vector<int> path;
	generatePath(path);
	//cout << "over" << endl;
}

int main(){
	ifstream file_in("clocks.in");
	ofstream file_out("clocks.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	vector<int> clocks(9);
	for(int i=0; i!=9; ++i){
		file_in >> clocks[i];
		clocks[i] = clocks[i]%12;
	}
	
	// the complexity of DFS and BFS is too high!!
	//DFSIDsearch(clocks);
	//BFSsearch(clocks);

	// in fact it only needs 4^9 complexity
	origin_clocks.insert(origin_clocks.begin(), clocks.begin(), clocks.end());
	OptimizedSearch();
	//cout << "over" << endl;
	//cout << pathSetIns.size() << endl;

	// for(int i=0; i!=pathset.size(); ++i){
	// 	pathSetIns[i] = pathToString(pathset[i]);
	// 	//printVector(pathset[i]);
	// }
	sort(pathSetIns.begin(), pathSetIns.end(), compareStringPath);
	//printVector(pathSetIns);


	for(int i=0; i!=pathSetIns[0].size()-1; ++i)
		file_out << pathSetIns[0][i] << " ";
	file_out << pathSetIns[0][pathSetIns[0].size()-1] << endl;


	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/stamps.cpp
/*
ID: luglian1
PROG: stamps
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "stamps"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAXS 50
#define MAX_LEN 12000000

using namespace std;

int k, n;
int cent[MAXS] = {0};
int m=0;

unsigned char mink[MAX_LEN] = {0};

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> k >> n;
	for(int i=0; i<n; ++i)
		file_in >> cent[i];

	return true;
}

void save(ostream& out)
{
	out << m << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	sort(cent, cent+n);
	PVL(cent, n)

	if(cent[0] != 1)
		return;

	for(int i=0; i<n; ++i)
	{
		mink[cent[i]] = 1;
	}

	for(m=2; m<MAX_LEN; ++m)
	{
		if(mink[m])
			continue;

		int mm = k+1;
		for(int j=0; j<n; ++j)
		{
			if(m-cent[j] > 0)
			{
				mm = min(mm, mink[m-cent[j]] + 1);
			}
		}
		if(mm <= k)
			mink[m] = mm;
		else
			break;
	}

	m--;
}

// This problem is simply begging for a DP solution. We keep an array "minstamps" such that minstamps[i] is the minimum number of stamps needed to make i cents. For each stamp type, we try adding one stamp of that type to each number of cents that we have already made. After we have found the minimum number of stamps needed to make any given number of cents, we find the smallest number of cents that we cannot make with the given number of stamps, and then we output one less then that.

// #include <fstream.h>

// const int BIG = 10000;

// short   minstamps[10000 * (200 + 3) + 3];
// int     stamps;
// int     value[200];
// int     number;


// int 
// main ()
// {

//     ifstream filein ("stamps.in");
//     filein >> number >> stamps;
//     int     biggest = -1;
//     for (int i = 0; i < stamps; ++i) {
// 	filein >> value[i];
// 	if (biggest < value[i]) {
// 	    biggest = value[i];
// 	}
//     }
//     filein.close ();

//     for (int i = 0; i <= biggest * number + 3; ++i) {
// 	minstamps[i] = BIG;
//     }

//     minstamps[0] = 0;
//     for (int i = 0; i < stamps; ++i) {
// 	for (int j = 0; j <= biggest * number; ++j) {
// 	    if (minstamps[j] < number) {
// 		if (minstamps[j + value[i]] > 1 + minstamps[j]) {
// 		    minstamps[j + value[i]] = 1 + minstamps[j];
// 		}
// 	    }
// 	}
//     }


//     int     string = 0;
//     while (minstamps[string + 1] <= number) {
// 	++string;
//     }

//     ofstream fileout ("stamps.out");
//     fileout << string << endl;
//     fileout.close ();

//     return (0);
// }
<file_sep>/section2/money.cpp
/*
ID: luglian1
PROG: money
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "money"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

bool load();
void save(ostream& out);
bool save();
void solve();

int V;
int N;
int coin[26] = {0};
long long tb[26][10001] = {0};

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> V >> N;
	for(int i=1; i<=V; ++i)
	{
		file_in >> coin[i];
	}

	// PV(V)
	// PV(N)
	// PVL(coin, V+1)

	return true;
}

void save(ostream& out)
{
	out << tb[V][N] << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	//init
	for(int i=0; i<=N; ++i)
	{
		tb[1][i] = i % coin[1] == 0 ? 1 : 0;
	}

	for(int i=0; i<=V; ++i)
	{
		tb[i][0] = 1;
	}

	if(V == 1)
		return;

	for(int i=2; i<=V; ++i)
	{
		for(int j=coin[i]; j<=N; ++j)
		{
			tb[i][j] = tb[i-1][j];

			if(j-coin[i] >=0)
				tb[i][j] += tb[i][j-coin[i]];

			// for(int k=1; k<=j/coin[i]; ++k)
			// {
			// 	tb[i][j] += tb[i-1][j-coin[i]*k];
			// }

			// if(j % coin[i] == 0)
			// 	tb[i][j] += 1;
		}
	}

	// PVL(tb[1], N+1)
	// PVL(tb[2], N+1)
	// PVL(tb[3], N+1)

}

// 范例
// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXTOTAL 10000

// long long nway[MAXTOTAL+1];

// void
// main(void)
// {
// 	FILE *fin, *fout;
// 	int i, j, n, v, c;

// 	fin = fopen("money.in", "r");
// 	fout = fopen("money.out", "w");
// 	assert(fin != NULL && fout != NULL);

// 	fscanf(fin, "%d %d", &v, &n);

// 	nway[0] = 1;
// 	for(i=0; i<v; i++) {
// 		fscanf(fin, "%d", &c);

// 		for(j=c; j<=n; j++)
// 			nway[j] += nway[j-c];
// 	}

// 	fprintf(fout, "%lld\n", nway[n]);
// }<file_sep>/section2/sort3.cpp
/*
ID: luglian1
PROG: sort3
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

#define min(a, b)	(a)<(b)?(a):(b)

int sequences[1000];

// not correct
int Sequence()
{
	ifstream file_in("sort3.in");
	ofstream file_out("sort3.out");
	if(!file_in || !file_out)
	{
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	file_in >> n;
	int max=0;
	bool appear[] = {false, false, false, false};
	int count = 0;

	// read all the data first
	for(int i=0; i<n; i++)
	{
		file_in >> sequences[i];
	}
	
	// deal with 1 first
	int insert_pos = 0;
	int cur_pos = n-1;
	while(true)
	{
		for(;sequences[insert_pos] == 1 && insert_pos<n; insert_pos++);
		for(;sequences[cur_pos] != 1 && cur_pos>=0; cur_pos--);

		if(cur_pos > insert_pos)
		{
			int temp = sequences[insert_pos];
			sequences[insert_pos] = sequences[cur_pos];
			sequences[cur_pos] = temp;
			count ++;
		}
		else
			break;
	}

		for(int i=0; i<n; i++)
	{
		cout << sequences[i] << " ";
	}
	cout << endl;

	// deal with 2
	//insert_pos = 0;
	cur_pos = n-1;
	while(true)
	{
		for(;sequences[insert_pos] == 2 && insert_pos<n; insert_pos++);
		for(;sequences[cur_pos] != 2 && cur_pos>=0; cur_pos--);

		if(cur_pos > insert_pos)
		{
			int temp = sequences[insert_pos];
			sequences[insert_pos] = sequences[cur_pos];
			sequences[cur_pos] = temp;
			count ++;
		}
		else
			break;
	}

	//cout << count << endl;
	for(int i=0; i<n; i++)
	{
		cout << sequences[i] << " ";
	}
	file_out << count << endl;
	file_in.close();
	file_out.close();
	return count;
}

void printCount(int (*pos_count)[4])
{
	//return;
	for(int i=1; i<4; i++)
	{
		for(int j=1; j<4; j++)
			cout << pos_count[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}


//先交换那些一次交换就可以回到正确位置的数字
int Greed()
{
	ifstream file_in("sort3.in");
	ofstream file_out("sort3.out");
	if(!file_in || !file_out)
	{
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	file_in >> n;

	int change_count = 0;
	int count[4]={0};
	// read all the data first
	for(int i=0; i<n; i++)
	{
		file_in >> sequences[i];
		count[sequences[i]]++;
	}


	// 先找出1，2，3的个数，贪婪地先把一次交换可以是两个数字回到正确的位置上
	for(int i=1; i<4; i++)
		cout << count[i] << " ";
	cout << endl;

	//统计1位置上2，3的个数，2位置上1，3个数，3位置上1，2个数
	int pos_count[4][4] = {0};
	for(int i=1, pos=0; i<4; i++)
	{
		
		for(int j=pos; j<pos+count[i]; j++)
		{
			pos_count[i][sequences[j]]++;
		}
		pos += count[i];
	}
	printCount(pos_count);

	// 1, 3交换
	int change_pos[3][2] = 
	{
		{1, 3},
		{1, 2},
		{2, 3}
	};

	for(int i=0; i<3; i++)
	{
		int pos1 = change_pos[i][0];
		int pos2 = change_pos[i][1];
		int min_count = min(pos_count[pos1][pos2], pos_count[pos2][pos1]);
		pos_count[pos1][pos2] -= min_count;
		pos_count[pos2][pos1] -= min_count;
		pos_count[pos1][pos1] += min_count;
		pos_count[pos2][pos2] += min_count;
		printCount(pos_count);
		change_count += min_count;
	}

	for(int i=2; i<4; i++)
	{
		change_count += pos_count[1][i]*2;
	}

	cout << change_count << endl;
	file_out << change_count << endl;
	return change_count;
}


int main()
{
	Greed();
	//Sequence();
	return 0;
}
<file_sep>/section 1/beads.cpp
/*
ID: luglian1
PROG: beads
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int main(){
	ifstream file_in("beads.in");
	ofstream file_out("beads.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	string beads;
	file_in >> n >> beads;
	

	beads += beads;



	int maxn=0;
	bool one_color = true;
	for(int i=0; i!=beads.size()-1; ++i){
		if( beads.at(i) != beads.at(i+1) ){		// try break
			one_color = false;
			int newn=0;
			char onec = beads.at(i), otherc = beads.at(i+1);
			if(onec == 'r') otherc = 'b';
			if(onec == 'b') otherc = 'r';
			if(otherc == 'r') onec = 'b';
			if(otherc == 'b') onec = 'r';
			for(int j=i; j>-1; --j){
				if(beads.at(j) == onec || beads.at(j) == 'w')
					++ newn;
				else
					break;
			}
			for(int j=i+1; j < beads.size(); ++j){
				if(beads.at(j) == otherc || beads.at(j) == 'w')
					++ newn;
				else
					break;
			}
			maxn = maxn > newn ? maxn : newn;
		}
	}
	if(one_color || maxn > beads.size()/2)
		maxn = beads.size() / 2;
	file_out << maxn << endl;
	cout << maxn << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/transform.cpp
/*
ID: luglian1
PROG: transform
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

class Square;

class Square{
	int n;
	char data[10][10];
public:
	friend istream& operator>>(istream& ins, Square& s);
	friend ostream& operator<<(ostream& outs, Square& s);
	int size(){ return n; }
	Square(int size): n(size) { };
	Square(const Square& s): n(s.n){
		for(int i=0; i!=n; ++i){
			for(int j=0; j!=n; ++j){
				data[i][j] = s.data[i][j];
			}
		}
	}

	void rotate90(){
		// rotate in place
		for(int i = 0; i!= (n+1)/2; ++i){
			for(int j=0; j!=n/2; ++j){
				int tmp = data[i][j];
				data[i][j] = data[n-1-j][i];
				data[n-1-j][i] = data[n-1-i][n-1-j];
				data[n-1-i][n-1-j] = data[j][n-1-i];
				data[j][n-1-i] = tmp;
			}
		}
	}

	void reflect(){
		// reflect in place
		for(int i=0; i!=n; ++i){
			for(int j=0; j!=n/2; ++j){
				int tmp = data[i][j];
				data[i][j] = data[i][n-1-j];
				data[i][n-1-j] = tmp;
			}
		}
	}

	Square& operator=(const Square& rhs){
		n = rhs.n;
		for(int i=0; i!=n; ++i){
			for(int j=0; j!=n; ++j){
				data[i][j] = rhs.data[i][j];
			}
		}
	}

	bool operator==(const Square& rhs) const{
		if(n == rhs.n){
			for(int i=0; i!=n; ++i){
				for(int j=0; j!=n; ++j){
					if(data[i][j] != rhs.data[i][j])
						return false;
				}
			}
		}
		else
			return false;
		return true;
	}

};


istream& operator>>(istream& ins, Square& s){
	for(int i=0; i!=s.n; ++i){
		string line;
		ins >> line;
		for(int j=0; j!=s.n; ++j){
			s.data[i][j] = line.at(j);
		}
	}
	return ins;
}

ostream& operator<<(ostream& outs, Square& s){
	for(int i=0; i!=s.n; ++i){
		for(int j=0; j!=s.n; ++j){
			outs << s.data[i][j];
		}
		outs << endl;
	}
	return outs;
}



int main(){
	ifstream file_in("transform.in");
	ofstream file_out("transform.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	file_in >> n;
	Square origin(n);
	Square target(n);
	file_in >> origin >> target;

	cout << origin << target;
	// // test rotate
	// cout << origin << endl;
	// origin.rotate90();
	// cout << origin << endl;
	// // test reflect
	// origin.reflect();
	// cout << origin << endl;


	bool fit = false;
	int state=0;
	int return_s[] = {1, 2, 3, 4, 5, 5, 5, 6, 7};
	for(int i=0; i!=2; ++i){
		if(fit)	break;

		for(int j=0; j!=3; ++j){
			origin.rotate90();
			if( origin == target ){
				fit = true;
				break;
			}
			++state;
		}

		origin.rotate90();
		origin.reflect();
		if(origin == target){
			fit = true;
			break;
		}
		if(fit) break;
		++state;
	}

	file_out << return_s[state] << endl;
	cout << return_s[state] << endl;
	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/checker.cpp
/*
ID: luglian1
PROG: checker
LANG: C++
*/

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <vector>
using namespace std;

bool diagonal[200] = {false};
bool rediagonal[200] = {false};
bool col[100] = {false};

int n;
int count = 0;
int solution[100] = {0};
vector<string> prints;

void dfs(int row){
	if(row == n){
		++ count;
		if(count<4){
			stringstream ss;
			for(int i=0; i!=n-1; ++i)
				ss << solution[i]+1 << " ";
			ss << solution[n-1]+1;
			prints.push_back(ss.str());
		}
		return;
	}

	for(int i=0; i!=n; ++i){
		if(!col[i] && !diagonal[row-i+n] && !rediagonal[n-row-i+n] ){
			col[i] = true;
			diagonal[row-i+n] = true;
			rediagonal[n-row-i+n] = true;
			solution[row] = i;
			dfs(row+1);
			col[i] = false;
			diagonal[row-i+n] = false;
			rediagonal[n-row-i+n] = false;
		}
	}
}

void work(){
	dfs(0);
}

void print(ostream& file_out){
	for(int i=0; i!=prints.size(); ++i)
		file_out << prints[i] << endl;
	file_out << count << endl;
}

int main(){
	ifstream file_in("checker.in");
	ofstream file_out("checker.out");

	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	file_in >> n;

	work();
	print(file_out);

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/dualpal.cpp
/*
ID: luglian1
PROG: dualpal
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

bool checkPalindromic(const string& s){
	for(int i=0; i!=s.size()/2; ++i){
		if(s.at(i) != s.at(s.size()-i-1) )
			return false;
	}
	return true;
}

string digits = "0123456789ABCDEFGHIJKLMN";
string buildString(int i, int base){
	string res;
	int quo = i;
	while(quo > 0){
		res = digits.at(quo % base)+res;
		quo = quo / base;
	}
	return res;
}


int main(){
	ifstream file_in("dualpal.in");
	ofstream file_out("dualpal.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n, s;
	file_in >> n >> s;

	int num=s+1;
	vector<int> nv;
	while(nv.size() != n){
		int count=0;
		for(int base=2; base!=11; ++base){
			if(checkPalindromic(buildString(num, base)))
				++count;
			if(count >= 2){
				nv.push_back(num);
				break;
			}
		}
		++num;
	}

	for(int i=0; i!=nv.size(); ++i)
		file_out << nv[i] << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/ride.cpp
/*
ID: luglian1
PROG: ride
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>

using namespace std;


int main(){
	ifstream in("ride.in");
	ofstream out("ride.out");

	string comet, group;
	in >> comet >> group;
	
	int c=1, g=1;
	for(int i=0; i!=comet.size(); ++i){
		c = (c * (comet.at(i)-'A'+1)) % 47;
	}	
	for(int i=0; i!=group.size(); ++i){
		g = (g * (group.at(i)-'A'+1)) % 47;
	}

	if( c== g )
		out << "GO" << endl;
	else
		out << "STAY" << endl;

	in.close();
	out.close();
	return 0;
}<file_sep>/mytest/boost/array_test.cpp
#include <boost/array.hpp>
#include <iostream>

using namespace std;

int main()
{
	boost::array<int, 2> a;
	boost::array<int, 2> b = {1, 2};
	cout << 1 << endl;
	cout << a[0] << a[1] << endl;
	return 0;
}<file_sep>/section 1/milk3.cpp
/*
ID: luglian1
PROG: milk3
LANG: C++
*/

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <fstream>

using namespace std;


set<int> cset;
enum buckets {A=0, B, C};
int Capacity[3] = {0};
int cleft[21] = {0};

// failed, over time
int tf[21][21] = {0};
void searcha(int* cur, int depth){
	// if(depth <= 0)
	// 	return;
	if(tf[cur[0]][cur[1]] == 1)
		return;
	tf[cur[0]][cur[1]] = 1;
	if(cur[0] == 0){
		cleft[cur[2]] = 1;
	}
	for(int i=0; i!=3; ++i){
		if(cur[i] !=0){
			for(int j=0; j!=3; ++j){
				if(j == i) continue;
				int change = min(cur[i], Capacity[j]-cur[j]);
				cur[j] += change;
				cur[i] -= change;
				searcha(cur, depth-1);
				cur[i] += change;
				cur[j] -= change;
			}
		}
	}
}



// void searcha3(int i, int k){
// 	if()
// }

int gcd(int a, int b){
	if(b > a)
		swap(a, b);
	int rem = a%b;
	while(rem!=0){
		a = b;
		b = rem;
		rem = a % b;
	}
	return b;
}

void pours(int* cur, int from, int to){
	if(from == to)
		return;
	int change = min(cur[from], Capacity[to]-cur[to]);
	cur[to] += change;
	cur[from] -= change;
}

// 
void searcha2(int* cur, int depth){
	int tmpcur[3];
	copy(cur, cur+3, tmpcur);

	for(int i = depth*3+2; i>=1; --i){
		if(tmpcur[0] == 0)
			cleft[tmpcur[2]] = 1;
		pours(tmpcur, i%3, (i-1)%3);
	}

	copy(cur, cur+3, tmpcur);
	for(int i = 2; i<=depth*3+1; ++i){
		if(tmpcur[0] == 0)
			cleft[tmpcur[2]] = 1;
		pours(tmpcur, i%3, (i+1)%3);
	}
}

int main(){
	ifstream file_in("milk3.in");
	ofstream file_out("milk3.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	for(int i=0; i!=3; ++i)
		file_in >> Capacity[i];

	int cur[3] = {0};
	cur[2] = Capacity[2];

	searcha(cur, 13);
	//searcha2(cur, 12);

	// if(Capacity[0] <= Capacity[1]/2 ){
	// 	for(int i=Capacity[2]-Capacity[1]; i<=Capacity[2]; ++i)
	// 		cleft[i] = 1;
	// }

	vector<int> cvec;
	for(int i=0; i!=21; ++i){
		if(cleft[i] == 1){
			cvec.push_back(i);
			cout << i << endl;
		}
	}

	cout << cvec.size() << endl;
	for(int i=0; i!=cvec.size()-1; ++i)
		file_out << cvec[i] << " ";
	file_out << cvec.back() << endl;
	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section2/nocows.cpp
/*
ID: luglian1
PROG: nocows
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "nocows"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

int N = 0;		// [3, 199]
int K = 0;		// [2, 99]
int count = 0;
int tab[100][200];	// [k, n] count

int nc[100][200];	// [n, <=k] count

bool load();
void save(ostream& out);
bool save();
void solve();
int cc();

int main(){
	load();
	solve();
	//cc();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N >> K;

	for(int i=0; i<100; i++)
		for(int j=0; j<200; j++)
		{
			tab[i][j] = 0;
			nc[i][j] = 0;
		}

	return true;
}

void save(ostream& out)
{
	out << tab[K][N] << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	tab[1][1] = 1;
	//nc[2][1] = 1;
	for(int k=2; k<100; k++)
	{
		int minn = k * 2 - 1;
		int maxn = 200;
		if(k < 8)
			maxn = 1 << k;
		int i = k-1;
		//PV(k)
		for(int m = 1; m < 200; m++)
		{
			for(int ni = i-1; ni>=0; ni--)
				nc[i][m] += tab[ni][m];

			nc[i][m] = nc[i][m] % 9901;
		}

		for(int n = minn; n < maxn; n += 2)
		{
			//PV(n)
			int sum = 0;

			for(int m = n-2; m >= 1; m--)
			{
				//PV(m)
				int rightm = n-1-m;
				int add = 0;
				add += tab[i][m] * nc[i][rightm] % 9901;
				add += tab[i][rightm] * nc[i][m] % 9901;
				add += tab[i][m] * tab[i][rightm] % 9901;

				sum += add % 9901;

			}
			tab[k][n] = sum % 9901;
			//cout << k << ", " << n << ", " << tab[k][n] << endl;
		}
	}

	for(int k=1; k<100; k++)
	{
		for(int n=0; n<200; n++)
			cout << "[" << n << "]" << tab[k][n] << ", ";
		cout << endl;
	}
	cout << endl;
	for(int k=1; k<100; k++)
	{
		for(int n=0; n<200; n++)
			cout << "[" << n << "]" << nc[k][n] << ", ";
		cout << endl;
	}
}



int cc()
{
    ifstream fin("nocows.in");
    ofstream fout("nocows.out");
    int n,k,dp[200][200];  
    fin>>n>>k;
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    for (int i=3;i<=n;i+=2)
        for (int j=1;j<=i-2;j+=2)
            for (int k1=1;k1<=(j+1)/2;k1++)
                for (int k2=1;k2<=(i-j)/2;k2++)
                {
                    dp[i][max(k1,k2)+1]+=dp[j][k1]*dp[i-j-1][k2];
                    dp[i][max(k1,k2)+1]%=9901;
                }

	for(int k=1; k<100; k++)
	{
		for(int n=0; n<200; n++)
			cout << "[" << n << "]" << dp[n][k] << ", ";
		cout << endl;
	}

    fout<<dp[n][k]<<endl;
    cout<<dp[n][k]<<endl;

    return 0;
}<file_sep>/section2/concom.cpp
/*
ID: luglian1
PROG: concom
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "concom"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

bool load();
void save(ostream& out);
bool save();
void solve();

int N = 0;
int x[101][101] = {0};
int c[101][101] = {0};

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;
	for(int i=0; i<N; ++i)
	{
		int a, b, c;
		file_in >> a >> b >> c;
		x[a][b] = c;
	}
	return true;
}

void save(ostream& out)
{
	for(int i=1; i<=100; ++i)
		for(int j=1; j<=100; ++j)
		{
			if(i == j)
				continue;
			if(c[i][j])
			{
				out << i << " " << j << endl;
			}
		}
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	for(int t=0; t<100; ++t)
	{
		for(int i=1; i<=100; ++i)
			for(int j=1; j<=100; ++j)
			{
				if(c[i][j])
					continue;

				int xall = x[i][j];
				for(int k=1; k<=100; ++k)
				{
					if(c[i][k])
						xall += x[k][j];
				}
				if(xall >= 50)
				{
					c[i][j] = 1;
				}
			}
	}
}


// example
// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define NCOM 101

// int owns[NCOM][NCOM];        /* [i,j]: how much of j do i and its
//                                 controlled companies own? */
// int controls[NCOM][NCOM];    /* [i, j]: does i control j? */

// /* update info: now i controls j */
// void
// addcontroller(int i, int j)
// {
//     int k;

//     if(controls[i][j])        /* already knew that */
//         return;

//     controls[i][j] = 1;

//     /* now that i controls j, add to i's holdings everything from j */
//     for(k=0; k<NCOM; k++)
//         owns[i][k] += owns[j][k];

//     /* record the fact that controllers of i now control j */
//     for(k=0; k<NCOM; k++)
//         if(controls[k][i])
//             addcontroller(k, j);

//     /* if i now controls more companies, record that fact */
//     for(k=0; k<NCOM; k++)
//         if(owns[i][k] > 50)
//             addcontroller(i, k);
// }

// /* update info: i owns p% of j */
// void
// addowner(int i, int j, int p)
// {
//     int k;

//     /* add p% of j to each controller of i */
//     for(k=0; k<NCOM; k++)
//         if(controls[k][i])
//             owns[k][j] += p;

//     /* look for new controllers of j */
//     for(k=0; k<NCOM; k++)
//         if(owns[k][j] > 50)
//             addcontroller(k, j);
// }

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, j, n, a, b, p;

//     fin = fopen("concom.in", "r");
//     fout = fopen("concom.out", "w");
//     assert(fin != NULL && fout != NULL);

//     for(i=0; i<NCOM; i++)
//         controls[i][i] = 1;

//     fscanf(fin, "%d", &n);
//     for(i=0; i<n; i++) {
//         fscanf(fin, "%d %d %d", &a, &b, &p);
//         addowner(a, b, p);
//     }

//     for(i=0; i<NCOM; i++)
//     for(j=0; j<NCOM; j++)
//         if(i != j && controls[i][j])
//             fprintf(fout, "%d %d\n", i, j);
//     exit(0);
// }<file_sep>/section2/comehome.cpp
/*
ID: luglian1
PROG: comehome
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "comehome"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAX_DIS 10000000
#define LEN	58

using namespace std;

int n=0;
int g[LEN][LEN] = {0};
int path[LEN] = {0};
int res = 0;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> n;
	for(int i=0; i<n; ++i)
	{
		char a, b;
		int dis;
		file_in >> a >> b >> dis;

		a = a - 'A';
		b = b - 'A';
		if(g[a][b] == 0 || dis < g[a][b])
		{
			g[a][b] = g[b][a] = dis;
			// cout << int(a) << ", " << int(b) << ", " << dis << endl;;
		}
	}

	// PVL(g[0], LEN)
	// PV(g[0][57])

	return true;
}

void save(ostream& out)
{
	out << char('A' + res) << " " << g[25][res] << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	for(int i=0; i<LEN; ++i)
	{
		path[i] = MAX_DIS;
		for(int j=0; j<LEN; ++j)
			if(g[i][j] == 0)
				g[i][j] = MAX_DIS;
		g[i][i] = 0;
	}

	int src = 25;

	path[src] = 0;

	for(int k=0; k<LEN; ++k)
	for(int i=0; i<LEN; ++i)
	{
		for(int j=0; j<LEN; ++j)
		{
			int newd = g[i][k] + g[k][j];
			if(newd < g[i][j])
				g[i][j] = newd;
		}
	}

	// PVL(g[src], LEN)

	int mind = MAX_DIS;
	for(int i=0; i<src; ++i)
	{
		if(i == src)
			continue;
		if(g[src][i] < mind)
		{
			mind = g[src][i];
			res = i;
		}
	}

	// PV(res)
}


// We use the Floyd-Warshall all pairs shortest path algorithm to calculate the minimum distance between the barn and all other points in the pasture. Then we scan through all the cow-containing pastures looking for the minimum distance.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>
// #include <ctype.h>

// #define INF 60000	/* bigger than longest possible path */

// int dist[52][52];

// int
// char2num(char c)
// {
//     assert(isalpha(c));

//     if(isupper(c))
// 	return c-'A';
//     else
// 	return c-'a'+26;
// }

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, j, k, npath, d;
//     char a, b;
//     int m;

//     fin = fopen("comehome.in", "r");
//     fout = fopen("comehome.out", "w");
//     assert(fin != NULL && fout != NULL);

//     for(i=0; i<52; i++)
//     for(j=0; j<52; j++)
// 	dist[i][j] = INF;

//     for(i=0; i<26; i++)
// 	dist[i][i] = 0;

//     fscanf(fin, "%d\n", &npath);
//     for(i=0; i<npath; i++) {
// 	fscanf(fin, "%c %c %d\n", &a, &b, &d);
// 	a = char2num(a);
// 	b = char2num(b);
// 	if(dist[a][b] > d)
// 	    dist[a][b] = dist[b][a] = d;
//     }

//     /* floyd warshall all pair shortest path */
//     for(k=0; k<52; k++)
//     for(i=0; i<52; i++)
//     for(j=0; j<52; j++)
// 	if(dist[i][k]+dist[k][j] < dist[i][j])
// 	    dist[i][j] = dist[i][k]+dist[k][j];

//     /* find closest cow */
//     m = INF;
//     a = '#';
//     for(i='A'; i<='Y'; i++) {
// 	d = dist[char2num(i)][char2num('Z')];
// 	if(d < m) {
// 	    m = d;
// 	    a = i;
// 	}
//     }

//     fprintf(fout, "%c %d\n", a, m);
//     exit(0);
// }
// Analysis of and code for Bessie Come Home by <NAME> of The Netherlands

// When looking at the problem the first thing you can conclude is that for the solution you will need to know all the distances from the pastures to the barn. After calculating them you only have to check all these distances and pick out the nearest pasture with a cow in it, and that's all.

// Because the amount of vertices (=pastures+barn) is small, running Floyd/Warshall algorithm will solve the problem easily in time. If you think programming Floyd/Warshall is easier than Dijkstra, just do it. But you can also solve the problem running Dijkstra once, which of course speeds up your program quite a bit. Just initialise the barn as starting point, and the algorithm will find the distances from the barn to all the pastures which is the same as the distances from all the pastures to the barn because the graph is undirected. Using dijkstra for the solution would make far more complex data solvable within time. Here below you can see my implementation of this solution in Pascal. It might look big, but this way of partitioning your program keeps it easy to debug.

// Var Dist:Array [1..58] of LongInt;      {Array with distances to barn}
//     Vis :Array [1..58] of Boolean;      {Array keeping track which
// pastures visited}
//     Conn:Array [1..58,1..58] of Word;   {Matrix with length of edges, 0 = no edge}

// Procedure Load;
// Var TF   :Text;
//     X,D,E:Word;
//     P1,P2:Char;

// Begin
//  Assign(TF,'comehome.in');
//  Reset(TF);
//  Readln(TF,E);                          {Read number of edges}
//  For X:=1 to E do
//  Begin
//   Read(TF,P1);                          {Read both pastures and edge
// length}
//   Read(TF,P2);
//   Read(TF,P2);      {Add edge in matrix if no edge between P1 and P2 yet or}
//   Readln(TF,D);     {this edge is shorter than the shortest till now}
//   If (Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]=0) or
//      (Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]>D) then
//   Begin
//    Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]:=D;
//    Conn[Ord(P2)-Ord('A')+1,Ord(P1)-Ord('A')+1]:=D;
//   End;
//  End;
//  Close(TF);
//  For X:=1 to 58 do
//   Dist[X]:=2147483647;                  {Set all distances to infinity}
//  Dist[Ord('Z')-Ord('A')+1]:=0;          {Set distance from barn to barn to 0}
// End;

// Procedure Solve;
// Var X,P,D:LongInt;                      {P = pasture and D = distance}

// Begin
//  Repeat
//   P:=0;
//   D:=2147483647;
//   For X:=1 to 58 do                     {Find nearest pasture not
// visited yet}
//    If Not Vis[X] and (Dist[X]<D) then
//    Begin
//     P:=X;
//     D:=Dist[X];
//    End;
//   If (P<>0) then
//   Begin
//    Vis[P]:=True;                        {If there is one mark it
// visited}
//    For X:=1 to 58 do                    {And update all distances}
//     If (Conn[P,X]<>0) and (Dist[X]>Dist[P]+Conn[P,X]) then
//      Dist[X]:=Dist[P]+Conn[P,X];
//   End;
//  Until (P=0);                {Until no reachable and unvisited pastures
// left}
// End;

// Procedure Save;
// Var TF  :Text;
//     X,BD:LongInt;                       {BD = best distance}
//     BP  :Char;                          {BP = best pasture}

// Begin
//  BD:=2147483647;
//  For X:=1 to 25 do                      {Find neares pasture}
//   If (Dist[X]<BD) then
//   Begin
//    BD:=Dist[X];
//    BP:=Chr(Ord('A')+X-1);
//   End;
//  Assign(TF,'comehome.out');
//  Rewrite(TF);
//  Writeln(TF,BP,' ',BD);                 {Write outcome to disk}
//  Close(TF);
// End;

// Begin
//  Load;
//  Solve;
//  Save;
// End.<file_sep>/section3/camelot.cpp
/*
ID: luglian1
PROG: camelot
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << (v)[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "camelot"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAX_ROW 30
#define MAX_COL 26
#define MAX_SIZE MAX_ROW * MAX_COL
#define INF 0x7ffffffe
typedef unsigned int uint;

using namespace std;

int row = 0, col = 0;
int maxs = 0;
uint res = 0;
uint grid[MAX_SIZE][MAX_SIZE] = {0};

int king = 0;
vector<int> knight;

bool load();
void save(ostream& out);
bool save();
void solve();
void solve2();

int main(){
	load();
	solve2();

	save();
	return 0;
}


int getPos(int r, const string& c)
{
	return (r-1) * col + c[0] - 'A';
}

void getrc(int pos, int& r, int& c)
{
	r = pos / col;
	c = pos - r * col;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> row >> col;

	maxs = row * col;

	int r;
	string c;
	file_in >> c >> r;

	king = getPos(r, c);

	set<int> sk;

	while(file_in.eof() == 0)
	{
		file_in >> c;
		file_in >> r;
		//knight.push_back(getPos(r, c));
		sk.insert(getPos(r, c));
	}


	// for(int i=0; i<maxs; ++i)
	// {
	// 	if(sk.count(i) == 0)
	// 	{
	// 		PV(i)
	// 		sk.insert(i);
	// 	}
	// }

	for(set<int>::iterator it=sk.begin(); it!=sk.end(); ++it)
		knight.push_back(*it);

	PV(row)
	PV(col)
	PV(maxs)
	PV(king)
	PV(knight.size())
	PVL(knight, knight.size())
	return true;
}

void save(ostream& out)
{
	out << res << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


int near[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {1, 2}, {2, 1}};
int neardiff[8] = {0};
int vn[MAX_SIZE];
int mark[MAX_SIZE];
int vton[MAX_SIZE];

inline bool compare(int src, int i, int j)
{
	return grid[src][i] > grid[src][j];
}

vector<int> find_near(int c)
{
	vector<int> res;
	for(int i=0; i<8; ++i)
	{
		int n = c + neardiff[i];
		if(n < 0 || n >= maxs)
			continue;
		res.push_back(n);
	}
	return res;
}

inline void my_swap(int i, int j)
{
	swap(vn[i], vn[j]);
	swap(vton[vn[i]], vton[vn[j]]);
}

void goup_heap(int src, int i)
{
	int p=i;
	do
	{

		p = (i - 1) / 2;

		if(p >=0 && compare(src, vn[p], vn[i]))
		{
			my_swap(p, i);
			i = p;
		}
		else
		{
			break;
		}

	}while(i > 0);

}

void godown_heap(int src, int i, int n)
{
	int p = i;
	do
	{
		int ch1 = 2 * p + 1;
		int ch2 = 2 * p + 2;
		int min = p;

		if(ch2 < n)
		{
			if(compare(src, vn[p], vn[ch1]) && compare(src, vn[ch2], vn[ch1]))
				min = ch1;
			else if(compare(src, vn[p], vn[ch2]))
				min = ch2;
		}
		else if(ch1 < n)
		{
			if(compare(src, vn[p], vn[ch1]))
				min = ch1;
		}
		else
		{
			break;
		}

		if(min == p || min >= n)
		{
			break;
		}

		//assert(dist[cur_src][vn[min]] < dist[cur_src][vn[p]]);
		my_swap(p, min);

		p = min;
	}while(p < n);
}

void my_pop_heap(int src, int n)
{
	my_swap(0, n-1);
	godown_heap(src, 0, n-1);
}

void dijkstra(int src)
{
	for(int i=0; i<maxs; ++i)
	{
		vn[i] = i;
	}
	for(int i=0; i<maxs; ++i)
	{
		vton[vn[i]] = i;
	}
	vector<int> ns = find_near(src);

	grid[src][src] = 0;
	goup_heap(src, src);

	for(vector<int>::iterator it=ns.begin(); it!=ns.end(); ++it)
	{
		grid[src][*it] = 1;
		goup_heap(src, *it);

	}

	for(int i=maxs; i>0; --i)
	{

		int n = vn[0];

		my_pop_heap(src, i);

		for(int j=0; j<8; ++j)
		{
			int next = n + neardiff[j];
			if(next < 0 || next >= maxs)
				continue;
			

			if(vton[next] <= i-1 && grid[src][n] + 1 < grid[src][next])
			{
				grid[src][next] = grid[src][n] + 1;
				goup_heap(src, vton[next]);
			}
		}
	}
}

void solve()
{
	for(int i=0; i<maxs; ++i)
		for(int j=0; j<maxs; ++j)
			grid[i][j] = INF;


	for(int i=0; i<8; ++i)
	{
		neardiff[i] = near[i][0] * row + near[i][1];
	}
	PVL(neardiff, 8)

	for(int i=0; i<knight.size(); ++i)
	{
		dijkstra(knight[i]);
	}

	for(int i=0; i<knight.size(); ++i)
	{
		PVL(grid[knight[i]], maxs)
	}

}


void bfs(int src)
{
	queue<int> node;
	node.push(src);
	grid[src][src] = 0;

	while(!node.empty())
	{
		int cur = node.front();
		int r, c;
		getrc(cur, r, c);
		node.pop();
		int move = grid[src][cur];
		for(int j=0; j<8; ++j)
		{
			// int nr = r + near[j][0];
			// int nc = c + near[j][1];

			// if (nr < 0 || nr >= row || nc < 0 || nc >=col)
			// 	continue;			

			// int next = nr * col + nc;
			// if(grid[src][next] < INF)
			// 	continue;

			int next = cur + neardiff[j];

			if(next < 0 || next >= maxs || grid[src][next] < INF || 
				r + near[j][0] < 0 || r + near[j][0] >= row || 
				c + near[j][1] < 0 || c + near[j][1] >=col)
				continue;

			grid[src][next] = move + 1;
			node.push(next);
			// PV(next)
			// PV(grid[src][next])
		}
	}
}

int near_knight[MAX_SIZE];
uint king_grid[MAX_SIZE][MAX_SIZE] = {0};
uint res_grid[MAX_SIZE] = {0};

int king_dist(int src, int dst)
{
	int sr, sc;
	getrc(src, sr, sc);
	int dr, dc;
	getrc(dst, dr, dc);

	int r = abs(dr - sr);
	int c = abs(dc - sc);
	return r + c - min(r, c);
}

void king_path()
{
	for(int i=0; i<maxs; ++i)
		for(int j=0; j<maxs; ++j)
			king_grid[i][j] = king_dist(i, j);
}

void solve2()
{
	for(int i=0; i<maxs; ++i)
		for(int j=0; j<maxs; ++j)
			{
				grid[i][j] = INF;
				king_grid[i][j] = INF;
			}


	for(int i=0; i<8; ++i)
	{
		neardiff[i] = near[i][0] * col + near[i][1];
	}

	// PVL(neardiff, 8)

	for(int i=0; i<maxs; ++i)
	{
		bfs(i);
	}

	// PVL(near_knight, maxs)

	// for(int i=0; i<knight.size(); ++i)
	// {
	// 	PVL(grid[knight[i]], maxs)
	// }

	king_path();

	PVL(king_grid[0], maxs)

	if(knight.empty())
		return;

	for(int i=0; i<maxs; ++i)
	{
		res_grid[i] = 0;//king_grid[king][i];
		for(int j=0; j<knight.size(); ++j)
		{
			res_grid[i] += grid[knight[j]][i];
		}
		// PV(res_grid[i])
	}

	PVL(res_grid, maxs)

	vector<int> search_pos;
	int kr, kc;
	getrc(king, kr, kc);
	int range = 3;
	for(int i=-range; i<=range; ++i)
	{
		for(int j=-range; j<=range; ++j)
		{
			int r = kr + i;
			int c = kc + j;
			if(r  < 0 || r >= row || c < 0 || c >=col)
				continue;
			search_pos.push_back(r * col + c);
		}
	}

	PVL(search_pos, search_pos.size())

	res = INF;
	uint minp = 0;
	for(int i=0; i<maxs; ++i)
	{
		int mind = INF;

		for(vector<int>::iterator itj=search_pos.begin(); itj!=search_pos.end(); ++itj)
		//for(int j=0; j<maxs; ++j)
		{
			int j = *itj;
			for(int k=0; k<knight.size(); ++k)
			{
				int kn = knight[k];
				long long d = king_grid[king][j] + grid[kn][j] + grid[j][i] - grid[kn][i];
				if(d < mind)
					mind = d;
			}
		}

		// // if(mind < 0)

		res_grid[i] = res_grid[i] + mind;

		if(res_grid[i] < res)
		{
			res = res_grid[i];
			minp = i;
		}
	}

	int r, c;
	getrc(minp, r, c);
	PV(minp)
	PV(r)
	PV(c)

	// bfs(knight[0]);
	// PVL(grid[knight[0]], maxs)

}


// This is a modification of the shortest path algorithm. If there was no king, then the shortest path algorithm can determine the distance that each knight must travel to get to each square. Thus, the cost of gathering in a particular square is simply the sum of the distance that each knight must travel, which is fairly simple to calculate.

// In order to consider the king, consider a knight which 'picks-up' the king in some square and then travels to the gathering spot. This costs some number of extra moves than just traveling to the gathering spot. In particular, the king must move to the pick-up square, and the knight must travel to this square and then to the final gathering point. Consider the number of extra moves to be the `cost' for that knight to pick-up the king. It is simple to alter the shortest path algorithm to consider picking-up the king by augmenting the state with a boolean flag stating whether the knight has the king or not.

// In this case, the cost for gathering at a particular location is the sum of the distance that each knight must travel to get to that square plus the minimum cost for a knight picking up the king on the way.

// Thus, for each square, we keep two numbers, the sum of the distance that all the knights that we have seen thus far would have to travel to get to this square and the minimum cost for one of those knights picking up the king on the way (note that one way to 'pick-up' the king is to have the king travel all by itself to the gathering spot). Then, when we get a new knight, we run the shortest path algorithm and add the cost of getting that knight (without picking up the king) to each square to the cost of gathering at that location. Additionally, for each square, we check if the new knight can pick-up the king in fewer moves than any previous knight, and update that value if it can.

// After all the knights have been processed, we determine the minimum over all squares of the cost to get to that square plus the additional cost for a knight to pick-up the king on its way to that square.

// #include <stdio.h>
// #include <string.h>
// #include <stdlib.h>

// /* "infinity"... > maximum distance possible (for one knight) */
// #define MAXN 10400

// /* maximum number of rows */
// #define MAXR 40 

// /* maximum number of columns */
// #define MAXC 26 

// /* cost of collecting all knights here */
// int cost[MAXC][MAXR]; 

// /* cost of getting a knight to collect the king */
// int kingcost[MAXC][MAXR];

// /* distance the king must travel to get to this position */
// int kdist[MAXC][MAXR];

// /* distance to get for current knight to get to this square */
// /* third index: 0 => without king, 1 => with king */
// int dist[MAXC][MAXR][2]; 

// /* number of rows and columns */
// int nrow, ncol;

// int do_step(int x, int y, int kflag) {
//     int f = 0; /* maximum distance added */
//     int d = dist[x][y][kflag]; /* distance of current move */

//   /* go through all possible moves that a knight can make */
//     if (y > 0) {
//         if (x > 1)
//              if (dist[x-2][y-1][kflag] > d+1) {
//                  dist[x-2][y-1][kflag] = d+1;
//                  f = 1;
//              }
//             if (x < ncol-2) {
//                 if (dist[x+2][y-1][kflag] > d+1) {
// 	            dist[x+2][y-1][kflag] = d+1;
// 	            f = 1;
// 	        }
//             }
//             if (y > 1) {
//                 if (x > 0)
// 	            if (dist[x-1][y-2][kflag] > d+1) {
// 	                dist[x-1][y-2][kflag] = d+1;
// 	                f = 1;
// 	            }
// 	        if (x < ncol-1)
// 	            if (dist[x+1][y-2][kflag] > d+1) {
// 	                dist[x+1][y-2][kflag] = d+1;
// 	                f = 1;
// 	            }
//             }
//     }
//     if (y < nrow-1) {
//         if (x > 1)
//             if (dist[x-2][y+1][kflag] > d+1) {
//                 dist[x-2][y+1][kflag] = d+1;
//                 f = 1;
//             }
//             if (x < ncol-2) {
//                 if (dist[x+2][y+1][kflag] > d+1) {
//                     dist[x+2][y+1][kflag] = d+1;
//                     f = 1;
//                 }
//             }
//         if (y < nrow-2) {
//             if (x > 0)
//                 if (dist[x-1][y+2][kflag] > d+1) {
//                     dist[x-1][y+2][kflag] = d+1;
//                     f = 1;
//                 }
//             if (x < ncol-1)
//                 if (dist[x+1][y+2][kflag] > d+1) {
//                     dist[x+1][y+2][kflag] = d+1;
//                     f = 1;
//                 }
//         }
//     }

// /* also check the 'pick up king here' move */
//     if (kflag == 0 && dist[x][y][1] > d + kdist[x][y]) {
//         dist[x][y][1] = d + kdist[x][y];
//         if (kdist[x][y] > f) f = kdist[x][y];
//     }
//     return f; /* 1 if simple knight move made, 0 if no new move found */
// }

// void calc_dist(int col, int row) {
//     int lv, lv2;	/* loop variables */
//     int d;		/* current distance being checked */
//     int max; 		/* maximum finite distance found so far */
//     int f; 		/* temporary variable (returned value from do_step */

// /* initiate all positions to be infinite distance away */
//     for (lv = 0; lv < ncol; lv++)
//         for (lv2 = 0; lv2 < nrow; lv2++)
//             dist[lv][lv2][0] = dist[lv][lv2][1] = MAXN;

// /* starting location is zero w/o king, kdist[col][row] with king */
//     dist[col][row][0] = 0;
//     max = dist[col][row][1] = kdist[col][row];

//     for (d = 0; d <= max; d++) { /* for each distance away */
//         for (lv = 0; lv < ncol; lv++)
//             for (lv2 = 0; lv2 < nrow; lv2++) {
// 				/* for each position that distance away */
//                 if (dist[lv][lv2][0] == d) {
// 				 /* update with moves through this square */
//                     f = do_step(lv, lv2, 0);
//                     if (d + f > max)     /* update max if necessary */
// 			max = d + f;
//                  }

//                  if (dist[lv][lv2][1] == d) {
// 			/* same as above, except this time knight has king */
//                      f = do_step(lv, lv2, 1);
//                      if (d + f > max) max = d + f;
//                  }
//             }
//     }
// }

// int main(int argc, char **argv) {
//     FILE *fout, *fin;
//     char t[10];
//     int pr, pc;
//     int lv, lv2;
//     int i, j;

//     if ((fin = fopen("camelot.in", "r")) == NULL) {
//         perror ("fopen fin");
//         exit(1);
//     }
//     if ((fout = fopen("camelot.out", "w")) == NULL) {
//         perror ("fopen fout");
//         exit(1);
//     }

//     fscanf (fin, "%d %d", &nrow, &ncol);
//     fscanf (fin, "%s %d", t, &pr);
//     pc = t[0] - 'A';
//     pr--;

//   /* Calculate cost of moving king from starting position to
//    * each board position.  This is just the taxi-cab distance */
//    for (lv = 0; lv < ncol; lv++)
//        for (lv2 = 0; lv2 < nrow; lv2++) {
//            i = abs(pc-lv);
//            j = abs(pr-lv2);
//            if (i < j) i = j;
//            kingcost[lv][lv2] = kdist[lv][lv2] = i;
//        }

//     while (fscanf (fin, "%s %d", t, &pr) == 2) { /* for all knights */
//         pc = t[0] - 'A';
//         pr--;

//         /* calculate distances */
//         calc_dist(pc, pr);

//         for (lv = 0; lv < ncol; lv++)
//             for (lv2 = 0; lv2 < nrow; lv2++) {
//                 /* to collect here, we must also move knight here */
//                 cost[lv][lv2] += dist[lv][lv2][0];

// 	        /* check to see if it's cheaper for the new knight to
// 	           pick the king up instead of whoever is doing it now */
// 	        if (dist[lv][lv2][1] - dist[lv][lv2][0] < kingcost[lv][lv2]) {
// 	            kingcost[lv][lv2] = dist[lv][lv2][1] - dist[lv][lv2][0];
// 	        }
//             }
//     }
//     /* find best square to collect in */
//     pc = cost[0][0] + kingcost[0][0];

//     for (lv = 0; lv < ncol; lv++)
//         for (lv2 = 0; lv2 < nrow; lv2++)
//             if (cost[lv][lv2] + kingcost[lv][lv2] < pc) /* better square? */
//                 pc = cost[lv][lv2] + kingcost[lv][lv2]; 
//   fprintf (fout, "%i\n", pc);
//   return 0;
// }<file_sep>/section 1/ariprog.cpp
/*
ID: luglian1
PROG: ariprog
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

template <typename T>
void printVector(const vector<T>& order){
	for(int i=0; i!=order.size(); ++i)
		cout << order[i] << " ";
	cout << endl;
}

ostream& operator<<(ostream& out, const set<int>& s){
	out << "{";
	set<int>::const_iterator it;
	for(it = s.begin(); it!=s.end(); ++it)
		out << *it << ", ";
	out << "}";
	return out;
}

struct Progression{
	int start;
	int dict;
	Progression(): start(0), dict(0){}
	Progression(int s, int d): start(s), dict(d) {}
	Progression& operator=(const Progression& rhs){
		start = rhs.start;
		dict = rhs.dict;
		return *this;
	}
};

bool operator<(const Progression& s1, const Progression& s2){
	return s1.start == s2.start ? s1.dict < s2.dict : s1.start < s2.start;
}

class CompareProgression{
public:
	bool operator()(const Progression& lhs, const Progression& rhs) const{
		return lhs.start == rhs.start ? 
				lhs.dict < rhs.dict : 
				lhs.start < rhs.start;
	}
};

struct Sequence{
	int start;
	int dict;
	int length;
	// bool operator<(const Sequence& s2) const {
	// 	return start == s2.start ? dict < s2.dict : start < s2.start;
	// }
};

bool operator<(const Sequence& s1, const Sequence& s2){
	return s1.start == s2.start ? s1.dict < s2.dict : s1.start < s2.start;
}

bool compare(const Progression& lhs, const Progression& rhs){
	return lhs.dict == rhs.dict ? lhs.start < rhs.start : lhs.dict < rhs.dict;
}



ostream& operator<<(ostream& out, const Progression& pg){
	out << pg.start << " " << pg.dict;
}

int main(){
	ifstream file_in("ariprog.in");
	ofstream file_out("ariprog.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n, m;
	file_in >> n >> m;
	int exist[125000] = {0};
	set<int> bisquares;
	cout << "here"<< endl;
	for (int i = 0; i <= m; ++i)	{
		for(int j=i; j <= m; ++j ){
			bisquares.insert(i*i + j*j);
			exist[i*i + j*j-1] = 1;
		}
	}
	cout << "over" << endl;
	int max = 2*m*m;
	cout << bisquares.size() << endl;
	vector<int> vbisquare;
	vbisquare.insert(vbisquare.begin() ,bisquares.begin(), bisquares.end());
	cout << vbisquare.size() << endl;
	cout << "copy" << endl;
	// 3. optimize 1
	cout << "begin" << endl;
	vector<Progression> result;
	for(int i=0; i!=vbisquare.size(); ++i){
		Progression pg;
		for(int j=i+1; j<vbisquare.size(); ++j){
			pg.start = vbisquare[i];
			pg.dict = vbisquare[j] - vbisquare[i];
			int count = 2;
			int cur = vbisquare[j];
			while(count < n){
				cur += pg.dict;
				if(cur > max)
					break;
				if(exist[cur-1] == 0)
					break;
				++count;
			}
			if(count == n)
				result.push_back(pg);
		}
	}


	cout << result.size() << endl;
	sort(result.begin(), result.end(), compare);
	//printVector(result);

	if(result.size() == 0) file_out << "NONE" << endl;
	for(int i=0; i!=result.size(); ++i){
		file_out << result[i].start << " "<< result[i].dict << endl;
	}
	file_in.close();
	file_out.close();
	return 0;

	// 1. try the foolish method, over time!
	// 	int n, m;
	// file_in >> n >> m;
	// set<int> bisquares;
	// for (int i = 0; i <= m; ++i)	{
	// 	for(int j=i; j <= m; ++j ){
	// 		bisquares.insert(i*i + j*j);
	// 	}
	// }
	// cout << bisquares << endl;
	// cout << bisquares.size() << endl;

	// vector<int> vbisquare(bisquares.begin(), bisquares.end());
	// vector<Progression> result;
	// for(int i=0; i!=vbisquare.size(); ++i){
	// 	Progression pg;
	// 	for(int j=i+1; j<vbisquare.size(); ++j){
	// 		pg.start = vbisquare[i];
	// 		pg.dict = vbisquare[j] - vbisquare[i];
	// 		int count = 2;
	// 		int cur = vbisquare[j];
	// 		while(count < n){
	// 			cur += pg.dict;
	// 			if(bisquares.count(cur) == 0)
	// 				break;
	// 			++count;
	// 		}
	// 		if(count == n)
	// 			result.push_back(pg);
	// 	}
	// }

	// // 2. another method, over memory
	// map<Progression, int> seqmap;
	// for(int i=vbisquare.size()-2; i>=0; --i){
	// 	for(int j=i+1; j<vbisquare.size(); ++j){
	// 		Progression pg(vbisquare[j], vbisquare[j] - vbisquare[i]);
	// 		map<Progression, int>::iterator it = seqmap.find(pg);
	// 		if( it == seqmap.end()){
	// 			pg.start = vbisquare[i];
	// 			seqmap.insert(make_pair(pg, 2));
	// 		}
	// 		else{
	// 			cout << "find" << endl;
	// 			pg = it->first;
	// 			pg.start = vbisquare[i];
	// 			int length = it->second+1;
	// 			seqmap.erase(it);
	// 			seqmap.insert(make_pair(pg, length));
	// 		}
	// 	}
	// }
	// for(map<Progression, int>::iterator it = seqmap.begin(); it!=seqmap.end(); ++it){
	// 	cout << it->first << " " << it->second << endl;
	// }

}
<file_sep>/section3/contact.cpp
/*
ID: luglian1
PROG: contact
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <set>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "contact"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

struct scmp
{
	bool operator()(const string& lhs, const string& rhs) const
	{
		if(lhs.length() != rhs.length())
			return lhs.length() < rhs.length();
		return lhs<rhs;
	};

};

class node
{
public:
	int count;
	node* ch[2];
	node(): count(0)
	{
		ch[0] = NULL;
		ch[1] = NULL;
	};

	void addStr(const char* s, int len)
	{
		if(len <= 0)
		{
			count++;

			return;
		}

		int cid = s[0] - '0';

		if(!ch[cid])
			ch[cid] = new node;
		if(len > 1)
			ch[cid]->addStr(s+1, len-1);
		else
			ch[cid]->addStr(s, len-1);
	}

	void dfsCount(map<int, set<string, scmp> >& count_map, const string& s)
	{
		if(count > 0)
		{
			if(!count_map.count(count))
				count_map.insert(pair<int, set<string, scmp> >(count, set<string, scmp>()));
			count_map[count].insert(s);
		}
		for(int i=0; i<2; ++i)
		{
			if(ch[i])
				ch[i]->dfsCount(count_map, s+char('0'+i));
		}
	}

	~node()
	{
		for(int i=0; i<2; ++i)
			if(ch[i])
				delete ch[i];
	}
};

int a, b, n;
string s;
map<int, set<string, scmp> > count_map;

ostream& operator<<(ostream& out, const set<string, scmp>& s)
{
	for(set<string, scmp>::const_iterator it=s.begin(); it!=s.end(); ++it)
		out << *it << ", ";
	return out;
}

ostream& operator<<(ostream& out, const map<int, set<string, scmp> >& m)
{
	for(map<int, set<string, scmp> >::const_iterator it=m.begin(); it!=m.end(); ++it)
		out << (*it).first << ": " << (*it).second << endl;
	return out;
}

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> a >> b >> n;
	string line;
	getline(file_in, line);
	while(getline(file_in, line))
	{
		s += line;
	}

	PV(s)

	return true;
}

void save(ostream& out)
{
	map<int, set<string, scmp> >::reverse_iterator it=count_map.rbegin();
	for(int i=0; i<n && it!=count_map.rend(); ++i, ++it)
	{
		out << (*it).first << endl;

		set<string, scmp>::iterator it2 = (*it).second.begin();
		int c=0;
		out << *it2;
		for(it2++;it2 != (*it).second.end(); ++it2)
		{
			c++;
			if(c % 6 == 0)
				out << endl;
			else
				out << " ";
			out << *it2;
		}
		out << endl;
	}
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	const char* cs = s.c_str();
	node root;
	for(int i=0; i<s.size(); ++i)
	{
		for(int j=a; j<=b; ++j)
		{
			if(i + 1 >= j)
			{
				root.addStr(cs+i+1-j, j);
			}
		}
	}

	root.dfsCount(count_map, "");

	PV(count_map)
}

// For this problem, we keep track of every bit sequence we see. We could use the bit sequence itself as an index into a table of frequencies, but that would not distinguish between the 2-bit sequence "10" and the 4-bit sequence "0010". To solve this, we always add a 1 to the beginning of the number, so "10" becomes "110" and "0010" becomes "10010".

// After reading the entire bit string, we sort the frequency table and walk through it to print out the top sequences.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXBITS 12
// #define MAXSEQ (1<<(MAXBITS+1))

// typedef struct Seq Seq;
// struct Seq {
//     unsigned bits;
//     int count;
// };

// Seq seq[MAXSEQ];

// /* increment the count for the n-bit sequence "bits" */
// void
// addseq(unsigned bits, int n)
// {
//     bits &= (1<<n)-1;
//     bits |= 1<<n;
//     assert(seq[bits].bits == bits);
//     seq[bits].count++;
// }

// /* print the bit sequence, decoding the 1<<n stuff */
// /* recurse to print the bits most significant bit first */
// void
// printbits(FILE *fout, unsigned bits)
// {
//     assert(bits >= 1);
//     if(bits == 1)	/* zero-bit sequence */
// 	return;

//     printbits(fout, bits>>1);
//     fprintf(fout, "%d", bits&1);
// }

// int
// seqcmp(const void *va, const void *vb)
// {
//     Seq *a, *b;

//     a = (Seq*)va;
//     b = (Seq*)vb;

//     /* big counts first */
//     if(a->count < b->count)
// 	return 1;
//     if(a->count > b->count)
// 	return -1;

//     /* same count: small numbers first */
//     if(a->bits < b->bits)
// 	return -1;
//     if(a->bits > b->bits)
// 	return 1;

//     return 0;
// }

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, a, b, n, nbit, c, j, k;
//     unsigned bit;
//     char *sep;

//     fin = fopen("contact.in", "r");
//     fout = fopen("contact.out", "w");
//     assert(fin != NULL && fout != NULL);

//     nbit = 0;
//     bit = 0;

//     for(i=0; i<=MAXBITS; i++)
// 	for(j=0; j<(1<<i); j++)
// 	    seq[(1<<i) | j].bits = (1<<i) | j;

//     fscanf(fin, "%d %d %d", &a, &b, &n);

//     while((c = getc(fin)) != EOF) {
// 	if(c != '0' && c != '1')
// 	    continue;

// 	bit <<= 1;
// 	if(c == '1')
// 	    bit |= 1;

// 	if(nbit < b)
// 	    nbit++;

// 	for(i=a; i<=nbit; i++)
// 	    addseq(bit, i);
//     }

//     qsort(seq, MAXSEQ, sizeof(Seq), seqcmp);

//     /* print top n frequencies for number of bits between a and b */
//     j = 0;
//     for(i=0; i<n && j < MAXSEQ; i++) {
// 	if(seq[j].count == 0)
// 	    break;

// 	c = seq[j].count;
// 	fprintf(fout, "%d\n", c);

// 	/* print all entries with frequency c */
// 	sep = "";
// 	for(k=0; seq[j].count == c; j++, k++) {
// 	    fprintf(fout, sep);
// 	    printbits(fout, seq[j].bits);
// 	    if(k%6 == 5)
// 		sep = "\n";
// 	    else
// 		sep = " ";
// 	}
// 	fprintf(fout, "\n");
//     }

//     exit(0);
// }

<file_sep>/mytest/test_swap.cpp
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;

#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;

int main()
{
	vector<int> a{1,2,3,4,5,6,7,8};
	a.push_back(9);
	vector<int>::iterator ait = a.begin();
	for(int i=0; i<7; ++i)
		a.pop_back();

	PV(a.size())
	PV(a.capacity())

	vector<int> b{10};
	vector<int>::iterator bit = b.begin();
	b.swap(a);
	PV(b.size())
	PV(b.capacity())

	PV(*(++ait))
	PV(*(++bit))
}
<file_sep>/section2/fracdec.cpp
/*
ID: luglian1
PROG: fracdec
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstring>
#include <map>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "fracdec"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

int a, b;
int integer = 0;
vector<int> decimal;
int remainder = 0;
map<int, int> remmap;
int resi = 0;
int resl = 0;
int divisible = 0;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> a >> b;

	return true;
}

void save(ostream& out)
{
	if(divisible)
	{
		out << integer << ".";
		for(int i=0; i<decimal.size(); ++i)
			out << decimal[i];
		out << endl;
	}
	else
	{
		int line=0;
		vector<int> outin;
		do
		{
			outin.push_back(integer % 10);
			integer = integer / 10;
		}while(integer > 0);

		for(int i=outin.size()-1; i>=0; --i)
			out << outin[i];

		out << ".";
		line = outin.size() + 1;

		for(int i=0; i<resi; ++i)
		{
			out << decimal[i];
			line++;
			if(line == 76)
			{
				line = 0;
				out << endl;
			}
		}
		out << "(";
		line++;
		if(line == 76)
		{
			line = 0;
			out << endl;
		}
		for(int i=0; i<resl; ++i)
		{
			out << decimal[resi+i];
			line++;
			if(line == 76)
			{
				line = 0;
				out << endl;
			}
		}
		out << ")" << endl;
	}

}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


int check_loop(const vector<int>& num)
{
	for(int i=0; i<num.size(); ++i)
	{
		for(int j=i+1; j<(num.size()-i)/3; ++j)
		{
			if(num[i] != num[j])
				continue;

			if(memcmp(num.data()+i, num.data()+j, (j-i)*sizeof(int)) == 0 &&
				memcmp(num.data()+j, num.data()+j+j-i, (j-i)*sizeof(int)) == 0)
			{
				if (j-i == 1)
				{
					if(num.size()-j < 10)
						return 0;
					for(int k=j; k<num.size(); ++k)
						if(num[k] != num[j])
							return 0;
					resi = i;
					resl = j - i;
					return 1;
				}
				else
				{
					resi = i;
					resl = j - i;
					return 1;
				}
				
			}
		}
	}
	return 0;
}

void solve()
{
	integer = a / b;
	remainder = a % b;

	for(int i=0; i<100000; ++i)
	{
		if(remmap.count (remainder))
		{
			resi = remmap[remainder];
			resl = i - resi;
			break;
		}

		if(remainder == 0)
		{
			divisible = 1;
			break;
		}
		remmap.insert(pair<int,int>(remainder, i));

		remainder *= 10;
		decimal.push_back(remainder / b);
		remainder = remainder % b;
		// if(check_loop(decimal))
		// 	break;
	}

	if(decimal.empty())
		decimal.push_back(0);

	// PV(remmap.size())

	// PVL(decimal, decimal.size())
}

// Remember long division? We know that the decimal expansion is repeating when, after the decimal point, we see a remainder we've seen before. The repeating part will be all the digits we've calculated since the last time we saw that remainder.

// We read in the input and print the integer part. Then we do long division on the fractional part until we see a remainder more than once or the remainder becomes zero. If we see a remainder more than once, we're repeating, in which case we print the non-repeated and repeated part appropriately. If the remainder becomes zero, we finished, in which case we print the decimal expansion. When no digits of the decimal expansion have been generated, the correct answer seems to be to print a zero.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXDIGIT 100100

// char dec[MAXDIGIT];
// int lastrem[MAXDIGIT];
// char buf[MAXDIGIT];

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int n, d, k, i, rem, len;

//     fin = fopen("fracdec.in", "r");
//     fout = fopen("fracdec.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d %d", &n, &d);
//     sprintf(buf, "%d.", n/d);

// 	/* long division keeping track of if we've seem a remainder before */
//     for(i=0; i<MAXDIGIT; i++)
// 	lastrem[i] = -1;

//     rem = n % d;
//     for(i=0;; i++) {
// 	if(rem == 0) {
// 	    if(i == 0)
// 		sprintf(buf+strlen(buf), "0");
// 	    else
// 		sprintf(buf+strlen(buf), "%s", dec);
// 	    break;
// 	}
// 	if(lastrem[rem] != -1) {
// 	    k = lastrem[rem];
// 	    sprintf(buf+strlen(buf), "%.*s(%s)", k, dec, dec+k);
// 	    break;
// 	}

// 	lastrem[rem] = i;
// 	n = rem * 10;
// 	dec[i] = n/d + '0';
// 	rem = n%d;
//     }

//     /* print buf 76 chars per line */
//     len = strlen(buf);
//     for(i=0; i<len; i+=76) {
//     	fprintf(fout, "%.76s\n", buf+i);
//     }
//     exit(0);
// }
// Here's a another, more elegant solution from <NAME>.

// Compute the number of digits before the repeat starts, and then you don't even have to store the digits or remainders, making the program use much less memory and go faster. We know that powers of 2 and 5 are the only numbers which do not result in a repeat, so to find the number of digits before the repeat, we just find the maximum of the differences between the powers of 2 and 5 in the denominator and numerator (see code snippet). Then we just use the first remainder, and output each digit as we calculate it:

// #include <iostream.h>
// #include <fstream.h>
// #include <math.h>
// ofstream out("fracdec.out");

// int colcount=0;

// int numBeforeRepeat(int n, int d) {
//     int c2=0, c5=0;
//     if (n == 0) return 1;
//     while (d%2==0) { d/=2; c2++; }
//     while (d%5==0) { d/=5; c5++; }
//     while (n%2==0) { n/=2; c2--; } /* can go negative */
//     while (n%5==0) { n/=5; c5--; } /* can go negative */
//     if (c2>c5)
//         if (c2>0) return c2;
//         else return 0;
//     else
//         if (c5>0) return c5;
//         else return 0;
// }

// void print (char c) {
//     if (colcount==76) {
//         out<<endl;
//         colcount=0;
//     }
//     out<<c;
//     colcount++;
// }

// void print (int n) {
//     if (n>=10) print (n/10);
//     print ((char)('0'+(n%10)));
// }

// int main() {
//     int n, d;
//     ifstream in("fracdec.in");
//     in>>n>>d;
//     in.close();

//     print (n/d);
//     print ('.');
//     n=n%d;
//     int m=numBeforeRepeat(n,d);
//     for(int i=0;i<m;i++) {
//         n*=10;
// 	print (n/d);
//         n%=d;
//     }
//     int r=n;
//     if(r!=0) {
// 	print ('(');
//         do {
//             n*=10;
// 	    print (n/d);
//             n%=d;
//         } while (n!=r);
// 	print (')');
//     }
//     out<<endl;
//     out.close();
//     exit (0);
// }
<file_sep>/section 1/packrec.cpp
/*
ID: luglian1
PROG: packrec
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

vector<vector<int> > orderset;

template <typename T>
void printVector(const vector<T>& order){
	for(int i=0; i!=order.size(); ++i)
		cout << order[i] << " ";
	cout << endl;
}

void buildOrder(int n, vector<int>& earlyorder, vector<bool>& mark){
	if(earlyorder.size() == n){
		orderset.push_back(earlyorder);
		return;
	}

	for(int i=0; i!=n; ++i){
		if(!mark[i]){
			// printVector(earlyorder);
			// printVector(mark);
			earlyorder.push_back(i);
			mark[i] = true;
			buildOrder(n, earlyorder, mark);
			earlyorder.pop_back();
			mark[i] = false;
		}
	}
}

vector<vector<bool> > rotateset;

void buildRotate(int n, vector<bool>& earlyrotate){
	if(earlyrotate.size() == 4){
		rotateset.push_back(earlyrotate);
		return;
	}

	earlyrotate.push_back(false);
	buildRotate(n, earlyrotate);
	earlyrotate.pop_back();
	earlyrotate.push_back(true);
	buildRotate(n, earlyrotate);
	earlyrotate.pop_back();
}

class Rectangle{
public:
	int width;
	int height;
	int area;

	Rectangle(int w, int h): width(w), height(h), area(w*h) {}
	Rectangle rotate(bool r=true){
		if(r)
			return Rectangle(height, width);
		else
			return Rectangle(width, height);
	}
};

bool operator<(const Rectangle& lhs, const Rectangle& rhs){
	return lhs.width < rhs.width;
}

ostream& operator<<(ostream& out, const Rectangle& r){
	out << r.width << " " << r.height << " " << r.area;
}

void calMinRect(const Rectangle& r1, vector<Rectangle>& minrect){
	if(minrect.size() == 0){
		minrect.push_back(r1);
	}
	else if(r1.area < minrect[0].area){
		minrect.clear();
		minrect.push_back(r1);
	}
	else if(r1.area == minrect[0].area){
		minrect.push_back(r1);
	}
}

void calLayoutArea(const vector<Rectangle>& in, vector<Rectangle>& minrect){
	if(in.size() != 4){
		cerr << "Error: size of in is not equal 4" << endl;
		return;
	}

	int h=0,w=0;
	// first layout
	h = max(max(max(in[0].height, in[1].height), in[2].height), in[3].height);
	for(int i=0; i!=4; ++i)
		w += in[i].width;
	calMinRect(Rectangle(w, h), minrect);

	// second
	h = max(max(in[0].height, in[1].height), in[2].height) + in[3].height;
	for(int i=0, w=0; i!=3; ++i)
		w += in[i].width;
	w = max(w, in[3].width);
	calMinRect(Rectangle(w, h), minrect);

	// third
	h = max(in[3].height, max(in[0].height, in[1].height) + in[2].height);
	w = max(in[0].width + in[1].width, in[2].width) + in[3].width;
	calMinRect(Rectangle(w, h), minrect);

	// fourth
	h = max(in[0].height, max(in[1].height + in[2].height, in[3].height));
	w = in[0].width + max(in[1].width, in[2].width) + in[3].width;
	calMinRect(Rectangle(w, h), minrect);

	// fifth
	h = max(max(in[0].height+in[1].height, in[2].height), in[3].height);
	w = max(in[0].width, in[1].width) + in[2].width + in[3].width;
	calMinRect(Rectangle(w, h), minrect);

	// sixth
	h = max(in[0].height + in[1].height, in[2].height+in[3].height);
	w = max(in[0].width, in[1].width) + max(in[2].width, in[3].width);
	calMinRect(Rectangle(w, h), minrect);

	// seventh
	h = max(in[0].height, in[1].height + in[2].height + in[3].height);
	w = in[0].width + max(in[1].width, max(in[2].width, in[3].width));
	calMinRect(Rectangle(w, h), minrect);

	// eighth
	if(in[1].height >= in[3].height && in[2].width <= in[3].width){
		h = max(in[0].height + in[1].height,  in[2].height+in[3].height);		
		w = max(in[0].width + in[2].width, in[1].width + in[3].width);
	}
	// else{
	// 	h = max(in[0].height + in[1].height, max(in[0].height+in[3].height, 
	// 		max(in[1].height+in[2].height, in[2].height+in[3].height)));
	// 	w = max(in[0].width + in[2].width, 
	// 		max(in[0].width+in[3].width, in[1].width+in[3].width));
	// }

	// if(h*w==80){
	// 	for(int i=0; i!=in.size(); ++i){
	// 		cout << in[i].width << " " << in[i].height << endl;
	// 	}
	// 	cout << endl;
	// }

	calMinRect(Rectangle(w, h), minrect);
}

void cutResult(vector<Rectangle>& minrect){
	set<Rectangle> minset;
	vector<Rectangle> tmprect(minrect);
	for(int i=0; i!=tmprect.size(); ++i){
		if(tmprect[i].height < tmprect[i].width){
			swap(tmprect[i].width, tmprect[i].height);
		}
	}
	minset.insert(tmprect.begin(), tmprect.end());
	minrect.clear();
	minrect.insert(minrect.begin(), minset.begin(), minset.end());
}

int main(){
	ifstream file_in("packrec.in");
	ofstream file_out("packrec.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file." << endl;
		return 0;
	}

	vector<Rectangle> rectset;
	int w, h;
	for(int i=0; i!=4; ++i){
		file_in >> w >> h;
		rectset.push_back(Rectangle(w, h));
		//cout << rectset[i].width << " " << rectset[i].height << endl;
	}
	cout << rectset.size() << endl;
	//printVector(rectset);
	// build order set
	vector<int> tmporder;
	vector<bool> mark(4, false);
	buildOrder(4, tmporder, mark);
	// for(int i=0; i!=orderset.size(); ++i)
	// 	printVector(orderset[i]);

	// build rotate set
	vector<bool> tmprotate;
	buildRotate(4, tmprotate);
	cout << rotateset.size() << endl;
	// for(int i=0; i!=rotateset.size(); ++i)
	// 	printVector(rotateset[i]);

	// find all the min rect
	vector<Rectangle> minrect;
	for(int i=0; i!=orderset.size(); ++i){
		for(int j=0; j!=rotateset.size(); ++j){
			vector<Rectangle> testset;
			for(int k=0; k!=4; ++k)
				testset.push_back(rectset[orderset[i][k]].rotate(rotateset[j][k]));
			calLayoutArea(testset, minrect);
		}
	}

	cout << minrect.size() << endl;
	cout << "before" << endl;
	for(int i=0; i!=minrect.size(); ++i){
		cout << minrect[i].width << " " << minrect[i].height << endl;
	}
	cout << "here" << endl;
	cutResult(minrect);
	cout << minrect.size() << endl;
	// for(int i=0; i!=minrect.size(); ++i){
	// 	cout << minrect[i] << endl;
	// }

	file_out << minrect[0].area << endl;
	for (int i = 0; i < minrect.size(); ++i)
	{
		file_out << minrect[i].width << " " << minrect[i].height << endl;
	}

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section 1/namenum.cpp
/*
ID: luglian1
PROG: namenum
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <queue>

using namespace std;


class TrieNode{
public:
	TrieNode* children[26];
	bool isLeaf;
	TrieNode():isLeaf(false){	
		for(int i=0; i!=26; ++i)
			children[i] = NULL;
	}
};



int main(){
	ifstream file_in("namenum.in");
	ofstream file_out("namenum.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	string s;
	file_in >> s;
	char code[8][3] = {{'A','B','C'}, {'D','E','F'},{'G','H','I'},{'J','K','L'}, {'M','N','O'},
						{'P','R','S'},{'T','U','V'},{'W','X','Y'}};

	vector<int> num;
	for(int i=0; i!=s.size(); ++i)
		num.push_back(s.at(i)-'2');

	// load name and build trie tree
	ifstream dict_in("dict.txt");
	if(!dict_in){
		cerr << "Error: no file dict.txt" << endl;
		return 0;
	}
	TrieNode root;
	vector<TrieNode*> alloctn;
	while(!dict_in.eof()){
		dict_in >> s;
		TrieNode* tp = &root;
		for(int i=0; i!=s.size(); ++i){
			if(tp->children[s.at(i)-'A'] == NULL){
				tp->children[s.at(i)-'A'] = new TrieNode();
				alloctn.push_back(tp->children[s.at(i)-'A']);
			}
			tp = tp->children[s.at(i)-'A'];
		}
		tp->isLeaf = true;
	}

	cout << alloctn.size() << endl;
	for(int i=0; i!=num.size(); ++i){
		cout << num[i] << endl;
	}
	// search it
	queue<TrieNode*> tnq;	// queue to be search 
	queue<string> tns;		// word to match
	tns.push("");
	tnq.push(&root);
	for(int pos=0; pos!=num.size(); ++pos){
		int size = tnq.size();
		if(size == 0)
			break;
		for(int i=0; i!=size; ++i){
			TrieNode* tp = tnq.front();
			tnq.pop();
			string neww = tns.front();
			tns.pop();
			cout << neww << " ";
			for(int j=0; j!=3; ++j){
				if(tp->children[code[num[pos]][j]-'A'] != NULL){
					cout << "find " << pos << endl;
					tnq.push(tp->children[code[num[pos]][j]-'A']);
					tns.push(neww + code[num[pos]][j]);
				}
			}
		}
	}

	if(tns.size() != 0){
		while(!tns.empty()){
			if(tnq.front()->isLeaf)
				file_out << tns.front() << endl;
			tnq.pop();
			tns.pop();
		}
	}
	else
		file_out << "NONE" << endl;

	for(int i=0; i!=alloctn.size(); ++i){
		delete alloctn[i];
	}

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/inflate.cpp
/*
ID: luglian1
PROG: inflate
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "inflate"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAX_LEN 10000

using namespace std;

int m;
int n;
int cp[MAX_LEN] = {0};
int cm[MAX_LEN] = {0};
int a[MAX_LEN+1] = {0};

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> m >> n;
	for(int i=0; i<n; ++i)
	{
		file_in >> cp[i] >> cm[i];
	}

	return true;
}

void save(ostream& out)
{
	out << a[m] << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void solve()
{
	for(int i=1; i<=m; ++i)
	{
		int maxa = 0;
		for(int j=0; j<n; ++j)
		{
			if(i >= cm[j])
				maxa = max(a[i - cm[j]] + cp[j], maxa);
		}

		a[i] = max(a[i-1], maxa);
	}

	PVL(a, m);

}


// We use dynamic programming to calculate the best way to use t minutes for all t from 0 to tmax.

// When we find out about a new category of problem with points p and length t, we update the best for j minutes by taking the better of what was there already and what we can do by using a p point problem with the best for time j - t.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXCAT 10000
// #define MAXTIME 10000

// int best[MAXTIME+1];

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int tmax, ncat;
//     int i, j, m, p, t;

//     fin = fopen("inflate.in", "r");
//     fout = fopen("inflate.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d %d", &tmax, &ncat);

//     for(i=0; i<ncat; i++) {
// 	fscanf(fin, "%d %d", &p, &t);
// 	for(j=0; j+t <= tmax; j++)
// 	    if(best[j]+p > best[j+t])
// 	    	best[j+t] = best[j]+p;
//     }

// 	m = 0;
//     for(i=0; i<=tmax; i++)
// 	if(m < best[i])
// 	    m = best[i];

//     fprintf(fout, "%d\n", m);
//     exit(0);
// }
// <NAME> writes: After the main `for' loop that does the actual DP work, we don't need to look at the entire array of best point totals to find the highest one. The array is always nondecreasing, so we simply output the last element of the array.

// #include <fstream.h>

// ifstream fin("inflate.in");
// ofstream fout("inflate.out");

// const short maxm = 10010;
// long best[maxm], m, n;

// void
// main()
// {
//     short i, j, len, pts;

//     fin >> m >> n;

//     for (j = 0; j <= m; j++)
//         best[j] = 0;

//     for (i = 0; i < n; i++) {
//         fin >> pts >> len;
//         for (j = len; j <= m; j++)
//             if (best[j-len] + pts > best[j])
//                 best[j] = best[j-len] + pts;
//     }
//     fout << best[m] << endl; // This is always the highest total.
// }<file_sep>/section2/hamming.cpp
/*
ID: luglian1
PROG: hamming
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#include <set>
#include <vector>
#include <cassert>

using namespace std;
bool load();
void save(ostream& out);
bool save();

#define MAX_B 256

int N, B, D;

int hamming_distance[MAX_B][MAX_B];

int search_path[MAX_B+1];

int depth[MAX_B];

int max_value;
bool isFound;
set<int> result;


void calculateDistance()
{
	max_value = 1 << B;
	// calculcate hammming distance
	for (int i = 0; i < max_value; ++i)
	{
		for (int j = i; j < max_value; ++j)
		{
			int xorvalue = i ^ j;
			hamming_distance[i][j] = 0;
			while(xorvalue)
			{
				xorvalue = xorvalue & (xorvalue-1);
				++ hamming_distance[i][j];
			}
		}
	}
	for (int i = 0; i < max_value; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			hamming_distance[i][j] = hamming_distance[j][i];
		}
	}

	// cout
	// for (int i = 0; i < max_value; ++i)
	// {
	// 	for (int j = 0; j < max_value; ++j)
	// 	{
	// 		cout << hamming_distance[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
}

void dfs_solve(int cur_depth, int cur_id)	// 接着要处理的数字和该数字所在的深度
{
	// check
	cout << "cur depth: " << cur_depth << endl;
	search_path[cur_depth] = cur_id;
	depth[cur_id] = cur_depth;
	if(cur_depth > max_value)
		return;
	if(cur_depth == N)	// check finish
	{

		result.clear();
		for (int i = 1; i <= N; ++i)
		{
			result.insert(search_path[i]);
		}
		assert(result.size() == N);
		isFound = true;
		return;
	}
	else
	{
		for (int i = cur_id+1; i < max_value; ++i)
		{
			int j=1;
			for (; j <= cur_depth; ++j)
			{
				if(hamming_distance[search_path[j]][i] < D)
					break;
			}
			if(j> cur_depth)
				dfs_solve(cur_depth+1, i);
			if(isFound)
				return;
		}
		depth[cur_id] = 0;
	}
}

void solve()
{
	calculateDistance();
	memset(depth, 0, MAX_B * sizeof(int));
	isFound = false;
	dfs_solve(1, 0);
	// for (int i = 0; i < max_value; ++i)
	// {
	// 	dfs_solve(1, i);
	// 	if(isFound)
	// 		return;
	// }
}

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in("hamming.in");
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N >> B >> D;
	cout << N << " " << B << " " << D << endl;
	return true;
}

void save(ostream& out)
{
	vector<int> resultv(result.begin(), result.end());
	for (int i = 0; i < N; ++i)
	{
		out << resultv[i];
		if(i % 10 == 9)
			out << endl;
		else if(i != N-1)
			out << " ";
		else
			out << endl;
	}
}

bool save()
{
	ofstream file_out("hamming.out");
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}
<file_sep>/section 1/palsquare.cpp
/*
ID: luglian1
PROG: palsquare
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

bool checkPalindromic(const string& s){
	for(int i=0; i!=s.size()/2; ++i){
		if(s.at(i) != s.at(s.size()-i-1) )
			return false;
	}
	return true;
}

string digits = "0123456789ABCDEFGHIJKLMN";
string buildString(int i, int base){
	string res;
	int quo = i;
	while(quo > 0){
		res = digits.at(quo % base)+res;
		quo = quo / base;
	}
	return res;
}

int main(){
	ifstream file_in("palsquare.in");
	ofstream file_out("palsquare.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n;
	file_in >> n;
	for(int i=1; i!=300; ++i){
		int square = i * i;
		string s = buildString(square, n);
		if(checkPalindromic(s))
			file_out << buildString(i, n) << " " << s << endl;
	}

	cout << buildString(300, 16) << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/humble.cpp
/*
ID: luglian1
PROG: humble
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "humble"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAXP 100
#define INF 0x7fffffff

using namespace std;

int n;
int m;
int p[MAXP]={0};
vector<int> num;
int next_num[MAXP];

int res;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> n >> m;

	for(int i=0; i<n; ++i)
		file_in >> p[i];

	return true;
}

void save(ostream& out)
{
	out << res << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	sort(p, p+n);

	// PVL(p, n)

	num.push_back(1);
	for(int i=0; i<m; ++i)
	{
		int min_next = INF;
		int min_p = 0;
		for(int j=0; j<n; ++j)
		{
			int next = p[j] * num[next_num[j]];
			while(next <= num[num.size()-1])
			{
				next_num[j]++;
				next = p[j] * num[next_num[j]];
			}
			if(next < min_next)
			{
				min_next = next;
				min_p = j;
			}
		}
		next_num[min_p]++;
		num.push_back(min_next);
	}

	res = num[num.size()-1];
	// PVL(num, num.size())
}


// We compute the first n humble numbers in the "hum" array. For simplicity of implementation, we treat 1 as a humble number, and adjust accordingly.

// Once we have the first k humble numbers and want to compute the k+1st, we do the following:

// 	for each prime p
// 		find the minimum humble number h
// 		  such that h * p is bigger than the last humble number.

// 	take the smallest h * p found: that's the next humble number.
// To speed up the search, we keep an index "pindex" of what h is for each prime, and start there rather than at the beginning of the list.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>
// #include <ctype.h>

// #define MAXPRIME 100
// #define MAXN 100000

// long hum[MAXN+1];
// int nhum;

// int prime[MAXPRIME];
// int pindex[MAXPRIME];
// int nprime;

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, minp;
//     long min;
//     int n;

//     fin = fopen("humble.in", "r");
//     fout = fopen("humble.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d %d", &nprime, &n);
//     for(i=0; i<nprime; i++)
// 	fscanf(fin, "%d", &prime[i]);

//     hum[nhum++] = 1;
//     for(i=0; i<nprime; i++)
// 	pindex[i] = 0;

//     while(nhum < n+1) {
// 	min = 0x7FFFFFFF;
// 	minp = -1;
// 	for(i=0; i<nprime; i++) {
// 	    while((double)prime[i] * hum[pindex[i]] <= hum[nhum-1]) 
// 		pindex[i]++;

// 	    /* double to avoid overflow problems */
// 	    if((double)prime[i] * hum[pindex[i]] < min) {
// 		min = prime[i] * hum[pindex[i]];
// 		minp = i;
// 	    }
// 	}

// 	hum[nhum++] = min;
// 	pindex[minp]++;
//     }

//     fprintf(fout, "%d\n", hum[n]);
//     exit(0);
// }
<file_sep>/section3/spin.cpp
/*
ID: luglian1
PROG: spin
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <set>
#include <cstring>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "spin"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

struct wedge
{
	int begin;
	int range;

	wedge(int b, int r): begin(b), range(r) {};
};

class wheel
{
public:
	vector<wedge> wedges;
	int speed;

	wheel(int s=0): speed(s) {};

	void add_wedge(int begin, int range)
	{
		wedges.push_back(wedge(begin, range));
	}

	set<int> get_minute(int m)
	{
		set<int> s;
		for(vector<wedge>::iterator w=wedges.begin(); w!=wedges.end(); w++)
		{
			int b = (*w).begin + m * speed;
			for(int i=0; i<=(*w).range; ++i)
			{
				s.insert((b+i) % 360);
			};
		}
		return s;
	}

	bool get_minute(int m, int n, int* count, bool& found)
	{
		bool match = false;
		for(vector<wedge>::iterator w=wedges.begin(); w!=wedges.end(); w++)
		{
			int b = (*w).begin + m * speed;
			for(int i=0; i<=(*w).range; ++i)
			{
				int id = (b+i) % 360;
				count[id]++;
				if(count[id] == 5)
				{
					found = true;
					return true;
				}
				if(count[id] == n+1)
				{
					match = true;
				}

			};
		}
		return match;
	}

};

ostream& operator<<(ostream& out, const set<int>& s)
{
	for(set<int>::const_iterator it=s.begin(); it!=s.end(); ++it)
		out << *it << ", ";
	return out;
}

vector<wheel> whs(5);
int count[360] = {0};
int resout = -1;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	for(int i=0; i<5; ++i)
	{
		int speed, n;
		file_in >> speed >> n;
		wheel& w = whs[i];
		w.speed = speed;

		for(int j=0; j<n; ++j)
		{
			int begin, range;
			file_in >> begin >> range;
			w.add_wedge(begin, range);
		}

		PV(whs[i].speed)
		PV(whs[i].wedges[0].begin)
		PV(whs[i].wedges[0].range)
	}

	return true;
}

void save(ostream& out)
{
	if(resout >= 0)
		out << resout << endl;
	else
		out << "none" << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	bool found = false;
	for(int i=0 ;i<=360; ++i)
	{
		memset(count, 0, 360 * sizeof(int));
		for(int j=0; j<5; ++j)
		{
			bool match = whs[j].get_minute(i, j, count, found);
			if(j==0)
				continue;
			if(!match)
				break;
			if(found)
			{
				resout = i;
				break;
			}
		}
		if(found)
			break;
	}
}


// The key observation for this problem is that after 360 seconds, the wheels have returned to their original locations, so if the wheels don't line up in 360 seconds, they will never line up.

// To determine if there is a location through which a light can be shine, mark, for each wheel, which angles between 0 and 359 a light can be shone through. If any location gets marked for all the wheels, then a light can be shone through the entire system. Otherwise, no light can be shone through all the wheels.

// #include <stdio.h>
// #include <assert.h>
// #include <string.h>

// int speed[5];      /* speed of each wheel */
// int wedgest[5][5]; /* start of each wedge (-1 == no wedge) */
// int wedglen[5][5]; /* length of each wedge */

// int pos[5];        /* angular position of each wheel */
// int t;             /* time (in seconds) since start */

// /* (light[deg] >> wid) & 0x1 is true if and only if there
//    is a wedge in wheel wid that a light can shine through at
//    angle deg */
// int light[360];    
 
// /* mark all the degrees we can see through wheel w */
// void mark_light(int w)
//  {
//   int lv, lv2; /* loop variables */
//   int wpos; /* wedge position */

//   for (lv = 0; lv < 5; lv++)
//    {
//     if (wedglen[w][lv] < 0) /* no more wedges for this wheel */
//       break;

//     /* start of wedge */
//     wpos = (pos[w] + wedgest[w][lv]) % 360;

//     for (lv2 = 0; lv2 <= wedglen[w][lv]; lv2++)
//      { /* throughout extent of wedge */
//       light[wpos] |= (1 << w); /* mark as hole in wheel */
//       wpos = (wpos + 1) % 360; /* go to the next degree */
//      }
//    }
//  }

// int main(int argc, char **argv)
//  {
//   FILE *fp;
//   FILE *fout;
//   int w, f;
//   int lv, lv2;

//   fp = fopen("spin.in", "r");
//   fout = fopen("spin.out", "w");
//   assert(fp);
//   assert(fout);
  
//   /* read in the data */
//   for (lv = 0; lv < 5; lv++)
//    {
//     fscanf (fp, "%d %d", &speed[lv], &w);
//     for (lv2 = 0; lv2 < w; lv2++)
//       fscanf (fp, "%d %d", &wedgest[lv][lv2], &wedglen[lv][lv2]);

//     /* mark the rest of the wedges as not existing for this wheel */
//     for (; lv2 < 5; lv2++)
//       wedglen[lv][lv2] = -1;
//    }

//   f = 0;
//   while (t < 360) /* for each time step */
//    {
//     memset(light, 0, sizeof(light));

//     /* mark the degrees we can see through each wheel */
//     for (lv = 0; lv < 5; lv++)
//       mark_light(lv);

//     for (lv = 0; lv < 360; lv++)
//       if (light[lv] == 31) /* we can shine a light through all five wheels */
//         f = 1;

//     if (f) break; /* we found a match! */

//     /* make a time step */
//     t++;
//     for (lv = 0; lv < 5; lv++)
//       pos[lv] = (pos[lv] + speed[lv]) % 360;
//    }

//   /* after 360 time steps, all the wheels have returned to their
//      original location */
//   if (t >= 360) fprintf (fout, "none\n");
//   else fprintf (fout, "%i\n", t);

//   return 0;
//  }

<file_sep>/mytest/test_time.cpp
#include <iostream>
#include <time.h>

using namespace std;
int main()
{
	time_t t;
	cout << time(&t) << endl;
	cout << daylight << endl;
	cout << timezone <<  endl;
}<file_sep>/section 1/combo.cpp
/*
ID: luglian1
PROG: combo
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "combo"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define abs(a) (a) >= 0 ? (a) : -(a)
using namespace std;
bool load();
void save(ostream& out);
bool save();
void solve();

int N;
int f[3];			// farmer
int m[3];			// master
int count = 0;

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;
	for(int i=0; i<3; i++)
		file_in >> f[i];

	for (int i=0; i<3; i++)
		file_in >> m[i];

	return true;
}

void save(ostream& out)
{
	out << count << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

int dis(int a, int b)
{
	int ab = abs(a-b);
	if(ab < 5)
		return 5-ab;
	else if(ab > N - 5)
		return 5-(N-ab);
	return 0;
}

void solve()
{
	if(N <= 5)
	{
		count = N*N*N;
		return;
	}

	int minus = 1;
	for(int i=0; i<3; i++)
	{
		int d = dis(f[i], m[i]);
		minus *= d;
	}

	PV(minus)

	count = 250 - minus;
}<file_sep>/section 1/wormhole.cpp
/*
ID: luglian1
PROG: wormhole
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	{std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;}
#define PROB_NAME "wormhole"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

bool load();
void save(ostream& out);
bool save();
void solve();

int N;
int pos[13][2];
int count=0;
int p[13] = {0};
int y[13][13] {};

int main(){
	load();
	solve();
	save();
	return 0;
}

int findy(int py)
{
	int i=0;
	for(; i<N; i++)
	{
		if(y[i][0] == py || y[i][0] == -1)
			break;
	}
	return i;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;
	for(int i=1; i<=N; i++)
	{
		file_in >> pos[i][0] >> pos[i][1];
		//PVL(pos[i], 2);
	}
	//PV(N)

	// 构造一个y相同，以x排序的数组，插入排序
	for(int i=0; i<13; i++)
		for(int j=0; j<13; j++)
			y[i][j]=-1;
	for(int i=1; i<=N; i++)
	{
		int posx = pos[i][0], posy = pos[i][1];
		int py = findy(posy);
		//PV(py)
		if(y[py][0] == -1)
		{
			y[py][0] = posy;
			y[py][1] = i;
			continue;
		}

		int j=12;
		for(; j>=1 && y[py][j]<=0; j--);
		for(; j>=1 && pos[y[py][j]][0] > posx; j--)
		{
			y[py][j+1] = y[py][j];
		}
		y[py][j+1] = i;
	}

	// for(int i=0; i<13; i++)
	// {
	// 	PVL(y[i], 13);
	// }

	return true;
}

void save(ostream& out)
{
	out << count << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void check()
{
	int pair[13][2] {0};
	for(int i=1; i<=N; i++)
	{
		if(pair[p[i]][0] == 0)
			pair[p[i]][0] = i;
		else
			pair[p[i]][1] = i;
	}


	// for(int i=0; i<13; i++)
	// {
	// 	PVL(pair[i], 2);
	// }

	int r[13] {};

	//暴力遍历来找回路
	for(int i=1; i<=N; i++)
	{
		for(int i=0; i<13; i++)
			r[i] = 0;
		int cur = i;		//进入i
		bool cir = false;
		for(int j=1; j<=N; j++)
		{
			r[cur] = 1;
			int next = 0;
			if(pair[p[cur]][0] == cur)
				next = pair[p[cur]][1];
			else
				next = pair[p[cur]][0];
			//r[next] = 1;
			//cout << cur << ", " << next << endl;
			int posx = pos[next][0], posy = pos[next][1];
			int py = findy(posy);
			int sp = 0;
			for(; y[py][sp] != next; sp++);
			if(y[py][sp+1] > 0)
				next = y[py][sp+1];
			else
				break;

			if(r[next] == 1)
			{
				cir = true;
				break;
			}

			cur = next;
		}
		if(cir)
		{
			count++;
			// PV(i)
			// PVL(p, 13)

			break;
		}
	}
	//PVL(r, 13)
}

// 选取第n对虫洞
void pick(int n)
{
	if(n > N / 2)
	{
		
		check();
		return;
	}

	int cur = 1;
	for(; p[cur] != 0; cur++);

	p[cur] = n;

	for(int i=cur+1; i<=N; i++)
	{
		if(p[i] != 0)
			continue;
		p[i] = n;
		pick(n+1);
		p[i] = 0;
	}
	p[cur] = 0;
}

void solve()
{
	pick(1);
}<file_sep>/section2/runround2.cpp
/*
ID: luglian1
PROG: runround
LANG: C++
*/

#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

#define INPUT_FILE "runround.in"
#define OUTPUT_FILE "runround.out"

using namespace std;

void NextNumber(std::vector<int>& number, int Digits) {
    number[Digits - 1]++;
    for (int i = Digits - 1; i >= 0; i--) {
        if (number[i] == 10) {
            number[i] = 1;
            if (i == 0) {
                number.insert (number.begin(),1);
                return;
            } else 
                number[i - 1]++;
        }
    }
    return;
}

bool CheckElement(std::vector<int>::iterator first,
    std::vector<int>::iterator last, int val) {
    while (first < last) {
        if (*first == val) 
            return true;
        ++first;
    }
    return false;
}

void NextUniqueNumber(std::vector<int>& number) {
    std::vector<int> old = number;
    for (int i = 1; i < number.size(); ++i) {
        if (number[i] == 0) number[i]++;
        while (CheckElement (number.begin(),number.begin() + i,number[i])) {
            number[i]++;
            if (number[i] == 10) {
                number[i] = 1;
                NextNumber (number,i);
                i = 1;
                continue;
            }
        }
    }
    return;
}

bool IsRoundNumber(std::vector<int>& number) {
    std::vector<bool> used(10,false);
    for (int i = 0, pos = 0, val = number[0]; i < number.size(); i++) {
        pos = (pos + val) % number.size();
        val = number[pos];
        if (used[pos] == true) return false;
        used[pos] = true;
    }
    return true;
}

unsigned int NextRoundNumber(unsigned int number) {
    std::vector<int> digits;
    for (int i = 0, tens = 1; i <= 10; ++i, tens *= 10) {
        int partial = number / tens;
        if (partial == 0) break;
        partial %= 10;
        digits.push_back(partial);
    }
    std::reverse (digits.begin(),digits.end());
    NextNumber (digits,digits.size());
    NextUniqueNumber (digits);
    while (!IsRoundNumber(digits)) {
        NextNumber (digits,digits.size());
        NextUniqueNumber (digits);
    }
    number = 0;
    for (int i = 0; i < digits.size(); i++) 
        number = 10 * number + digits[i];
    return number;
}

int main(int argc, char *argv[]) {
    ifstream FileInput (INPUT_FILE);
    ofstream FileOutput (OUTPUT_FILE);
    unsigned int Number;
    FileInput >> Number;
    FileOutput << NextRoundNumber(Number) << "\n";
    return 0;
}<file_sep>/section 1/friday.cpp
/*
ID: luglian1
PROG: friday
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

bool cheakLeap(int year){
	return ( (year % 4 == 0 && year % 100 != 0) || year % 400 == 0);
}

int main(){

	int noleap_days[] = {31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
	int leap_days[] = {31, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30};

	ifstream in("friday.in");
	ofstream out("friday.out");

	int n;
	in >> n;

	int count[7] = {0,0,0,0,0,0,0};

	int start = (0-31)%7+7;

	for(int i=1900; i < 1900 + n; ++i){
		int* pdays;
		if( cheakLeap(i) )
			pdays = leap_days;
		else
			pdays = noleap_days;
		for(int j=0; j != 12; ++j){
			start = (start + pdays[j]) % 7;
			++count[start];
		}
	}

	for(int i=0; i!=6; ++i){
		out << count[i] << " ";
	}
	out << count[6] << endl;

	in.close();
	out.close();
	return 0;
}
<file_sep>/section3/kimbits.cpp
/*
ID: luglian1
PROG: kimbits
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <bitset>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PVB(v, n) std::cout << #v << " = " << bitset<n>(v) << std::endl;
#define PROB_NAME "kimbits"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

unsigned int N, L, I;
unsigned int maxk[33] = {0};
unsigned int one[33] = {0};
unsigned int res;
bitset<32> resb;
unsigned int count[33][33] = {0};

bool load();
void save(ostream& out);
bool save();
void solve();
void solve2();

int main(){
	load();
	//solve();
	solve2();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N >> L >> I;

	return true;
}

void save(ostream& out)
{
	// bitset<32> b(res);
	// for(int i=N-1; i>=0; --i)
	// 	out << b[i];
	// out << endl;

	for(int i=N; i>=1; --i)
		out << resb[i];
	out << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

// n bits with most k 1s
unsigned int findnext(unsigned int cur, int n, int k)
{
	if(n == 0)
	{
		return cur | one[0];
	}

	int realk = min(k, n);
	int mini = max(0, n-k);
	int seqk = 0;
	int i=n-1;

	// find continuous 1s
	for(; i>=mini; --i)
	{
		if(!(cur & one[i]))
			break;

		seqk ++;
	}

	// find continuous 0s
	if(seqk < realk)
	{
		for(; i >= 0; --i)
		{
			if(cur & one[i])
				break;
		}
		return findnext(cur, i+1, k-seqk);
	}
	else
	{
		return cur & (~maxk[n-1]) | one[n];
	}

}

void solve()
{
	for(int i=0; i<32; ++i)
	{
		one[i] = 1 << i;
		if(i > 0)
			maxk[i] = maxk[i-1];
		maxk[i] |= one[i];
	}



	// PVL(maxk, 33)

	res = 0;
	for(int i=0; i<I-1; ++i)
	{
		res = findnext(res, N, L);
		// PVB(res, 32)
	}
	// PVB(res, 32)
}

void solve2()
{
	for(int i=0; i<33; ++i)
	{
		count[i][0] = 1;
		count[0][i] = 1;
	}

	for(int i=1; i<33; ++i)
	{
		for(int j=1; j<=i; ++j)
		{
			count[i][j] = count[i-1][j] + count[i-1][j-1];
		}
		for(int j=i+1; j<33; ++j)
			count[i][j] = count[i][i];
	}

	for(int i=0; i<33; ++i)
	{
		PVL(count[i], 33)
	}

	unsigned int curi = I;
	unsigned curl = L;
	for(int i=N; i>0; --i)
	{
		// PV(i)
		// PV(curi)
		// PV(curl)
		if(curi > count[i-1][curl])
		{
			resb[i] = true;
			curi -= count[i-1][curl];
			curl --;
			if(curl == 0)
				break;
		}

	}

	PV(resb)
}

// Suppose we knew how to calculate the size of the set of binary numbers for a given nbits and nones. That is, suppose we have a function sizeofset(n, m) that returns the number of n-bit binary numbers that have at most m ones in them.

// Then we can solve the problem as follows. We're looking for the ith element in the set of size n with m bits. This set has two parts: the numbers the start with zero, and the numbers that start with one. There are sizeofset(n-1, m) numbers that start with zero and have at most m one bits, and there are sizeofset(n-1, m-1) numbers that start with one and have at most m one bits.

// So if the index is less than sizeofset(n-1, m), the number in question occurs in the part of the set that is numbers that start with zero. Otherwise, it starts with a one.

// This lends itself to a nice recursive solution, implemented by "printbits".

// The only difficult part left is calculating "sizeofset". We can do this by dynamic programming using the property described above:

// 	sizeofset(n, m) = sizeofset(n-1, m) + sizeofset(n-1, m-1)
// and sizeofset(0, m) = 1 for all m. We use double's throughout for bits, but that's overkill given the rewritten problem that requires only 31 bits intead of 32.
// /*
// PROG: kimbits
// ID: rsc001
// */

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// FILE *fout;

// /* calculate binomial coefficient (n choose k) */
// double sizeofset[33][33];

// void
// initsizeofset(void)
// {
// 	int i, j;

// 	for(j=0; j<=32; j++)
// 		sizeofset[0][j] = 1;

// 	for(i=1; i<=32; i++)
// 	for(j=0; j<=32; j++)
// 		if(j == 0)
// 			sizeofset[i][j] = 1;
// 		else
// 			sizeofset[i][j] = sizeofset[i-1][j-1] + sizeofset[i-1][j];
// }

// void
// printbits(int nbits, int nones, double index)
// {
// 	double s;

// 	if(nbits == 0)
// 		return;

// 	s = sizeofset[nbits-1][nones];
// 	if(s <= index) {
// 		fprintf(fout, "1");
// 		printbits(nbits-1, nones-1, index-s);
// 	} else {
// 		fprintf(fout, "0");
// 		printbits(nbits-1, nones, index);
// 	}
// }

// void
// main(void)
// {
// 	FILE *fin;
// 	int nbits, nones;
// 	double index;

// 	fin = fopen("kimbits.in", "r");
// 	fout = fopen("kimbits.out", "w");
// 	assert(fin != NULL && fout != NULL);

// 	initsizeofset();
// 	fscanf(fin, "%d %d %lf", &nbits, &nones, &index);
// 	printbits(nbits, nones, index-1);
// 	fprintf(fout, "\n");

// 	exit(0);
// }
<file_sep>/section 1/numtri.cpp
/*
ID: luglian1
PROG: numtri
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int mat[1000][1000]={0};
int r=0;

void read(ifstream& file_in){
	file_in >> r;
	for(int i=0; i!=r; ++i){
		for(int j=0; j<=i; ++j){
			file_in >> mat[i][j];
		}
	}
}

void work(){
	r=r-2;
	while(r>=0){
		for(int i=0; i<=r; ++i){
			mat[r][i] += max(mat[r+1][i], mat[r+1][i+1]);
		}
		--r;
	}
}

int main(){
	ifstream file_in("numtri.in");
	ofstream file_out("numtri.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	read(file_in);
	//cout << r << endl;
	work();

	file_out << mat[0][0] << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section3/shopping.cpp
/*
ID: luglian1
PROG: shopping
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << (v)[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "shopping"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

struct coffer
{
	int code;
	int num;
	int price;
	coffer(int c=0, int n=0, int p=0): code(c), num(n), price(p){};
};

struct offer
{
	vector<coffer> cs;
	int reduce;
};

bool cmp_coffer(const coffer& c1, const coffer& c2)
{
	return c1.code < c2.code;
}

ostream& operator<<(ostream& out, const coffer& c)
{
	out << "(" << c.code << ", " << c.num << ", " << c.price <<")";
	return out;
}

int s;
int n;
vector<offer> offers;
vector<coffer> purchase;
int dp[6][6][6][6][6] = {0};
int res=0;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in  >> s;
	for(int i=0; i<s; ++i)
	{
		int n;
		file_in >> n;
		offer o;
		for(int j=0; j<n; ++j)
		{
			int code, num;
			file_in >> code >> num;
			o.cs.push_back(coffer(code, num));
		}
		file_in >> o.reduce;
		offers.push_back(o);
	}

	int p;
	file_in >> p;
	for(int i=0; i<p; ++i)
	{
		int code, num, price;
		file_in >> code >> num >> price;
		purchase.push_back(coffer(code, num, price));
	}

	PVL(purchase, purchase.size())
	sort(purchase.begin(), purchase.end(), cmp_coffer);

	map<int, int> code_map;
	map<int, int> price_map;
	for(int i=0; i<p; ++i)
	{
		code_map.insert(pair<int, int>(purchase[i].code, i));
		PV(purchase[i].code)
		PV(code_map[purchase[i].code])
		purchase[i].code = i;
	}
	PV(p)

	for(vector<offer>::iterator it=offers.begin(); it!=offers.end(); ++it)
	{
		int cost = 0;
		bool can_buy=true;
		for(vector<coffer>::iterator cit=it->cs.begin(); cit!=it->cs.end(); ++cit)
		{
			if(code_map.count(cit->code) == 0)
			{
				can_buy = false;
				break;
			}
			cit->code = code_map[cit->code];
			cost += purchase[cit->code].price * cit->num;
		}

		if(can_buy)
			it->reduce = cost - it->reduce;
		else
			it->reduce = 0;
	}

	for(vector<offer>::iterator it=offers.begin(); it!=offers.end(); ++it)
	{
		PVL(it->cs, it->cs.size())
		PV(it->reduce)
	}	

	PVL(purchase, purchase.size())


	return true;
}

void save(ostream& out)
{
	out << res << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	int p[5] = {0};

	for(int i=0; i<purchase.size(); ++i)
	{
		p[i] = 5;
	}

	PVL(p, 5)

	for(int i=0; i<=p[4]; ++i)
	{
		for(int j=0; j<=p[3]; ++j)
		{
			for(int k=0; k<=p[2]; ++k)
			{
				for(int m=0; m<=p[1]; ++m)
				{
					for(int n=0; n<=p[0]; ++n)
					{
						int ids[5] = {n, m, k, j, i};
						// PVL(ids, 5)
						int maxr = 0;
						for(vector<offer>::iterator it=offers.begin(); it!=offers.end(); ++it)
						{
							bool can_buy = true;
							for(vector<coffer>::iterator it2=it->cs.begin(); it2!=it->cs.end(); ++it2)
							{
								if(ids[it2->code] < it2->num)
								{
									can_buy = false;
									break;
								}
							}
							if(!can_buy)
								continue;

							int nids[5] = {n, m, k, j, i};
							for(vector<coffer>::iterator it2=it->cs.begin(); it2!=it->cs.end(); ++it2)
							{
								nids[it2->code] -= it2->num;
							}

							int r = it->reduce + dp[nids[0]][nids[1]][nids[2]][nids[3]][nids[4]];
							maxr = max(r, maxr);
						}
						dp[n][m][k][j][i] = maxr;
					}
				}
			}
		}
	}

	// PVL((int*)dp, 3125)

	int q[5] = {0};
	int cost=0;
	for(int i=0; i<purchase.size(); ++i)
	{
		q[purchase[i].code] = purchase[i].num;
		cost += (purchase[i].num * purchase[i].price);
	}

	PV(cost)
	PVL(q, 5)
	PV(dp[q[0]][q[1]][q[2]][q[3]][q[4]])

	res = cost - dp[q[0]][q[1]][q[2]][q[3]][q[4]];

}





// Shopping Offers
// <NAME>
// This is a shortest path problem. The goal is to find the shortest path from an empty basket to a basket containing the requested objects. Thus, Dijkstra's algorithm can be used.

// The nodes in the graph correspond to baskets and the edges correspond to offers (purchasing a single item can be considered a degenerate offer). The length of an edge is the cost of the offer. For each item type, there can be between 0 and 5 inclusive objects of that type in the basket, for a total of 65 = 7,776 possible baskets.

// #include <stdio.h>
// #include <string.h>

// /* maximum number of offers */
// /* 100 offers + 5 degenerate offers */
// #define MAXO 105

// typedef struct OFFER_T
//  {
//   int nitem; /* number of items in the offer */
//   int itemid[5]; /* item's id */
//   int itemamt[5]; /* item's amount */
//   int cost; /* the cost of this offer */
//  } offer_t;

// offer_t offers[MAXO];
// int noffer;

// /* the cost of each basket type */
// int cost[7776];

// /* the item statistics */
// int itemid[5]; /* the id */
// int itemcst[5]; /* the cost of buying just 1 */
// int nitem;

// /* heap used by Dijkstra's algorithm */
// int heap[7776];
// int hsize;
// int hloc[7776]; /* location of baskets within the heap */

// /* debugging routine */
// void check_heap(void)
//  { /* ensure heap order is maintained */
//   int lv;
//   return;

//   for (lv = 1; lv < hsize; lv++)
//    {
//     if (cost[heap[lv]] < cost[heap[(lv-1)/2]])
//      {
//       fprintf (stderr, "HEAP ERROR!\n");
//       return;
//      }
//    }
//  }

// /* delete the minimum element in the heap */
// void delete_min(void)
//  {
//   int loc, val;
//   int p, t;

//   /* take last item from the heap */
//   loc = heap[--hsize];
//   val = cost[loc];

//   /* p is the current position of item (loc,val) in the heap */
//   /* the item isn't actually there, but that's where we're
//      considering putting it */
//   p = 0; 

//   while (2*p+1 < hsize)
//    { /* while one child is less than the last item,
//         move the lesser child up */
//     t = 2*p+1;
//     /* pick lesser child */
//     if (t+1 < hsize && cost[heap[t+1]] < cost[heap[t]]) t++;

//     if (cost[heap[t]] < val)
//      { /* if child is less than last item, move it up */
//       heap[p] = heap[t];
//       hloc[heap[p]] = p;
//       p = t;
//      } else break;
//    }

//   /* put the last item back into the heap */
//   heap[p] = loc;
//   hloc[loc] = p;
//   check_heap();
//  }

// /* we decreased the value corresponding to basket loc */
// /* alter heap to maintain heap order */
// void update(int loc)
//  {
//   int val;
//   int p, t;

//   val = cost[loc];
//   p = hloc[loc];

//   while (p > 0) /* while it's not at the root */
//    {
//     t = (p-1)/2; /* t = parent of node */
//     if (cost[heap[t]] > val)
//      { /* parent is higher cost than us, swap */
//       heap[p] = heap[t];
//       hloc[heap[p]] = p;
//       p = t;
//      } else break;
//    }

//   /* put basket back into heap */
//   heap[p] = loc;
//   hloc[loc] = p;
//   check_heap();
//  }

// /* add this element into the heap */
// void add_heap(int loc)
//  {
//   if (hloc[loc] == -1)
//    { /* if it's not in the heap */

//     /* add it to the end (same as provisionally setting it's value
//        to infinity) */
//     heap[hsize++] = loc;
//     hloc[loc] = hsize-1;
//    }

//   /* set to correct value */
//   update(loc);
//  }

// /* given an id, calculate the index of it */
// int find_item(int id)
//  {
//   if (itemid[0] == id) return 0;
//   if (itemid[1] == id) return 1;
//   if (itemid[2] == id) return 2;
//   if (itemid[3] == id) return 3;
//   if (itemid[4] == id) return 4;
//   return -1;
//  }

// /* encoding constants 6^0, 6^1, 6^2, ..., 6^5 */
// const int mask[5] = {1, 6, 36, 216, 1296};

// void find_cost(void)
//  {
//   int p;
//   int cst;
//   int lv, lv2;
//   int amt;
//   offer_t *o;
//   int i;
//   int t;

//   /* initialize costs to be infinity */
//   for (lv = 0; lv < 7776; lv++) cost[lv] = 999*25+1;

//   /* offer not in heap yet */
//   for (lv = 0; lv < 7776; lv++) hloc[lv] = -1;
  
//   /* add empty baset */
//   cost[0] = 0;
//   add_heap(0);

//   while (hsize)
//    {
//     /* take minimum basket not checked yet */
//     p = heap[0];
//     cst = cost[p];

//     /* delete it from the heap */
//     delete_min();

//     /* try adding each offer to it */
//     for (lv = 0; lv < noffer; lv++)
//      {
//       o = &offers[lv];
//       t = p; /* the index of the new heap */
//       for (lv2 = 0; lv2 < o->nitem; lv2++)
//        {
//         i = o->itemid[lv2];
// 	/* amt = amt of item lv2 already in basket */
// 	amt = (t / mask[i]) % 6;

// 	if (amt + o->itemamt[lv2] <= 5)
// 	  t += mask[i] * o->itemamt[lv2];
// 	else
// 	 { /* if we get more than 5 items in the basket,
// 	      this is an illegal move */
// 	  t = 0; /* ensures we will ignore it, since cost[0] = 0 */
// 	  break;
// 	 }
//        }
//       if (cost[t] > cst + o->cost)
//        { /* we found a better way to get this basket */

//         /* update the cost */
//         cost[t] = cst + o->cost;
// 	add_heap(t); /* add, if necessary, and reheap */
//        }
//      }
//    }
//  }

// int main(int argc, char **argv)
//  {
//   FILE *fout, *fin;
//   int lv, lv2; /* loop variable */
//   int amt[5]; /* goal amounts of each type */
//   int a; /* temporary variable */

//   if ((fin = fopen("shopping.in", "r")) == NULL)
//    {
//     perror ("fopen fin");
//     exit(1);
//    }
//   if ((fout = fopen("shopping.out", "w")) == NULL)
//    {
//     perror ("fopen fout");
//     exit(1);
//    }

//   fscanf (fin, "%d", &noffer);

//   /* read offers */
//   for (lv = 0; lv < noffer; lv++)
//    {
//     fscanf (fin, "%d", &offers[lv].nitem);
//     for (lv2 = 0; lv2 < offers[lv].nitem; lv2++)
//       fscanf (fin, "%d %d", &offers[lv].itemid[lv2], &offers[lv].itemamt[lv2]);
//     fscanf (fin, "%d", &offers[lv].cost);
//    }

//   /* read item's information */
//   fscanf (fin, "%d", &nitem);
//   for (lv = 0; lv < nitem; lv++)
//     fscanf (fin, "%d %d %d", &itemid[lv], &amt[lv], &cost[lv]);

//   /* fill in rest of items will illegal data, if necessary */
//   for (lv = nitem; lv < 5; lv++) 
//    {
//     itemid[lv] = -1;
//     amt[lv] = 0;
//     cost[lv] = 0;
//    }

//   /* go through offers */
//   /* make sure itemid's are of item's in goal basket */
//   /* translate itemid's into indexes */
//   for (lv = 0; lv < noffer; lv++)
//    {
//     for (lv2 = 0; lv2 < offers[lv].nitem; lv2++)
//      {
//       a = find_item(offers[lv].itemid[lv2]);
//       if (a == -1)
//        { /* offer contains an item which isn't in goal basket */
        
// 	/* delete offer */

// 	/* copy last offer over this one */
//         memcpy (&offers[lv], &offers[noffer-1], sizeof(offer_t));
// 	noffer--;

// 	/* make sure we check this one again */
// 	lv--;
// 	break;
//        }
//       else
//         offers[lv].itemid[lv2] = a; /* translate id to index */
//      }
//    }

//   /* add in the degenerate offers of buying single items 8/
//   for (lv = 0; lv < nitem; lv++)
//    {
//     offers[noffer].nitem = 1;
//     offers[noffer].cost = cost[lv];
//     offers[noffer].itemamt[0] = 1;
//     offers[noffer].itemid[0] = lv;
//     noffer++;
//    }

//   /* find the cost for all baskets */
//   find_cost();

//   /* calculate index of goal basket */
//   a = 0;
//   for (lv = 0; lv < 5; lv++)
//     a += amt[lv] * mask[lv];

//   /* output answer */
//   fprintf (fout, "%i\n", cost[a]);
//   return 0;
//  }
// <NAME>'s Comments

// This problem can be solved using dynamic programming. This way is easier to code, and for the test cases it runs for much less than 0.1 seconds.

// We keep a five dimensional array sol (it's not that much, because its size is only 5*5*5*5*5*sizeof(special_offer).) Each configuration of the dimensions sol[a][b][c][d][e] corresponds to having a products from the first kind, b products from the second kind, c from the third, etc.

// Basically, the DP forumla is the following : sol[a][b][c][d][e]= min (a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5], so[k].price+ sol[a-so[k].prod[1].items] [b-so[k].prod[2].items] [c-so[k].prod[3].items] [d-so[k].prod[4].items] [e-so[k].prod[5].items] ) where k changes from 1 to the number of special offers. Or, in other words, for each field of the array we check which is better :

// Not to use any special offer
// To use some special offer
// It's very similliar to the knapsack problem. The complexity of this algorithm is O(5*5*5*5*5*100)=O(312,500), which is quite acceptable.
// #include <fstream>
// #include <cstring>
// using namespace std;

// ifstream fin ("shopping.in");
// ofstream fout("shopping.out");

// struct special_offer {
//     int n;
//     int price;              // the price of that special offer
//     struct product {        // for each product we have to keep :
//         int id;             // the id of the product
//         int items;          // how many items it includes
//     } prod[6];
// } so[100];                  // here the special offers are kept

// int code[1000],             /* Each code is 'hashed' from its real value
//                                to a smaller index.  Example :
// 			       If in the input we have code 111, 934, 55,
// 			       1, 66 we code them as 1,2,3,4,5. That is
// 			       kept in code[1000];
//                              */

// price[6],                   // the price of each product
// many[6];                    // how many of each product are to be bought

// int s,                      // the number of special offers
//     b;                      // the number of different kinds of products to be bought

// int sol[6][6][6][6][6];     // here we keep the price of each configuration

// void init() {               // reads the input
//     fin>>s;
//     for (int i=1;i<=s;i++) {
//         fin>>so[i].n;
//         for (int j=1;j<=so[i].n;j++)
//             fin>>so[i].prod[j].id>>so[i].prod[j].items;
//         fin>>so[i].price;
//     }
//     fin>>b;
//     for (int i=1;i<=b;i++) {
//         int tmp;
//         fin>>tmp;
//         code[tmp]=i; // here we convert the code to an id from 1..5
//         fin>>many[i];
//         fin>>price[i];
//     }
// }

// void solve() { // the procedure that solves the problem
//     for (int a=0;a<=many[1];a++)
//         for (int b=0;b<=many[2];b++)
//             for (int c=0;c<=many[3];c++)
//                 for (int d=0;d<=many[4];d++)
//                     for (int e=0;e<=many[5];e++)
//                         if ((a!=0)||(b!=0)||(c!=0)||(d!=0)||(e!=0)) {

//       int min=a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5];
// 	  /* in min we keep the lowest price at which we can buy a items
// 	     from the 1st type, +b from the 2nd+c of the 3rd... e from the
//    	      5th */

//       for (int k=1;k<=s;k++) { // for each special offer
//           int can=1,hm[6];
//           memset(&hm,0,sizeof(hm));
//           for (int l=1;l<=so[k].n;l++)
//               hm[code[so[k].prod[l].id]]=so[k].prod[l].items;
//              if ((hm[1]>a)||(hm[2]>b)||(hm[3]>c)||(hm[4]>d)||(hm[5]>e))
//                  can=0;// we check if it is possible to use that offer

//              if (can) {        // if possible-> check if it is better
//                                // than the current min
//                  int pr=so[k].price+sol[a-hm[1]][b-hm[2]][c-hm[3]]
//                           [d-hm[4]][e-hm[5]];
//                          /* Those which are not included in the special offer */
//                  if (pr<min) min=pr;
//              }
//       }
//       sol[a][b][c][d][e]=min;

//                         }
// }

// int main() {
//     memset(&so,0,sizeof(so));
//     init();
//     solve();
//     fout<<sol[many[1]][many[2]][many[3]][many[4]][many[5]]<<endl;
//     return 0;
// }


// USACO Gateway  |   Comment or Question<file_sep>/section 1/milk.cpp
/*
ID: luglian1
PROG: milk
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

class farmer{
public:
	int price;
	int amount;
};

class FarmerCompare{
public:
	bool operator()(const farmer& lhs, const farmer& rhs){
		return lhs.price < rhs.price;
	}
};

int main(){
	ifstream file_in("milk.in");
	ofstream file_out("milk.out");
	if(!file_in || !file_out){
		cerr << "Error: Failed to open file" << endl;
		return 0;
	}

	int n, m;
	file_in >> n >> m;
	vector<farmer> farmers(m);

	for(int i=0; i!=m; ++i){
		file_in >> farmers[i].price >> farmers[i].amount;
	}

	sort(farmers.begin(), farmers.end(), FarmerCompare());

	for(int i=0; i!=m; ++i){
		cout << farmers[i].price << " " << farmers[i].amount << endl;
	}

	int price = 0;
	int i=0;
	while(n > 0){
		if(n > farmers[i].amount){
			price += farmers[i].amount * farmers[i].price;
			n -= farmers[i].amount;
		}
		else{
			price += n * farmers[i].price;
			n = 0;
		}
		++i;
	}

	file_out << price << endl;

	file_in.close();
	file_out.close();
	return 0;
}
<file_sep>/section2/zerosum.cpp
/*
ID: luglian1
PROG: zerosum
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <sstream>
#include <algorithm>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "zerosum"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

//int N = 5;
//int cal[20] = {1, 12, 2, 12, 3, 10, 4, 11, 5, 0, 0, 0}; 		// 10 = '+', 11 = '-', 12 = ' '

int N = 0;
int cal[20] = {0}; 		// 10 = '+', 11 = '-', 12 = ' '

vector<string> outstr;

bool load();
void save(ostream& out);
bool save();
void solve();
int parseResult();
void dfs(int);
string makestr();


int main(){
	load();
	solve();
	save();

	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;

	for(int i=1; i <= N; ++i)
	{
		cal[(i-1) * 2] = i;
	}



	return true;
}

string makestr()
{
	stringstream ss;

	for(int i=0; i < 2 * N - 1; ++i)
	{
		switch(cal[i])
		{
			case 10:
				ss << '+';
				break;
			case 11:
				ss << '-';
				break;
			case 12:
				ss << ' ';
				break;
			default:
				ss << cal[i];
		}
	}

	return ss.str();
}

void save(ostream& out)
{
	for(vector<string>::iterator begin=outstr.begin(); begin != outstr.end(); begin++)
	{
		out << *begin << endl;
	}
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	sort(outstr.begin(), outstr.end());

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	dfs(1);

}

void dfs(int curpos)
{
	if(curpos >= 2 * N - 1)
	{
		if(parseResult() == 0)
		{	
			outstr.push_back(makestr());
		}

	}

	else
	{
		for(int i=10; i<=12; ++i)
		{
			cal[curpos] = i;
			dfs(curpos + 2);
		}
	}
}

int parseResult()
{
	int re = 0;
	int op = 0;
	int lastop = 0;
	int right = 0;

	int recal[20] = {0};
	int curpos = 0;
	// first merge space and num
	for(int i=0; i < 2 * N; ++i)
	{
		if (i % 2 == 0)	// num
		{
			right = right * 10 + cal[i];
		}
		else
		{
			op = cal[i];
			if(op != 12)
			{
				recal[curpos++] = right;
				right = 0;
				recal[curpos++] = op;
			}
		}
	}

	//PVL(recal, 20)

	// secode calc result
	re = recal[0];
	right = 0;
	op = 0;
	for(int i=1; i < curpos; ++i)
	{
		if (i % 2 == 0)	// num
		{
			right = recal[i];
			if(op == 10)	// +
			{
				re = re + right;
			}
			else if(op == 11)	// -
			{
				re = re - right;
			}
		}
		else
		{
			op = recal[i];
		}
	}

	//PV(re)

	return re;
}<file_sep>/section2/lamps.cpp
/*
ID: luglian1
PROG: lamps
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <set>
#include <string>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define INPUT_FILE "lamps.in"
#define OUTPUT_FILE "lamps.out"
using namespace std;
bool load();
void save(ostream& out);
bool save();
void solve();

int N;
int C;
bool stats[101] = {true};

vector<int> onIds;
vector<int> offIds;
set<string> results;

int main(){
	load();
	solve();
	save();
	return 0;
}

void changeLamps(int begin, int step)
{
	for(int i=begin; i<=N; i+=step)
	{
		stats[i] = !stats[i];
	}
}

bool checkValid(int remainC)
{
	for(int i=0; i<onIds.size(); ++i)
	{
		if(!stats[onIds[i]])
			return false;
	}

	for(int i=0; i<offIds.size(); ++i)
	{
		if(stats[offIds[i]])
			return false;
	}
	if(remainC % 2 == 1)
		return false;
	return true;
}

string statsToString()
{
	char s[N+1];
	for(int i=1; i<=N; ++i)
	{
		s[i-1] = stats[i] ? '1' : '0';
	}
	s[N] = '\0';
	return string(s);
}

void dfs(int buttonId, int remainC)
{
	if(checkValid(remainC))
	{
		results.insert(statsToString());
	}

	if(remainC <= 0 || buttonId > 4)
		return;

	int begin = 1;
	int step = 1;
	switch(buttonId)
	{
		case 1:
			begin = 1;
			step = 1;
			break;
		case 2:
			begin = 1;
			step = 2;
			break;
		case 3:
			begin = 2;
			step = 2;
			break;
		case 4:
			begin = 1;
			step = 3;
			break;
		default:
			break;
	}

	if(buttonId < 4)
		dfs(buttonId+1, remainC);

	changeLamps(begin, step);
	//PV(buttonId);
	//PV(statsToString());
	dfs(buttonId+1, remainC-1);
	changeLamps(begin, step);
}

void solve()
{
	for(int i=1; i<= N; ++i)
	{
		stats[i] = true;
	}
	dfs(1, C);
}


bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> N;
	file_in >> C;
	int end;
	file_in >> end;
	while(end != -1)
	{
		onIds.push_back(end);
		file_in >> end;
	}

	file_in >> end;
	while(end != -1)
	{
		offIds.push_back(end);
		file_in >> end;
	}

	return true;
}

void save(ostream& out)
{
	for(set<string>::iterator it = results.begin(); it != results.end(); ++it)
	{
		out << *it << endl;
	}
	if(results.size() == 0)
		out << "IMPOSSIBLE" << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}
<file_sep>/section3/fact4.cpp
/*
ID: luglian1
PROG: fact4
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "fact4"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

int n;
int res = 1;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> n;

	return true;
}

void save(ostream& out)
{
	out << res % 10 << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void solve()
{
	res = 1;
	for(int i=1; i<=n; ++i)
	{
		res *= i;

		while(res % 10 == 0)
			res = res / 10;

		if(res > 100000)
			res = res % 100000;
		PV(res)
	}
}

// The insight for this problem is that 0's at the end of a number come from it being divisible by 10, or equivalently, by 2 and 5. Furthermore, there are always more 2s than 5s in a factorial.

// To get the last digit of the factorial, we can run a loop to calculate it modulo 10, as long as we don't include any 2s or 5s in the product. Of course, we want to exclude the same number of 2s and 5s, so that all we're really doing is ignoring 10s. So after the loop, we need to multiply in any extra 2s that didn't have 5s to cancel them out.


// PROG: fact4
// ID: rsc001


// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// void
// main(void)
// {
// 	FILE *fin, *fout;
// 	int n2, n5, i, j, n, digit;

// 	fin = fopen("fact4.in", "r");
// 	fout = fopen("fact4.out", "w");
// 	assert(fin != NULL && fout != NULL);

// 	fscanf(fin, "%d", &n);
// 	digit = 1;
// 	n2 = n5 = 0;
// 	for(i=2; i<=n; i++) {
// 		j = i;
// 		while(j%2 == 0) {
// 			n2++;
// 			j /= 2;
// 		}
// 		while(j%5 == 0) {
// 			n5++;
// 			j /= 5;
// 		}
// 		digit = (digit * j) % 10;
// 	}

// 	for(i=0; i<n2-n5; i++)
// 		digit = (digit * 2) % 10;

// 	fprintf(fout, "%d\n", digit);
// 	exit(0);
// }<file_sep>/section2/maze1.cpp
/*
ID: luglian1
PROG: maze1
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "maze1"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

int w = 0, h = 0, all = 0;
vector<vector<int> > e;
vector<int> ex;
int res[3800] = {0};

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> w >> h;
	all = w * h;

	e.resize(all, vector<int>());

	// PV(e.size())

	string line;
	getline(file_in, line);
	for(int x=0; x < 2 * h + 1; ++x)
	{
		string line;
		getline(file_in, line);
		// cout << line << endl;
		if(line.length() < 2 * w + 1)
		{
			line += string(2 * w + 1 - line.length(), ' ');
		}
		for(int y=0; y < 2 * w + 1; ++y)
		{
			char c = line[y];
			if(c != ' ')
				continue;

			if(x % 2 == 0)
			{
				if(x == 0)
				{
					int nid = (y - 1) / 2;
					ex.push_back(nid);
				}
				else if(x == 2 * h)
				{
					int nid = w * (h-1) + (y - 1) / 2;
					ex.push_back(nid);
				}
				else
				{
					int nid1 = (x - 2) / 2 * w + (y - 1) / 2;
					int nid2 = x  / 2 * w + (y - 1) / 2;
					e[nid1].push_back(nid2);
					e[nid2].push_back(nid1);
				}
			}
			else
			{
				if(y == 0)
				{
					int nid = (x - 1) / 2 * w;
					ex.push_back(nid);
				}
				else if(y == 2 * w)
				{
					int nid = (x - 1) / 2 * w + w -1;
					ex.push_back(nid);
				}
				else if(y % 2 == 0)
				{
					int nid1 = (x - 1) / 2 * w + (y - 2) /  2;
					int nid2 = nid1 + 1;
					e[nid1].push_back(nid2);
					e[nid2].push_back(nid1);
				}
			}
		}
	}	// for

	// for(int i=0; i < w * h; ++ i)
	// {
	// 	PVL(e[i], e[i].size())
	// }

	// PV(ex.size())
	// PVL(ex, 2)

	return true;
}

void save(ostream& out)
{
	//out << res + 1 << endl;
	// PVL(res, all)
	//PV(res[0])
	int max = 0;
	for(int i=0; i< all; ++i)
	{
		if(res[i] > max)
			max = res[i];
	}
	out << max + 1 << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}


void dijkstra(int src)
{
	int q[3800] = {0};
	int s[3800] = {0};

	// init q
	for(int i=0; i< all; ++i)
	{
		q[i] = 3800;
	}
	
	for(vector<int>::iterator i=e[src].begin(); i != e[src].end(); ++i)
		q[*i] = 1;

	q[src] = 0;
	s[src] = 1;

	for(int i=0; i< all; ++i)
	{
		int minid = -1;
		int minq = 3800;
		for(int j=0; j < all; ++j)
		{
			if(s[j] == 0 && q[j] < minq)
			{
				minid = j;
				minq = q[j];
			}
		}

		//PV(minid)

		if(minid < 0)
			break;

		s[minid] = 1;
		for(vector<int>::iterator j=e[minid].begin(); j != e[minid].end(); ++j)
		{
			if(s[*j] == 0)
			{
				int newq = minq + 1;
				if(newq < q[*j])
					q[*j] = newq;
			}
		}

	}

	// PVL(q, all)

	for(int i=0; i<all; ++i)
	{

		if(q[i] < res[i])
			res[i] = q[i];

	}
	return;
}

void solve()
{
	for(int i=0; i < all; ++i)
		res[i] = 3800;

	for(vector<int>::iterator src=ex.begin(); src != ex.end(); src++)
	{
		dijkstra(*src);
	}
}


// We can solve this with a standard flood fill, using a queue to implement breadth first search. It is convenient to leave the maze in its ASCII format and just look at it as a bunch of characters, with non-space characters being walls.

// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>

// #define MAXWID 38
// #define MAXHT 100

// typedef struct Point Point;
// struct Point {
// 	int r, c;
// };

// int wid, ht;
// char maze[MAXHT*2+1][MAXWID*2+1+2];	/* extra +2 for "\n\0" */
// int dist[MAXHT*2+1][MAXWID*2+1];

// Point
// Pt(int r, int c)
// {
//     Point p;

//     p.r = r;
//     p.c = c;
//     return p;
// }

// typedef struct Queue Queue;
// struct Queue {
//     Point p;
//     int d;
// };

// Queue floodq[MAXHT*MAXWID];
// int bq, eq;

// /* if no wall between point p and point np, add np to queue with distance d+1 */
// void
// addqueue(int d, Point p, Point np)
// {
//     if(maze[(p.r+np.r)/2][(p.c+np.c)/2] == ' ' && maze[np.r][np.c] == ' ') {
// 	maze[np.r][np.c] = '*';
// 	floodq[eq].p = np;
// 	floodq[eq].d = d+1;
// 	eq++;
//     }
// }

// /* if there is an exit at point exitp, plug it and record a start point
//  * at startp */

// void
// lookexit(Point exitp, Point startp)
// {
//     if(maze[exitp.r][exitp.c] == ' ') {
// 	addqueue(0, startp, startp);
// 	maze[exitp.r][exitp.c] = '#';
//     }
// }

// void
// main(void)
// {
//     FILE *fin, *fout;
//     Point p;
//     int i, r, c, m, d;

//     fin = fopen("maze1.in", "r");
//     fout = fopen("maze1.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d %d\n", &wid, &ht);
//     wid = 2*wid+1;
//     ht = 2*ht+1;

//     for(i=0; i<ht; i++)
// 	fgets(maze[i], sizeof(maze[i]), fin);

//     /* find exits */
//     for(i=1; i<wid; i+=2) {
// 	lookexit(Pt(0, i), Pt(1, i));
// 	lookexit(Pt(ht-1, i), Pt(ht-2, i));
//     }
//     for(i=1; i<ht; i+=2) {
// 	lookexit(Pt(i, 0), Pt(i, 1));
// 	lookexit(Pt(i, wid-1), Pt(i, wid-2));
//     }

//     /* must have found at least one square with an exit */
//     /* since two exits might open onto the same square, perhaps eq == 1 */
//     assert(eq == 1 || eq == 2);	

//     for(bq = 0; bq < eq; bq++) {
// 	p = floodq[bq].p;
// 	d = floodq[bq].d;
// 	dist[p.r][p.c] = d;

// 	addqueue(d, p, Pt(p.r-2, p.c));
// 	addqueue(d, p, Pt(p.r+2, p.c));
// 	addqueue(d, p, Pt(p.r, p.c-2));
// 	addqueue(d, p, Pt(p.r, p.c+2));
//     }

//     /* find maximum distance */
//     m = 0;
//     for(r=0; r<ht; r++)
//     for(c=0; c<wid; c++)
// 	if(dist[r][c] > m)
// 	    m = dist[r][c];

//     fprintf(fout, "%d\n", m);

//     exit(0);
// }

<file_sep>/section2/cowtour.cpp
/*
ID: luglian1
PROG: cowtour
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << v[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "cowtour"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"
#define MAX_DIS 1000000

using namespace std;

struct Point 
{
	int x;
	int y;
};

ostream& operator<<(ostream& out, const Point& p)
{
	out << "(" << p.x << ", " << p.y << ")";
}

// union find
class UF
{
public:
	UF(int n)
	{
		id.resize(n, 0);
		uni.resize(n, vector<int>());
		for(int i=0; i<n; ++i)
		{
			id[i] = i;
			uni[i].push_back(i);
		};
		c = n;
	}

	int find(int i) const
	{
		return id[i];
	}

	void merge(int i, int j)
	{
		int fi = id[i];
		int fj = id[j];
		if(fi == fj)
			return;

		for(int k = 0; k < id.size(); ++k)
		{
			if(id[k] == fj)
			{
				id[k] = fi;
				uni[fi].push_back(k);
			}		
		}	
		uni[fj].clear();
		c--;
	}

	bool connected(int i, int j) const
	{
		return id[i] == id[j];
	}

	int count() const
	{
		return c;
	}

	const vector<int>& findUnion(int uid) const
	{
		return uni[uid];
	}
public:
	vector<int> id;
	int c;
	vector<vector<int> > uni;
};

int n = 0;
string g[150];
double path[150][150] = {0};
double dis[150][150] = {0};
Point pos[150];
double mindis = MAX_DIS;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	solve();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	file_in >> n;
	for(int i=0; i < n; ++i)
	{
		file_in >> pos[i].x >> pos[i].y;
	}

	for(int i=0; i< n; ++i)
	{
		file_in >> g[i];
	}

	// PVL(g, n);

	return true;
}

void save(ostream& out)
{
	out << setiosflags(ios::fixed) << setprecision(6) << mindis << endl;
}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}

void dijkstra(int src, const UF& uf)
{
	double* q = path[src];
	int s[150] = {0};

	int per[150] = {0};

	// init q
	for(int i=0; i< n; ++i)
	{
		q[i] = MAX_DIS;
	}
	
	for(int i=0; i < n; ++i)
		if(g[src][i] == '1')
		{
			q[i] = dis[src][i];
			per[i] = src;
		}

	q[src] = 0;
	s[src] = 1;

	const vector<int>& u = uf.findUnion(uf.find(src));

	double pp = 0;

	for(int i=0; i < u.size(); ++i)
	{
		int minid = -1;
		double minq = MAX_DIS;
		for(vector<int>::const_iterator j=u.begin(); j != u.end(); ++j)
		{
			if(s[*j] == 0 && q[*j] < minq)
			{
				minid = *j;
				minq = q[*j];
			}
		}

		//PV(minid)
		// if(src == 15)
		// {
		// 	PV(minid)
		// }
		// if(minq == 39793)
		// {
		// 	PV(src)
		// 	PV(minid)
		// }
		if(minid < 0)
			break;

		s[minid] = 1;
		for(vector<int>::const_iterator j=u.begin(); j != u.end(); ++j)
		{
			if(s[*j] == 0 && g[minid][*j] == '1')
			{
				double newq = minq + dis[minid][*j];
				if(newq < q[*j])
				{
					q[*j] = newq;
					per[*j] = minid;
				}
			}
		}

	}

	// if(src == 15)
	// {
	// 	int dst = 20;
	// 	double dd = 0;
	// 	while(per[dst] != 15)
	// 	{
	// 		dd += dis[dst][per[dst]];
	// 		dst = per[dst];
	// 	}
	// 	PV(dd)
	// 	PV(dis[dst][15])
	// 	dd += dis[dst][15];
	// 	PV(dd)
	// }

	return;
}

double addConnect(const UF& uf, int a, int b)
{
	double maxdis = 0;
	double dab = dis[a][b];

	const vector<int>& ua = uf.findUnion(uf.find(a));
	const vector<int>& ub = uf.findUnion(uf.find(b));

	for(vector<int>::const_iterator i=ua.begin(); i!=ua.end(); ++i)
	{
		for(vector<int>::const_iterator j=ub.begin(); j!=ub.end(); ++j)
		{
			double d = path[*i][a] + dab + path[*j][b];
			if(d > maxdis)
				maxdis = d;

			if(d >= MAX_DIS)
			{
				PV(uf.find(a))
				PV(uf.find(b))
				PVL(ua, ua.size())
				PVL(ub, ub.size())
				PV(a)
				PV(b)
				PV(*i)
				PV(*j)
				PV(dab)
				PV(path[*i][a])
				PV(path[*j][b])
				PV(d)
				exit(0);
			}
		}
	}

	// for(int i=0; i<n; ++i)
	// {
	// 	if(!uf.connected(i, a))
	// 		continue;

	// 	for(int j=0; j<n; ++j)
	// 	{
	// 		if(!uf.connected(j, b))
	// 			continue;

	// 		// recalc the dis
	// 		double d = dis(i, a) + dab + dis(j, b);
	// 		if(d > maxdis)
	// 			maxdis = d;
	// 	}
	// }

	return maxdis;
}

void solve()
{
	UF uf(n);
	for(int i=0; i < n; ++i)
		for(int j=i+1; j < n; ++j)
		{
			if(g[i][j] == '1')
				uf.merge(i, j);

			double x = pos[i].x - pos[j].x;
			double y = pos[i].y - pos[j].y;
			dis[i][j] = dis[j][i] = sqrt((x * x) + (y * y));
		}

	// PV(uf.count())

	for(int i=0; i < n; ++i)
		dijkstra(i, uf);

	vector<int> uid;

	// PVL(uf.id, n)

	for(int i=0; i<n; ++i)
	{
		//PVL(path[i], n);

		if(uf.uni[i].size()>0)
		{
			uid.push_back(i);
			//PVL(uf.uni[i], uf.uni[i].size());
			// PV(uf.uni[i][0])
			// PV(pos[uf.uni[i][0]])
			// PV(uf.uni[i].size())
		}
	}

	double maxdis = 0;
	for(int i=0; i< n; ++i)
		for(int j=i+1; j<n; ++j)
			if(path[i][j] != MAX_DIS && path[i][j] > maxdis)
				maxdis = path[i][j];

	// PV(maxdis)
	// PV(uid.size())
	for(int i=0; i<uid.size(); ++i)
	{
		const vector<int>& ui = uf.findUnion(uid[i]);
		for(int j=i+1; j<uid.size(); ++j)
		{
			const vector<int>& uj = uf.findUnion(uid[j]);
			for(vector<int>::const_iterator ci=ui.begin(); ci!=ui.end(); ++ci)
			{
				for(vector<int>::const_iterator cj=uj.begin(); cj!=uj.end(); ++cj)
				{
					// PV(*ci)
					// PV(*cj)
					double res = addConnect(uf, *ci, *cj);
					// PV(res)
					res = max(maxdis, res);
					if(res < mindis)
						mindis = res;
				}
			}
		}
	}
}


// We do a fair bit of precomputation before choosing the path to add.

// First, we calculate the minimum distance between all connected points. Then, we use a recursive depth first search to identify the different fields. Then we fill in diam[i], which is defined to be the distance to the farthest pasture that pasture i is connected to. Fielddiam[j] is the diameter of field j, which is the maximum of diam[i] for all pastures i in the field j.

// Once we have all this, selecting a path is simple. If we add a path joining pastures i and j which are in different fields, the diameter of the new field is the maximum of:

// dist to point farthest from i + dist from i to j + dist to point farthest from j.
// old diameter of the field containing pasture i.
// old diameter of the field containing pasture j.
// #include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <assert.h>
// #include <math.h>

// #define INF    (1e40)

// typedef struct Point Point;
// struct Point {
//     int x, y;
// };

// #define MAXPASTURE 150

// int n;
// double dist[MAXPASTURE][MAXPASTURE];
// double diam[MAXPASTURE];
// double fielddiam[MAXPASTURE];
// Point pt[MAXPASTURE];
// int field[MAXPASTURE];
// int nfield;

// double
// ptdist(Point a, Point b)
// {
//     return sqrt((double)(b.x-a.x)*(b.x-a.x)+(double)(b.y-a.y)*(b.y-a.y));
// }

// /* mark the field containing pasture i with number m */
// void
// mark(int i, int m)
// {
//     int j;
//     if(field[i] != -1) {
//         assert(field[i] == m);
//         return;
//     }

//     field[i] = m;
//     for(j=0; j<n; j++)
//         if(dist[i][j] < INF/2)
//             mark(j, m);
// }

// void
// main(void)
// {
//     FILE *fin, *fout;
//     int i, j, k, c;
//     double newdiam, d;

//     fin = fopen("cowtour.in", "r");
//     fout = fopen("cowtour.out", "w");
//     assert(fin != NULL && fout != NULL);

//     fscanf(fin, "%d\n", &n);
//     for(i=0; i<n; i++)
//         fscanf(fin, "%d %d\n", &pt[i].x, &pt[i].y);
        
//     for(i=0; i<n; i++) {
//         for(j=0; j<n; j++) {
//             c = getc(fin);
//             if(i == j)
//                 dist[i][j] = 0;
//             else if(c == '0')
//                 dist[i][j] = INF;        /* a lot */
//             else
//                 dist[i][j] = ptdist(pt[i], pt[j]);
//         }
//         assert(getc(fin) == '\n');
//     }

//     /* Floyd-Warshall all pairs shortest paths */
//     for(k=0; k<n; k++)
//     for(i=0; i<n; i++)
//     for(j=0; j<n; j++)
//         if(dist[i][k]+dist[k][j] < dist[i][j])
//             dist[i][j] = dist[i][k]+dist[k][j];

//     /* mark fields */
//     for(i=0; i<n; i++)
//         field[i] = -1;
//     for(i=0; i<n; i++)
//         if(field[i] == -1)
//             mark(i, nfield++);

//     /* find worst diameters involving pasture i, and for whole field */
//     for(i=0; i<n; i++) {
//         for(j=0; j<n; j++)
//             if(diam[i] < dist[i][j] && dist[i][j] < INF/2)
//                 diam[i] = dist[i][j];
//         if(diam[i] > fielddiam[field[i]])
//             fielddiam[field[i]] = diam[i];
//     }

//     /* consider a new path between i and j */
//     newdiam = INF;
//     for(i=0; i<n; i++)
//     for(j=0; j<n; j++) {
//         if(field[i] == field[j])
//             continue;

//         d = diam[i]+diam[j]+ptdist(pt[i], pt[j]);
//         if(d < fielddiam[field[i]])
//             d = fielddiam[field[i]];
//         if(d < fielddiam[field[j]])
//             d = fielddiam[field[j]];
    
//         if(d < newdiam)
//             newdiam = d;
//     }

//     fprintf(fout, "%.6lf\n", newdiam);
//     exit(0);
// }
<file_sep>/section 1/gift1.cpp
/*
ID: luglian1
PROG: gift1
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

struct person{
	string name;
	int initial_m;
	int final_m;
	//int gifts;
	vector<string> friends;
};

void readPerson(person& p, ifstream& in){
	in >> p.initial_m;
	int fn;
	in >> fn;
	p.friends.resize(fn);
	for(int i=0; i!=fn; ++i){
		in >> p.friends[i];
	}
	p.final_m = 0;
}

int main(){

	ifstream in("gift1.in");
	ofstream out("gift1.out");

	int n;
	in >> n;

	cout << n << endl;

	//return 0;

	map<string, int> person_id;
	vector<person> person_list(n);

	cout << person_list.size() << endl;

	person ptmp;
	for(int i=0; i!=n; ++i){
		in >> person_list[i].name;
		person_id.insert(pair<string, int>(person_list[i].name, i));
		cout << person_id.size() << " " << person_list[i].name << endl;
	}


	string name;
	for(int i=0; i!=n; ++i){
		in >> name;
		cout << person_id.find(name)->second << endl;
		readPerson(person_list[person_id.find(name)->second], in);
	}

	cout << "i am here" << endl;
	// give gifts
	for(int i=0; i!=n; ++i){
		if(person_list[i].friends.size() == 0)
			continue;
		int quo = person_list[i].initial_m / person_list[i].friends.size();
		int rem = person_list[i].initial_m % person_list[i].friends.size();
		person_list[i].final_m += rem;
		cout << "i am here" << endl;
		for(int j=0; j < person_list[i].friends.size(); ++j){
			person_list[person_id.find(person_list[i].friends[j])->second].final_m += quo;
		}
		cout << "finish" << endl;
	}

	
	for(int i=0; i!=n; ++i){
		out << person_list[i].name << " " 
			<< person_list[i].final_m - person_list[i].initial_m << endl;
	}

	in.close();
	out.close();
	return 0;
}
<file_sep>/template.cpp
/*
ID: luglian1
PROG: beads
LANG: C++
*/

#include <iostream>
#include <string>
#include <fstream>
#define PV(v) std::cout << #v << " = " << v << std::endl;
#define PVL(v, n) \
	std::cout << #v << " = ";\
	for(int _i=0; _i<n; ++_i) \
		{std::cout << (v)[_i] << ", ";}\
	std::cout << std::endl;
#define PROB_NAME "combo"
#define INPUT_FILE PROB_NAME".in"
#define OUTPUT_FILE PROB_NAME".out"

using namespace std;

bool load();
void save(ostream& out);
bool save();
void solve();

int main(){
	load();
	save();
	return 0;
}

bool load()
{
	ifstream file_in(INPUT_FILE);
	if(!file_in)
	{
		cerr << "Error: Failed to load file." << endl;
		return false;
	}

	return true;
}

void save(ostream& out)
{

}

bool save()
{
	ofstream file_out(OUTPUT_FILE);
	if(!file_out){
		cerr << "Error: Failed to open file." << endl;
		return false;
	}

	save(file_out);
	save(cout);

	return true;
}
