시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 13 | 9 | 7 | 63.636% |
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 = 9978, Mlim = 100 000, Plim = 100 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
Olympiad > Central European Olympiad in Informatics > CEOI 2016 > Day 2 6-7번