hackercupai/hackercup

1<p>2You know what a finshake is, right? It's just like a handshake. Except performed by fish rather than humans.3</p>4 5<p>6There are <strong>N</strong> pools of water in a row, numbered from 1 to <strong>N</strong> in order. 7Pool <em>i</em>'s water level is at an elevation of <strong>H<sub>i</sub></strong> metres. There are <strong>N</strong> - 1 equally-tall walls, one between each pair of adjacent pools, 8with the top of each wall at an elevation of <strong>W</strong> metres. 9All of the water levels are lower than the tops of the walls (in other words, <strong>H<sub>i</sub></strong> &lt; <strong>W</strong> for each <em>i</em>).10</p>11 12<p>13There are also <strong>M</strong> fish throughout the pools. The <em>i</em>th fish initially lives in pool <strong>P<sub>i</sub></strong>, 14and has a jumping height of <strong>J<sub>i</sub></strong> metres. It can jump over a wall from any given pool <strong>a</strong> to an adjacent pool <strong>b</strong> 15(such that |<strong>a</strong> - <strong>b</strong>| = 1) if and only if <strong>J<sub>i</sub></strong> &gt; <strong>W</strong> - <strong>H<sub>a</sub></strong>. 16Multiple fish may live in the same pool.17</p>18 19<p>20Each of the <strong>M</strong> fish will spend some time jumping over walls amongst the pools, before each choosing a final pool to settle in. 21After all of the fish have settled down, for each unique unordered pair of fish who have ended up in the same pool as one another, they will give each other a finshake. 22Assuming the fish all work together, what's the maximum number of finshakes which can occur once they've all settled down in their chosen pools?23</p>24 25 26<h3>Input</h3>27 28<p>29Input begins with an integer <strong>T</strong>, the number of rows of pools.30For each row of pools, there is first a line containing the space-separated integers <strong>N</strong>, <strong>M</strong>, and <strong>W</strong>.31Then follows a line containing the <strong>N</strong> space-separated integers <strong>H<sub>1</sub></strong> through <strong>H<sub>N</sub></strong>.32Then <strong>M</strong> lines follow, the <em>i</em>th of which contains the space-separated integers <strong>P<sub>i</sub></strong> and <strong>J<sub>i</sub></strong>.33</p>34 35 36<h3>Output</h3>37 38<p>39For the <em>i</em>th row of pools, output a line containing "Case #<em>i</em>: " followed by the maximum number of finshakes which can occur.40</p>41 42 43<h3>Constraints</h3>44 45<p>461 &le; <strong>T</strong> &le; 50 <br />471 &le; <strong>N</strong> &le; 500 <br />481 &le; <strong>M</strong> &le; 50 <br />492 &le; <strong>W</strong> &le; 1,000,000 <br />501 &le; <strong>H<sub>i</sub></strong> &lt; <strong>W</strong> <br />511 &le; <strong>P<sub>i</sub></strong> &le; <strong>N</strong> <br />521 &le; <strong>J<sub>i</sub></strong> &le; 1,000,000 <br />53</p>54 55 56<h3>Explanation of Sample</h3>57 58<p>59In the first case, neither fish has a sufficient jumping height to jump over the wall from its own pool to the other pool. 60As such, each fish must remain isolated in its own pool, resulting in 0 finshakes being exchanged.61</p>62 63<p>64In the second case, the second fish has sufficient jumping strength to go back and forth over the wall. It should choose to settle in the first pool. 65With both fish ending up in the same pool, they'll exchange 1 finshake.66</p>67 68<p>69In the third case, the first fish is unable to leave the first pool. The fourth fish could decide to choose to stay in the first pool as well, and give the first fish a finshake. 70However, it's better for the last 3 fish to all congregate in the second pool instead, as this will result in a total of 3 finshakes being exchanged amongst them.71</p>72