prithivMLmods/Coder-Stat

1 2 3<h1><font color="#000000">Problem F: </font>Dr. Podboq or: How We Became Asymmetric</h1>4 5<p>6After long studying how embryos of organisms become asymmetric during7their development, Dr. Podboq, a famous biologist, has reached his new8hypothesis.  Dr. Podboq is now preparing a poster for the coming9academic conference, which shows a tree representing the development10process of an embryo through repeated cell divisions starting from one11cell.  Your job is to write a program that transforms given trees into12forms satisfying some conditions so that it is easier for the audience13to get the idea.14</p>15<!-- end en only -->16 17<!-- begin en only -->18<p>19A tree representing the process of cell divisions has a form described20below.21</p>22<ul>23<li>The starting cell is represented by a circle placed at the top.</li>24<li>Each cell either terminates the division activity or divides into25two cells.  Therefore, from each circle representing a cell, there are26either no branch downward, or two branches down to its27two child cells.</li>28</ul>29<p>30Below is an example of such a tree.31</p>32<!-- end en only -->33 34<p>35<center>36<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-1" border="1" /><br />37<!-- begin en only -->38Figure F-1: A tree representing a process of cell divisions39<!-- end en only -->40</center>41</p>42 43<!-- begin en only -->44<p>45According to Dr. Podboq's hypothesis, we can determine which cells46have stronger or weaker asymmetricity by looking at the structure of47this tree representation.  First, his hypothesis defines "left-right48similarity" of cells as follows:49</p>50<ol>51<li>The left-right similarity of a cell that did not divide further is520.</li> <li>For a cell that did divide further, we collect the partial53trees starting from its child or descendant cells, and count how54many kinds of structures they have.  Then, the left-right similarity of55the cell is defined to be the ratio of the number of structures56that appear both in57the right child side and the left child side.  We regard two trees58have the same structure if we can make them have exactly the same shape by59interchanging two child cells of arbitrary cells.</li>60</ol>61<p>62For example, suppose we have a tree shown below:63</p>64<!-- end en only -->65 66<p>67<center>68<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-2" border="1" /><br />69<!-- begin en only -->70Figure F-2: An example tree71<!-- end en only -->72</center>73</p>74 75<!-- begin en only -->76<p>77The left-right similarity of the cell A is computed as follows.78First, within the descendants of the cell B, which is the left child79cell of A, the following three kinds of structures appear.  Notice that80the rightmost structure appears three times, but when we count the number81of structures, we count it only once.82</p>83<!-- end en only -->84 85<p>86<center>87<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-3" border="1" /><br />88<!-- begin en only -->89Figure F-3: Structures appearing within the descendants of the cell B90<!-- end en only -->91</center>92</p>93 94<!-- begin en only -->95<p>96On the other hand, within the descendants of the cell C, which is the97right child cell of A, the following four kinds of structures appear.98</p>99<!-- end en only -->100 101<p>102<center>103<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-4" border="1" /><br />104<!-- begin en only -->105Figure F-4: Structures appearing within the descendants of the cell C106<!-- end en only -->107</center>108</p>109 110<!-- begin en only -->111<p>112Among them, the first, second, and third ones within the B side are113regarded as the same structure as the second, third, and fourth ones114within the C side, respectively.  Therefore, there are four structures115in total, and three among them are common to the left side and the116right side, which means the left-right similarity of A is 3/4.117</p>118<!-- end en only -->119 120<!-- begin en only -->121<p>122Given the left-right similarity of each cell, Dr. Podboq's hypothesis123says we can determine which of the cells <i>X</i> and <i>Y</i> has124stronger asymmetricity by the following rules.125</p>126<ol>127<li>If <i>X</i> and <i>Y</i> have different left-right similarities, the128one with lower left-right similarity has stronger asymmetricity.129<li>Otherwise, if neither <i>X</i> nor <i>Y</i> has child cells, they130have completely equal asymmetricity.131<li>Otherwise, both <i>X</i> and <i>Y</i> must have two child cells. In this case,132we compare the child cell of <i>X</i> with stronger (or equal)133asymmetricity (than the other child cell of <i>X</i>) and the child134cell of <i>Y</i> with stronger (or equal) asymmetricity (than the other child cell135of <i>Y</i>), and the one having a child with stronger asymmetricity136has stronger asymmetricity.</li>137<li>If we still have a tie, we compare the other child cells of <i>X</i>138and <i>Y</i> with weaker (or equal) asymmetricity, and the one having a child with139stronger asymmetricity has stronger asymmetricity.</li>140<li>If we still have a tie again, <i>X</i> and <i>Y</i> have141completely equal asymmetricity.</li>142</ol>143<p>144When we compare child cells in some rules above, we recursively apply145this rule set.146</p>147<!-- end en only -->148 149<!-- begin en only -->150<p>151Now, your job is to write a program that transforms a given tree152representing a process of cell divisions, by interchanging two child cells153of arbitrary cells, into a tree where the following conditions are154satisfied.155</p>156<ol>157<li>For every cell <i>X</i> which is the starting cell of the given158tree or a left child cell of some parent cell, if <i>X</i> has two159child cells, the one at left has stronger (or equal) asymmetricity than the one160at right.</li>161<li>For every cell <i>X</i> which is a right child cell of some parent162cell, if <i>X</i> has two child cells, the one at right has stronger (or equal)163asymmetricity than the one at left.</li>164</ol>165<p>166In case two child cells have equal asymmetricity, their order is167arbitrary because either order would results in trees of the same shape.168</p>169<!-- end en only -->170 171<!-- begin en only -->172<p>173For example, suppose we are given the tree in Figure F-2.  First we174compare B and C, and because B has lower left-right similarity, which means stronger asymmetricity, we175keep B at left and C at right.  Next, because B is the left child cell176of A, we compare two child cells of B, and the one with stronger177asymmetricity is positioned at left.  On the other hand, because C is178the right child cell of A, we compare two child cells of C, and the one179with stronger asymmetricity is positioned at right.  We examine the180other cells in the same way, and the tree is finally transformed into181the tree shown below.182</p>183<!-- end en only -->184 185<p>186<center>187<img  src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-5" border="1" /><br />188<!-- begin en only -->189Figure F-5: The example tree after the transformation190<!-- end en only -->191</center>192</p>193 194<!-- begin en only -->195<p>196Please be warned that the only operation allowed in the transformation197of a tree is to interchange two child cells of some parent cell.  For198example, you are not allowed to transform the tree in Figure F-2 into the tree199below.200</p>201<!-- end en only -->202 203<p>204<center>205<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_f-6" border="1" /><br />206<!-- begin en only -->207Figure F-6: An example of disallowed transformation208<!-- end en only -->209</center>210</p>211 212 213 214<h3>Input</h3>215 216 217<!-- begin en only -->218<p>219The input consists of <i>n</i> lines (1&le;<i>n</i>&le;100) describing220<i>n</i> trees followed by a line only containing a single zero which221represents the end of the input.  Each tree includes at least 1 and at222most 127 cells.  Below is an example of a tree description.223</p>224<!-- end en only -->225 226<blockquote>227<tt>((x (x x)) x)</tt>228</blockquote>229 230<!-- begin en only -->231<p>232This description represents the tree shown in Figure F-1.  More233formally, the description of a tree is in either of the following two formats.234</p>235<blockquote>236"<tt>(</tt>" &lt;description of a tree starting at the left child&gt; &lt;single space&gt; &lt;description of a tree starting at the right child&gt; ")"237</blockquote>238 239<p>or</p>240 241<blockquote>242"<tt>x</tt>"243</blockquote>244<p>245The former is the description of a tree whose starting cell has two246child cells, and the latter is the description of a tree whose starting247cell has no child cell.248</p>249<!-- end en only -->250 251 252<h3>Output</h3>253 254<!-- begin en only -->255<p>256For each tree given in the input, print a line describing the result257of the tree transformation.  In the output, trees should be described in258the same formats as the input, and the tree descriptions must259appear in the same order as the input.  Each line should have no extra260character other than one tree description.261</p>262<!-- end en only -->263 264 265<h3>Sample Input</h3>266 267<pre>268(((x x) x) ((x x) (x (x x))))269(((x x) (x x)) ((x x) ((x x) (x x))))270(((x x) ((x x) x)) (((x (x x)) x) (x x)))271(((x x) x) ((x x) (((((x x) x) x) x) x)))272(((x x) x) ((x (x x)) (x (x x))))273((((x (x x)) x) (x ((x x) x))) ((x (x x)) (x x)))274((((x x) x) ((x x) (x (x x)))) (((x x) (x x)) ((x x) ((x x) (x x)))))2750276</pre>277 278<h3>Output for the Sample Input</h3>279 280<pre>281((x (x x)) ((x x) ((x x) x)))282(((x x) ((x x) (x x))) ((x x) (x x)))283(((x ((x x) x)) (x x)) ((x x) ((x x) x)))284(((x ((x ((x x) x)) x)) (x x)) ((x x) x))285((x (x x)) ((x (x x)) ((x x) x)))286(((x (x x)) (x x)) ((x ((x x) x)) ((x (x x)) x)))287(((x (x x)) ((x x) ((x x) x))) (((x x) (x x)) (((x x) (x x)) (x x))))288</pre>289 290 291 292 293 294