Build a Computer
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 1024 megabytes
You want to build a computer to achieve a specific functionality: Given an integerx, determine whether
x lies within the interval[L, R]. To accomplish this, you designed a directed acyclic graph (DAG) with
edge weights of0 and 1, which contains a starting node with an indegree of0 and an ending node with an
outdegree of0. By starting from the starting node and following a path to the ending node, the sequence
of the traversed edge weights forms a binary representation of an integer within the range[L, R] without
leading zeros. Every integer within the range[L, R] must correspond to exactly one unique path in this
graph. In this way, you can determine whether an integer lies within the range[L, R] by checking if its
binary representation can be constructed by traversing this DAG.
Clearly, you could separate the corresponding path for each integer into individual chains. However, you
realized that for a large range, such a DAG would require too many nodes, and the computer you built with
only 256 MiB of memory cannot store it. Therefore, you need to compress this DAG, allowing different
paths to share nodes, in order to reduce the number of nodes and edges. Formally, you need to construct
a DAG with no more than100 nodes, where each node has an outdegree of at most200. The DAG must
have edge weights of0 and 1, with exactly one starting node with an in-degree of0 and one ending node
with an out-degree of0. Every integer in the range[L, R] must correspond toexactly one unique path
from the start to the end in this DAG, and no path should represent any integer outside the range[L, R].
Note that none of the binary sequences formed by any path in the graph should have leading zeros. There
may be two edges with different weights between two nodes.
Input
A single line containing two positive integersL, R(1 ≤L ≤R ≤106).
Output
The first line should output the number of nodesn (1 ≤n ≤100). You need to make n as small as possible and your score will be determined by the value of n.
For the nextn lines, thei-th line should start with an integerk (0 ≤k ≤200), representing the number
of outgoing edges from nodei. Then output2 ·k integers ai,k, vi,k (1 ≤ai,k ≤n, ai,k ̸= i, vi,k ∈{0, 1}),
which means that nodei has a directed edge with weightvi,k to node ai,k. You must ensure that the
output represents a directed acyclic graph that satisfies the requirements.
Example
standard input standard output
5 7 8
3 2 1 3 1 4 1
1 5 0
1 6 1
1 7 1
1 8 1
1 8 0
1 8 1
0
Page 1 of 1