// Author: Ivan Kazmenko (gassa@mail.ru)
// Generator for problem "twosum"
module gen;
import std.algorithm;
import std.conv;
import std.exception;
import std.format;
import std.random;
import std.range;
import std.stdio;

immutable string testFormat = "%03d";
enum generateAnswers = false;

immutable int minN =       1;
immutable int maxN = 200_000;
immutable int minS =       0;
immutable int maxS = 999_982;
immutable int notS = 742_681;

immutable int M = maxS + 1;

int next (int s)
{
	return (s * 618_023L + 1) % (maxS + 1);
}

int prev (int s) {
  int t = ((s + (M - 1).to!long) * 548_967L) % M;
  enforce(next(t) == s);
  return t;
}

static assert (next (notS) == notS);

struct Test
{
	int n;
	int s;

	string comment;

	void validate () const
	{
		enforce (minN <= n && n <= maxN);
		enforce (minS <= s && s <= maxS);
		enforce (s != notS);
	}

	void print (File f) const
	{
		f.writeln (n, " ", s);
	}

	string log () const
	{
		return format !("%s (n = %s, s = %s)") (comment, n, s);
	}
}

Test [] tests;

void printAllTests ()
{
	foreach (testNumber, test; tests)
	{
		test.validate ();
		auto testString = format (testFormat, testNumber + 1);
		auto f = File (testString, "wt");
		test.print (f);
		static if (generateAnswers)
		{
			auto g = File (testString ~ ".a", "wt");
			test.printAnswer (g);
		}
		writeln (testString, ": ", test.log ());
	}
}

Mt19937 rndLocal;
Unqual !(T) rndValue (T) () {return uniform !(T) (rndLocal);}
Unqual !(T) rndValue (T) (T lim)
    {return uniform (cast (T) (0), lim, rndLocal);}
Unqual !(T) rndValue (string boundaries = "[)", T) (T lo, T hi)
    {return uniform !(boundaries) (lo, hi, rndLocal);}

auto rndChoice (R) (R r) {return r[rndValue (cast (int) (r.length))];}

void rndShuffle (R) (R r)
{
	auto len = r.length.to !(int);
	foreach (i; 0..len)
	{
		int k = rndValue (i, len);
		r.swapAt (i, k);
	}
}

Test maximizeSumOfS (size_t n) {
  uint[] a;
  a.reserve(M);
  int s = 0;
  foreach (i; 0..M) {
    a ~= s;
    s = next (s);
  }
  ulong t = 0;
  foreach (i; 0 .. M) {
    t += a[i];
  }
  ulong max_sum;
  int best;
  foreach (i; 1 .. M + 1) {
    t += a[(i + n) % M];
    t -= a[i-1];
    if (max_sum < t) {
      max_sum = t;
      best = i - 1;
    }
  }
  return Test(n.to!(int), best, format!("maximizeSumOfS (n = %d, sum_s = %d)")(n, max_sum));
}

int prev_n (int s, size_t n) {
  foreach (i; 0 .. n) {
    s = prev (s);
  }
  return s;
}

void main ()
{
	rndLocal.seed (225_613_484);
	tests ~= Test (      4, 179_629, "example test 1");

	tests ~= Test (      1,       0, "minimal test 1");
	tests ~= Test (      1,       prev(0), "minimal test 2 (bound case s = 0 for single computation)");

	tests ~= Test (     11,     123, "general test 1");
	tests ~= Test (    100,       1, "general test 2");
	tests ~= Test (   1000,  12_456, "general test 3");
	tests ~= Test ( 10_000,  53_467, "general test 4");
	tests ~= Test ( 50_000, 197_573, "general test 5");
	tests ~= Test (100_000, 999_982, "general test 6");
	tests ~= Test (125_000, 123_789, "general test 7");
	tests ~= Test (150_555, 999_982, "general test 8");
	tests ~= Test (175_666, 654_321, "general test 9");
	tests ~= Test (199_998, 987_754, "general test 10");
	tests ~= Test (199_999, 123_123, "general test 11");
	tests ~= Test (200_000,     321, "general test 12");
	tests ~= Test (200_000,   4_321, "general test 13");
	tests ~= Test (200_000, 544_321, "general test 14");
	tests ~= Test (200_000, 777_777, "general test 15");
	tests ~= Test (200_000, 111_111, "general test 16");
  tests ~= maximizeSumOfS (200_000);
  foreach (s; 62 .. 67) {
    tests ~= Test (maxN, prev_n (s, maxN), format!("last s equal to %d")(s));
  }
	printAllTests ();
}