시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 41 | 19 | 19 | 47.500% |
Henry and Hetty were recently hired by a networking company from Piatra Neamț. Their first project is to create a new type of router, the revolutionary Connect Ethernet Operating Interface 2016, comprised of:
A node X can send data to a node Y (and hence Y can receive data from X) if:
If a node X can send data to a node Y, and X ≠ Y, then we define a data path from X to Y as a set of direct connections {(A1, A2), (A2, A3), … (AL-1, AL)} for some L ≥ 2, such that A1 = X and AL = Y.
A router works properly if:
Like any other electronic device, a router needs electricity to work. Let's define the power needed to operate a node X as PX = INX × OUTX, where INX is the number of input nodes that can send data to X, and OUTX is the number of output nodes that can receive data from X. Let's define the maximum power used by the router as Pmax = max(P1, P2, … P2×N+K).
The project manager has given Henry and Hetty the technical specifications for building a few test routers, listed in the table below. For each of these specifications, the manager wants a router which:
On the first and only line, three integers: N, the number of input and output nodes; Mlim, the maximum number of direct connections allowed; and Plim, the maximum power the router uses.
N = 5101, Mlim = 500 000, Plim = 500 000
You will output two integer numbers separated by a space: Ntot = 2×N + K, representing the total number of nodes used to build the router; and M, representing the total number of direct connections used. On each of the following M lines you should output a pair of integers X and Y, meaning a direct connection from node X to node Y was built.
3 100 200
9 8 1 7 2 7 3 8 7 8 8 4 8 9 9 5 9 6
Henry and Hetty must build a router with 3 input nodes and 3 output nodes, which uses at most 100 direct connections and uses a maximum power of 200.
They use 9 nodes overall (input nodes 1, 2 and 3, output nodes 4, 5 and 6, and internal nodes 7, 8 and 9), and 8 direct connections.
The maximum power the router uses is 9 and is given by the power of vertex 8, which can receive data from IN8=3 input nodes and can send data to OUT8=3 output nodes.
3 100 200
6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6
Another valid router for the same specifications uses 6 nodes overall (the three input nodes and the three output nodes).
The maximum power this router uses is 3: each input node can receive data only from itself and can send data to all three output nodes. Similarly, each output node can receive data from all 3 input nodes and can send data only to itself.
Olympiad > Central European Olympiad in Informatics > CEOI 2016 > Day 2 6-4번