prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem E: </font>Driving an Icosahedral Rover</H1>3 4<p>5After decades of fruitless efforts, one of the expedition teams of ITO (Intersolar Tourism Organization) finally found a planet that would surely provide one of the best tourist attractions6within a ten light-year radius from our solar system. The most attractive feature of the planet,7besides its comfortable gravity and calm weather, is the area called <i>Mare Triangularis</i>. Despite8the name, the area is not covered with water but is a great plane. Its unique feature is that it is9divided into equilateral triangular sections of the same size, called <i>trigons</i>. The <i>trigons</i> provide10a unique impressive landscape, a must for tourism. It is no wonder the board of ITO decided11to invest a vast amount on the planet.12</p>13 14<p>15Despite the expected secrecy of the staff, the Society of Astrogeology caught this information16in no time, as always. They immediately sent their president's letter to the Institute of Science17and Education of the Commonwealth Galactica claiming that authoritative academic inspections18were to be completed before any commercial exploitation might damage the nature.19</p>20 21<p>22Fortunately, astrogeologists do not plan to practice all the possible inspections on all of the23<i>trigons</i>; there are far too many of them. Inspections are planned only on some characteristic24<i>trigons</i> and, for each of them, in one of twenty different scientific aspects.25</p>26 27<p>28To accelerate building this new tourist resort, ITO's construction machinery team has already succeeded in putting their brand-new29invention in practical use. It is a rover vehicle of the shape of an <i>icosahedron</i>, a regular polyhedron with twenty faces of equilateral triangles. 30The machine is customized31so that each of the twenty faces exactly fits each of the <i>trigons</i>. 32Controlling the high-tech <i>gyromotor</i> installed inside its body, the rover can roll onto one of the three <i>trigons</i> neighboring the one its bottom is33on.34</p>35 36<center>37<table width="480">38<tr>39<td>40<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1319_1">41</td>42<tr>43<td>44<b>Figure E.1: The Rover on Mare Triangularis</b>45</td>46</tr>47</table>48</center>49 50 51<p>52Each of the twenty faces has its own function. The set of equipments installed on the bottom53face touching the ground can be applied to the <i>trigon</i> it is on. Of course, the rover was meant to accelerate construction of the luxury hotels to host rich interstellar travelers, but, changing54the installed equipment sets, it can also be used to accelerate academic inspections.55</p>56 57<p>58You are the driver of this rover and are asked to move the vehicle onto the <i>trigon</i> specified by59the leader of the scientific commission with the smallest possible steps. What makes your task60more difficult is that the designated face installed with the appropriate set of equipments has to61be the bottom. The direction of the rover does not matter.62</p>63 64<center>65<table width="480">66<tr>67<td align="justify">68<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1319_2">69</td>70<td>71<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_1319_3">72</td>73<tr>74<td>75<b>Figure E.2:The Coordinate System </b>76</td>77<td align="center">78<b>79Figure E.3: Face Numbering</b>80</td>81</tr>82</table>83</center>84	85 86<p>87The <i>trigons</i> of <i>Mare Triangularis</i> are given two-dimensional coordinates as shown in Figure E.2.88Like maps used for the Earth, the <i>x</i> axis is from the west to the east, and the <i>y</i> axis is from the89south to the north. Note that all the trigons with its coordinates (<i>x , y</i>) has neighboring trigons90with coordinates (<i>x</i> - 1 , <i>y</i>) and (<i>x</i> + 1 , <i>y</i>). In addition to these, when <i>x</i> + <i>y</i> is even, it has a91neighbor (<i>x</i> , <i>y</i> + 1); otherwise, that is, when <i>x</i> + <i>y</i> is odd, it has a neighbor (<i>x , y</i> - 1).92</p>93 94<p>95Figure E.3 shows a development of the skin of the rover. The top face of the development96makes the exterior. That is, if the numbers on faces of the development were actually marked97on the faces of the rover, they should been readable from its outside. These numbers are used98to identify the faces.99</p>100 101<p>102When you start the rover, it is on the <i>trigon</i> (0,0) and the face 0 is touching the ground. The103rover is placed so that rolling towards north onto the <i>trigon</i> (0,1) makes the face numbered 5104to be at the bottom.105</p>106 107<p>108As your first step, you can choose one of the three adjacent <i>trigons</i>, namely those with coordinates (-1,0), (1,0), 109and (0,1), to visit. The bottom will be the face numbered 4, 1, and 5,110respectively. If you choose to go to (1,0) in the first rolling step, the second step can bring111the rover to either of (0,0), (2,0), or (1,-1). The bottom face will be either of 0, 6, or 2,112correspondingly. The rover may visit any of the <i>trigons</i> twice or more, including the start and the goal <i>trigons</i>, when appropriate.113</p>114 115<p>116The theoretical design section of ITO showed that the rover can reach any goal <i>trigon</i> on the117specified bottom face within a finite number of steps.118</p>119 120<H2>Input</H2>121 122<p>123The input consists of a number of datasets. The number of datasets does not exceed 50.124</p>125 126<p>127Each of the datasets has three integers <i>x</i>, <i>y</i>, and <i>n</i> in one line, separated by a space. Here, (x,y)128specifies the coordinates of the <i>trigon</i> to which you have to move the rover, and <i>n</i> specifies the129face that should be at the bottom.130</p>131 132<p>133The end of the input is indicated by a line containing three zeros.134</p>135 136<H2>Output</H2>137 138<p>139The output for each dataset should be a line containing a single integer that gives the minimum140number of steps required to set the rover on the specified <i>trigon</i> with the specified face touching141the ground. No other characters should appear in the output.142</p>143 144<p>145You can assume that the maximum number of required steps does not exceed 100. <i>Mare Triangularis</i>146 is broad enough so that any of its edges cannot be reached within that number of147steps.148</p>149 150<H2>Sample Input</H2>151<pre>1520 0 11533 5 2154-4 1 315513 -13 2156-32 15 9157-50 50 01580 0 0159</pre>160 161<H2>Output for the Sample Input</H2>162<pre>16361641016591663016747168100169</pre>