题面

小氟发现，这张图正好有 $n+1$ 条从 1 到 114 的路径，并且在这些路径的边权和中， $[0,n]$ 的每一个整数正好出现了一次。

小氟想问你，这张图可能是什么样的？请你给出一种方案。

所有的点编号和边权皆为非负整数，点的编号要在 $[1,n]$ 范围内。

$n\leq32500$ ，方案中点数 $<18$ ，边数 $<48$ ，边权 $\le n$ 。 其中点数包含和。

题解

相当于把 $[0,n]$ 二进制拆分。构造一列 $i\rightarrow i+1$ ，边权 $2^k,0$ 的边。1 到某个点 $i$ 可以扩充 $2^k$ 的范围。

代码

const int N = 514;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	struct node {
		int u, v, w;
	};
	vector <node> e;
	int main () {
		n = Read();
		int t = log2(n);
		e.emplace_back((node){t, 114, 1});
		e.emplace_back((node){t, 114, 0});
		for (int i = 2; i <= t; i++) {
			e.emplace_back((node){i - 1, i, 1 << t - i + 1});
			e.emplace_back((node){i - 1, i, 0});
		}
		for (int i = t - 1, j = 0; i; i--) {
			j |= 1 << i + 1;
			if (!((n >> i) & 1)) continue;
			e.emplace_back((node){1, t + 1 - i, n & j});
		}
		if (n & 1) e.emplace_back((node) {1, 114, n - 1});
		e.emplace_back((node) {1, 114, n});
		printf ("%d %ld\n", t + 1, e.size());
		for (auto v: e) printf ("%d %d %d\n", v.u, v.v, v.w);
		return 0;
	}
}

int main () {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	Main::main();
	return 0;
}