当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6561:High Priestess

Special Judge 特殊评判
题目描述
Look for areas in your life that may be out of balance or lacking ‘flow’ and ease. Knowledge of how to fix these issues will not come through thinking and rationalising, but through feeling and trusting your intuition, so allow yourself the time and space to meditate and listen to your inner voice. Your intuitive sense right now is providing you with useful and helpful information and is assisting you to become more in touch with your subconscious mind.

Your task is simple: to build a circuit with effective resistance as close to a target value as possible.
Specifically, you are given a 1V battery, $10^4$ resistors of 1$\Omega$ and unlimited number of conductive posts. You can attach each resistor to an arbitrary pair of different posts. Different resistors may be attached to same pairs of posts and you do not need to use up all the resistors (definitely not all posts either). When you finish all attachments, you can finally choose two posts to attach the battery on.
For convenience, we can observe the resistor network you build as a undirected graph G = (V, E). Naturally in this mapping each post with at least one resistor attached to it is a vertex in V and each resistor is an undirected edge in E. Following basic physics laws we can calculate the voltage at each post x, denoted as $v_x$ (suppose the voltage at the negative post of the battery is 0) and the sum of current flowing through all resistors between posts x and y, denoted as ixy. We can now define the effective resistance between any pair of posts a and b as

Suppose the battery is attached to post $a_0$ and $b_0$, your task is to build a graph such that |$r_{a_0b_0}$- r| ÷ $10^{-7}$ for any given r.
There are one more constraint - you are only allowed to build the graph following the procedures below.
First you have n resistors of 1з, numbered from 0 to n n 1. And each of the resistors can be seen as a graph of 2 posts and 1 edge. You are then allowed to perform several merge operations to any two of the graphs you currently have to form a new graph. The original two graphs are then removed and the new graph is added to your graph pool and numbered consecutively starting from n (that is to say, the graph obtained in the first operation has the number n and in the second operation the number is n + 1 and so on).
There are two types of merge operations, a serial merge or a parallel merge. Specifically, if the two graphs you choose to merge is o -> A -> o and o -> B -> o (the o refers to the posts and the -> refers to how the current flows) respectively. After a serial merge, the new graph will be

and after a parallel merge, the new graph will be
输入解释
First line of the input contains a single positive integer $T$ ($T$ ≤ 20) denoting the testcase count.
In each test case, a single line of a real number r (0.1 ≤ $r$ ≤ 0.9) will be presented. This is your target resistance.
输出解释
For each testcase, first you have to print Case $i$: in one line, in which $i$ is the case number starting from 1. In the next line you should print two integers n and m (1 ≤ m < n ≤ $10^4$ ) in one line, denoting the number of resistors you initially need and the total number of operations you wish to perform.
In the following $m$ lines, you have to print an operation in one line in the format of
op x y
where op should be 0 if you wish to perform a serial merge and 1 if you wish to perform a parallel merge. x and y are the numbers of the two graphs you wish to merge. Note that all graphs are numbered following the rule described in the statement automatically.
We assume the last graph obtained from your last operation is your final answer.
Do not print extra empty lines in your output.

Note
The solution is not unique. Your answer will be special judged and will be accepted if |$r$ - $your$_$answer$| ≤ $10^{-7}$.
The basic physics laws:

  • Ohm’s law: the current through a conductor between two points is directly proportional to the voltage across the two points.

  • I=$\frac{V}{R}$

  • Kirchhoff ’s law: the

  • $\sum\limits_{k=1}^n$ $I_k$ = 0
    输入样例
    2
    0.5
    0.6666666666666667
    输出样例
    Case 1:
    2 1
    1 0 1
    Case 2:
    6 5
    1 0 1
    1 2 6
    1 3 4 
    1 5 8
    0 7 9
    来自杭电HDUOJ的附加信息
    Recommend chendu

    该题目是Virtual Judge题目,来自 杭电HDUOJ

    源链接: HDU-6561

    最后修改于 2020-10-25T23:32:20+00:00 由爬虫自动更新

    共提交 0

    通过率 --%
    时间上限 内存上限
    8000/5000MS(Java/Others) 262144/262144K(Java/Others)