#include "bits/stdc++.h"
// #include "algotester.h"
#include "algotester_generator.h"
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;
string computation_times[21] =
{
"1 1 8 14 21 28 34 41 48 54 61",
"1 2 8 53 98 143 188 233 278 323 368",
"1 3 4 7 10 12 13",
"2 1 8 29 54 76 95 113 128 140 150",
"2 2 1 8",
"2 3 4 7 11 14 16",
"3 1 16 32 59 85 110 134 159 182 205 228 250 271 293 314 334 355 375",
"3 2 8 33 60 87 114 141 167 193 219",
"4 1 6 39 76 111 150 186 220",
"5 1 11 52 99 147 191 239 286 332 383 427 474 521",
"6 1 8 100 192 274 357 456 513 586 657",
"7 1 9 78 152 220 294 362 421 497 563 627",
"8 1 13 30 52 77 96 121 142 162 182 205 221 235 257 275",
"8 2 8 24 43 63 81 99 117 134 151",
"9 1 10 13 22 31 40 49 57 65 74 82 89",
"9 2 7 9 16 22 28 33 40 45",
"9 3 3 6 10 13",
"10 1 7 18 28 38 48 58 69 78",
"10 2 8 13 21 29 36 44 52 59 67",
"10 3 8 6 8 10 12 14 17 17 19",
"31 107 20"
};
void PrintComputationTimes()
{
FOR (i, 0, 21)
{
cout << computation_times[i] << endl;
}
}
const int N = 10000;
const int U = 5000000;
inline double RandLaplace(AlgotesterGenerator& gen, double beta)
{
double u1 = gen.randDouble(), u2 = gen.randDouble();
if (u1 <= 0.5)
{
return -beta * log(1 - u2);
}
else
{
return beta * log(u2);
}
}
// n: number of packets; p: probability for each type of packet; u: range for the packet times
void GenRandUniform(AlgotesterGenerator& gen, int n, vector<double> p, int u)
{
vector<pair<int, int> > a(n);
cout << n << endl;
FOR (i, 0, n)
{
double q = gen.randDouble();
int type = q < p[0] ? 1 : (q < p[0] + p[1] ? 2 : 3);
a[i].first = gen.randInt(1, u);
a[i].second = type;
}
sort(a.begin(), a.end());
FOR (i, 0, n)
{
cout << i + 1 << ' ' << a[i].second << ' ' << a[i].first << endl;
}
}
// n: number of packets; p: probability for each type of packet; d: expected gap between two packets; u: range for
// random fluctuation
void GenRandUniformBounded(AlgotesterGenerator& gen, int n, vector<double> p, int d, int u)
{
vector<pair<int, int> > a(n);
cout << n << endl;
FOR (i, 0, n)
{
double q = gen.randDouble();
int type = q < p[0] ? 1 : (q < p[0] + p[1] ? 2 : 3);
a[i].first = i * d + gen.randInt(1, u);
a[i].second = type;
}
sort(a.begin(), a.end());
FOR (i, 0, n)
{
cout << i + 1 << ' ' << a[i].second << ' ' << a[i].first << endl;
}
}
// n: number of packets; p: probability for each type of packet; d: expected gap between two packets; beta: parameter
// for Laplace distribution
void GenRandLaplace(AlgotesterGenerator& gen, int n, vector<double> p, int d, double beta)
{
vector<pair<int, int> > a(n);
cout << n << endl;
FOR (i, 0, n)
{
double q = gen.randDouble();
int type = q < p[0] ? 1 : (q < p[0] + p[1] ? 2 : 3);
int t = int(i * d + RandLaplace(gen, beta));
a[i].first = max(1, min(U, t));
a[i].second = type;
}
sort(a.begin(), a.end());
FOR (i, 0, n)
{
cout << i + 1 << ' ' << a[i].second << ' ' << a[i].first << endl;
}
}
int delta[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15, 20, 30, 50, 80, 100, 150};
int deltaNumber = sizeof(delta) / sizeof(int);
void Gen(AlgotesterGenerator& gen, int minDelay, int minDelay1, int minDelay2, vector<double> p, int type, int maxn)
{
int n;
FOR (i, 0, deltaNumber)
{
if (type == 0)
{
int mean = minDelay + delta[i];
assert(mean * N <= U);
n = gen.randInt(maxn / 2) + maxn / 2;
GenRandUniform(gen, n, p, n * mean);
return;
}
type--;
}
FOR (i, 0, deltaNumber)
{
if (type == 0)
{
int mean = minDelay1 + delta[i];
assert(mean * N <= U);
n = gen.randInt(maxn / 2) + maxn / 2;
double ratio = 0.1 * exp(6 * gen.randDouble());
GenRandUniformBounded(gen, n, p, mean, mean*ratio);
return;
}
type--;
}
FOR (i, 0, deltaNumber)
{
if (type == 0)
{
int mean = minDelay2 + delta[i];
assert(mean * N <= U);
n = gen.randInt(maxn / 2) + maxn / 2;
double beta = mean * 0.1 * exp(6 * gen.randDouble());
GenRandLaplace(gen, n, p, mean, beta);
return;
}
type--;
}
throw -1;
}
void PrintPackets(AlgotesterGenerator& gen)
{
int totalTypes = 5 * 3 * deltaNumber + 3;
int type = gen.randInt(totalTypes);
if (type < 3 * deltaNumber)
{
Gen(gen, 157, 157, 157, {1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0}, type, N);
return;
}
type -= 3 * deltaNumber;
if (type < 3 * deltaNumber)
{
Gen(gen, 339, 332, 332, {1, 0, 0}, type, N);
return;
}
type -= 3 * deltaNumber;
if (type < 3 * deltaNumber)
{
Gen(gen, 312, 310, 310, {0.9, 0.05, 0.05}, type, N);
return;
}
type -= 3 * deltaNumber;
if (type <3 * deltaNumber)
{
Gen(gen, 273, 271, 271, {0.75, 0.15, 0.1}, type, N);
return;
}
type -= 3 * deltaNumber;
if (type < 3 * deltaNumber)
{
Gen(gen, 287, 287, 287, {0.85, 0.05, 0.1}, type, 500);
return;
}
type -= 3 * deltaNumber;
if (type == 0) GenRandUniform(gen, 10000, {1, 0, 0}, 3410000);
else if (type == 1) GenRandUniformBounded(gen, 10000, {1, 0, 0}, 331, 200);
else if (type == 2) GenRandLaplace(gen, 10000, {1, 0, 0}, 334, 10000);
else throw -1;
}
int main(int argc, char* argv[])
{
//ios::sync_with_stdio(false); cin.tie(0);
auto gen = AlgotesterGenerator(argc, argv);
PrintComputationTimes();
PrintPackets(gen);
}
