Home STD Contest Notification Clarification Problems Ranklist Status Print Sign Out
1006的数据已经更新,提交已重判,请各位查看。More...

High Priestess

Time Limit: 8000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1    Accepted Submission(s): 0
Special Judge


Problem Description
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
 

Input
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.
 

Output
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
     

    Sample Input
    2 0.5 0.6666666666666667
     

    Sample Output
    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
     

    Source
    642ccpc吉林
     

    Statistic | Submit | Clarifications | Back