#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>

using namespace std;

int *val = 0;
int up = 1000000;

int &Q(int n) {
	if (n<1 || n>up) {
		throw "out of bounds";
	} else {
		return val[n-1];
	}
}

vector<int> i;
int w = 0;
int mx = 10;

void complete(int n0) {
	try {
		for (int n=n0; n<=up; n++) {
			int val = 0;
			for (size_t k=0; k<i.size(); k++) {
				val += Q(n-Q(n-i[k]));
			}
			Q(n) = val;
		}

		// ok
		printf("[");
		for (int n=1; n<=n0-1; n++) {
			if (n>1) {
				printf(", ");
			}
			try {
				int val = 0;
				for (size_t k=0; k<i.size(); k++) {
					val += Q(n-Q(n-i[k]));
				}
				if (val==Q(n)) {
					// implied
					printf("(%d)", Q(n));
				} else {
					// fixed
					printf("%d", Q(n));
				}
			} catch (...) {
				// fixed
				printf("%d", Q(n));
			}
		}
		printf("]\n");
		fflush(stdout);
	} catch (...) {
		// stuck
	}
}

void search() {
	printf("# searching for Q(n) = ");
	for (size_t k=0; k<i.size(); k++) {
		if (k) {
			printf(" + ");
		}
		printf("Q(n-Q(n-%d))", i[k]);
	}
	printf("\n");
	printf("# w=%d max=%d up=%d\n", w, mx, up);
	fflush(stdout);

	for (long long k=0; k<LLONG_MAX; k++) {
		if (w) {
			for (int n=1; n<=w; n++) {
				Q(n) = 1 + (rand() % mx);
			}
			complete(w+1);
		} else {
			long long rem = k;
			for (int n=1;; n++) {
				Q(n) = 1 + (rem % mx);
				rem /= mx;
				if (rem==0) {
					complete(n+1);
					break;
				}
			}
		}
	}
}

int opt = 0;
bool match(const char *arg, const char *prefix) {
	size_t len = strlen(prefix);
	if (strncmp(arg, prefix, len)==0) {
		opt = atoi(arg+len);
		return opt>0;
	} else {
		return false;
	}
}

int main(int argc, const char **argv) {
	if (argc==1) {
		printf("Usage: %s options...\n"
		       "Options are:\n"
			   "   up=#     compute/check up to this number of terms (at least 1000)\n"
			   "   w=#      fixed number of random initial values\n"
			   "            when missing: explore all solutions with 1, 2, 3, ... initial values\n"
			   "   max=#    max value for initial terms\n"
			   "   #        offsets to satisfy: Q(n) = Sum Q(n-Q(n-#))\n", argv[0]);
	} else {
		for (int a=1; a<argc; a++) {
			if (match(argv[a], "up=")) { up = opt; } else
			if (match(argv[a], "w=")) { w = opt; } else
			if (match(argv[a], "max=")) { mx = opt; } else
			if (match(argv[a], "")) { i.push_back(opt); } else
			{
				printf ("Invalid option: %s\n", argv[a]);
				return 1;
			}
		}

		if (up<1000) {
			up = 1000;
		}
		if (w>100) {
			printf("w way too large\n");
			return 2;
		}

		if (i.size()==0) {
			printf("missing offsets\n");
			return 3;
		}

		val = (int*)malloc(up * sizeof(int));
		if (val==0) {
			printf("out of memory\n");
			return 4;
		}

		search();

		free(val);
		val = 0;
	}

	return 0;
}