1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <climits>
#include <cstring>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

typedef unsigned long UINT;
typedef signed long SINT;
typedef unsigned long long UINT64;
typedef signed long long SINT64;

[[maybe_unused]] constexpr SINT MAX_SINT = LONG_MAX;
[[maybe_unused]] constexpr UINT MAX_UINT = ULONG_MAX;
[[maybe_unused]] constexpr SINT MAX_SINT64 = LLONG_MAX;
[[maybe_unused]] constexpr UINT MAX_UINT64 = ULLONG_MAX;

// TODO optimize queue
// - vector with pre-reserved size will be okay as it has double-ended access
// - no need to remove queue elems, just skip them
// - mark area under ananlysis (unless it's done already) to avoid repetitive
//   queue items

// Benchmark
#ifdef LOCAL
#include "../benchmark.h"
#define BENCH_START bench_time_start();
#define BENCH_M_START(comment) bench_meth_start(comment);
#define BENCH_M_END bench_meth_end();
#else
#define BENCH_START
#define BENCH_M_START(comment)
#define BENCH_M_END
#endif

/** Redirect stdin to provide input with Qt Creator */
void reopenInput(int argc, char** argv) {
#ifdef LOCAL
	if (argc > 1) {
		auto inFile = argv[1];
		cerr << "Reopening stdin to: " << inFile << endl;
		auto success = freopen(inFile, "r", stdin);
		if (!success) {
			cerr << "Error when opening file!" << endl;
			cerr << std::strerror(errno) << endl;
		}
	}
#endif
}

/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */

static SINT k;

void printNode(SINT a, SINT b) {
	cout << a << " " << b << "\n";
}

/**
 * It always produces exactly 60 nodes.  It is an acceptable simplification.
 *
 * It can be proven that 60 nodes is enough to draw 10^9 different paths
 * (log_2 10^9).
 */
void solve()
{
	const SINT last_node = 60;

	cout << last_node << "\n";

	SINT remaining = k;
	SINT curr_node = 1;

	while (remaining > 1) {
		bool odd = remaining % 2 == 1;
		remaining = remaining / 2;

		SINT next_node = curr_node + 2;
		SINT alternate_node = curr_node + 1;

		// print current node
		printNode(next_node, alternate_node);

		// print alternate node
		printNode(next_node, odd ? last_node : -1);

		curr_node = next_node;
	}

	// add node padding so that last node is 100th
	while (curr_node < last_node) {
		printNode(++curr_node, -1);
	}

	// print last node
	printNode(-1, -1);
	cout << flush;
}

int main(int argc, char** argv)
{
	BENCH_START
	reopenInput(argc, argv);
	std::ios::sync_with_stdio(false);

	cin >> k;
	cerr << "k: " << k << endl;

	solve();
	return 0;
}