SRM 587

JumpFurther.cpp

/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

const int MOD = 1000000007;
const int INF = 0x7fffffff;

/* -&$&#*( &#*@)^$@&*)*/

const int N = 50;

class JumpFurther {
public:
	int furthest(int n, int badStep) {
        int res = n*(n+1) / 2; REP_1(i, n) if ((i + 1) * i / 2 == badStep){
            --res; break;
        }
		return res;
	}

};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			int N                     = 2;
			int badStep               = 2;
			int expected__            = 3;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			int N                     = 2;
			int badStep               = 1;
			int expected__            = 2;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			int N                     = 3;
			int badStep               = 3;
			int expected__            = 5;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			int N                     = 1313;
			int badStep               = 5858;
			int expected__            = 862641;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 4: {
			int N                     = 1;
			int badStep               = 757065;
			int expected__            = 1;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 5: {
			int N                     = ;
			int badStep               = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 6: {
			int N                     = ;
			int badStep               = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 7: {
			int N                     = ;
			int badStep               = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = JumpFurther().furthest(N, badStep);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE

ThreeColorability.cpp

/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

/* -&$&#*( &#*@)^$@&*)*/

const int N = 50;
int G[N][N], C[N];
int n, m;

bool dfs(int u, bool c = 0){

    if (~C[u]) return C[u] == c;

    C[u] = c; REP(v, n) if (u != v){
        bool b0 = 0, b1 = 0;
        REP(i, m) if (~G[u][i] && ~G[v][i]){
            if (G[u][i] == G[v][i]) b0 = 1; else b1 = 1;
        }
        if (!b0 && !b1) continue;
        if (b0 && b1 || !dfs(v, C[u]^b1)) return 0;
    }
    return 1;
}

bool valid(){
    FLC(C, -1); REP(i, n) if (!~C[i]){
        if (!dfs(i)) return 0;
    }
    return 1;
}

class ThreeColorability {
public:
	vector <string> lexSmallest(vector <string> cells) {

        n = SZ(cells), m = SZ(cells[0]);
        REP_2(i, j, n, m) G[i][j] = cells[i][j] == '?' ? -1 : cells[i][j] == 'Z';

		if (!valid()) return {};
		else {
            REP_2(i, j, n, m) if (!~G[i][j]){
                G[i][j] = 0; if (!valid()) G[i][j] = 1;
                assert(valid());
            }

            vector <string> res(n);
            REP_2(i, j, n, m) res[i] += G[i][j] ? 'Z' : 'N';
            return res;
		}
	}
};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << "{"; for (typename vector<T>::const_iterator vi=v.begin(); vi!=v.end(); ++vi) { if (vi != v.begin()) os << ","; os << " " << *vi; } os << " }"; return os; }
	template<> ostream& operator<<(ostream &os, const vector<string> &v) { os << "{"; for (vector<string>::const_iterator vi=v.begin(); vi!=v.end(); ++vi) { if (vi != v.begin()) os << ","; os << " \"" << *vi << "\""; } os << " }"; return os; }

	int verify_case(int casenum, const vector <string> &expected, const vector <string> &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			string cells[]            = {"???", "NN?", "N?Z", "?NN"};
			string expected__[]       = {};

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}
		case 1: {
			string cells[]            = {"??????????????????????????????????????????????????", "??????????????????????????????????????????????????", "??????????????????????N??N????????????????????????", "?????????Z???????????????????????????????????Z????", "?????????????????????N???????????????Z????????????", "??????????????????????????????????????????????????", "???N????????????????Z?????????????????????????????", "??????????????????????????????????????ZN??????????", "??????????????????????????????????????????????????", "???????????????????????????N???????N??????????????", "??????????????????????????????????????????????????", "????Z???????????????????????N?????????????????????", "Z??????????????????????????????????Z??????????????", "???????????N???????????Z??????????????????????????", "???Z??????????????????????N???????????????????????", "???????????????????Z????????????N?????????????????", "??????????????????????????????????????????????????", "??????????????????N????????Z??????????????????????", "????????????????????????????????Z????N????????????", "??????????????????????????????????????????????????", "??????????????????????????????N?????????????????Z?", "??????????????????????????????????????????????????", "????????????N?N???????????????????????????????????", "????????????????????N??????????N??????????????????", "??????????N???????????Z???????????????????????????", "????????????N????????N????????????????????????????", "??N?????????????????????????????????????????????Z?", "?????????????????N??????Z?????????????????????????", "??????????????Z????????N??????????????????????????", "???????????????????N??????????????????N???????????", "??????????Z??????????????????????????????????Z????", "?Z???????????????????????????????N????????????????", "Z??????????????????????????????Z??????????????????", "????????Z????????????????????????Z????????????????", "??????????????????????????????????????????????????", "??????????????????????????????????????????????????", "??????????????????????????????????????????????????", "??????????????????????????????????????????????????", "???????????Z?????????????N????????????????????????", "??????????????????????????????????????????????????", "????????Z?????????????????N???????????????????????", "??????????????????????????????????????????????????", "??????????????????Z?????N?????????????????????????", "??????????????????????????????????????????????????", "??Z??????Z????????????????????????????????????????", "??????????????????????????????????????????????????", "?????????????????N??????????N?????????????????????", "?N????????????????????????????Z???????????????????", "??????????????????????????????????????????????????", "????N??????????????????????????????????N??????????"};
			string expected__[]       = {};

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}
		case 2: {
			string cells[]            = {"ZZZ", "ZNZ"};
			string expected__[]       = { };

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}
		case 3: {
			string cells[]            = {"N?N??NN","??ZN??Z","NN???Z?","ZZZ?Z??","Z???NN?","N?????N","ZZ?N?NN"};
			string expected__[]       = { };

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}
		case 4: {
			string cells[]            = {"ZZZZ","ZZZZ","ZZZZ"};
			string expected__[]       = {"ZZZZ", "ZZZZ", "ZZZZ" };

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}

		// custom cases

/*      case 5: {
			string cells[]            = ;
			string expected__[]       = ;

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}*/
/*      case 6: {
			string cells[]            = ;
			string expected__[]       = ;

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}*/
/*      case 7: {
			string cells[]            = ;
			string expected__[]       = ;

			clock_t start__           = clock();
			vector <string> received__ = ThreeColorability().lexSmallest(vector <string>(cells, cells + (sizeof cells / sizeof cells[0])));
			return verify_case(casenum, vector <string>(expected__, expected__ + (sizeof expected__ / sizeof expected__[0])), received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE

TriangleXor.cpp

/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

const int N = 50;

DB w;
DB y(int i){return (DB)i/(i+w);}
DB x(int i){return y(i)*w;}

class TriangleXor {
public:
	int theArea(int W) {

        DB res = 0; w = W;

        if (~W&1) res += w/4;

        for (int i=1;i<=W;i+=2){
            res += x(i)-x(i-1);
        }

        //res += w/8;
        for (int i=1;i<=W;i+=2){
            res += (W-2*x(i)) * (y(i+1)-y(i-1))/2;
        }

		return res;
	}
};


// BEGIN CUT HERE
namespace moj_harness {
	int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum) {
		switch (casenum) {
		case 0: {
			int W                     = 1;
			int expected__            = 0;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 1: {
			int W                     = 2;
			int expected__            = 1;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 2: {
			int W                     = 3;
			int expected__            = 1;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 3: {
			int W                     = 4;
			int expected__            = 2;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 4: {
			int W                     = 5;
			int expected__            = 2;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}
		case 5: {
			int W                     = 12345;
			int expected__            = 4629;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 6: {
			int W                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 7: {
			int W                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
/*      case 8: {
			int W                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = TriangleXor().theArea(W);
			return verify_case(casenum, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}

int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE