hackercupai/hackercup

1<p>2Fred works the night shift in a refrigerator storage warehouse. It's not very exciting work, but Fred has ways to pass the time when nobody's around. 3For example, lifting fridges turns out to be an amazing bodybuilding method!4</p>5 6<p>7The warehouse consists of <strong>N</strong> sections in a row, numbered from 1 to <strong>N</strong>. 8In each section <em>i</em>, there are initially <strong>F<sub>i</sub></strong> fridges, all arranged in a single stack. 9The sections are intended to be separate from one another, and only accessible from the outside. 10To that end, each pair of adjacent sections are separated by a wall, for a total of <strong>N</strong>-1 walls. 11However, these walls don't stretch all the way to the ceiling, and aren't necessarily all of the same height. 12The wall between sections <em>i</em> and <em>i</em>+1 has a height of <strong>H<sub>i</sub></strong> fridge-heights (Fred has come to measure everything relative to fridge dimensions). 13Fred's favourite pastime involves climbing over these walls to get between the warehouse's sections!14</p>15 16<p>17Fred will begin by entering the warehouse in some section, carrying in some number of new fridges from the outside (yes, he's become strong enough to carry multiple fridges in his arms at once). When he's currently in a certain section <em>s</em> and is carrying <em>f</em> fridges, he may perform any of the following actions:18<p>19 20<ul style="list-style-type:disc; padding-inline-start: 30px;">21<li>Pick up a fridge from section <em>s</em>'s stack of fridges, if it's non-empty. This decreases the number of fridges in that stack by 1, and increases <em>f</em> by 1.</li>22<li>Add a fridge that he's carrying onto section <em>s</em>'s stack of fridges, if he's carrying at least one fridge. 23This decreases <em>f</em> by 1, and increases the number of fridges in that stack by 1. </li>24<li>Climb onto section <em>s</em>'s stack of fridges and jump over a wall into an adjacent section, if the number of fridges in that stack is at least as large as the height of that wall 25(in fridge-heights). This decreases or increases <em>s</em> by 1. </li>26</ul>27 28<p>29Fred's goal is to visit all <strong>N</strong> sections at least once each. 30He just needs to decide which section he should initially enter and how many additional fridges he should bring from the outside. 31He has <strong>M</strong> such possible starting situations in mind, the <em>i</em>th of which involves him beginning in section 32<strong>X<sub>i</sub></strong> while carrying <strong>Y<sub>i</sub></strong> fridges. 33For each hypothetical starting situation, please help Fred determine whether or not he will be able to visit all <strong>N</strong> sections!34</p>35 36 37<h3>Input</h3>38 39<p>40Input begins with an integer <strong>T</strong>, the number of warehouses Fred works at.41<br />For each warehouse, there is first a line containing the space-separated integers <strong>N</strong> and <strong>M</strong>.42<br />Then follows a line with the <strong>N</strong> space-separated integers <strong>F<sub>1</sub></strong> through <strong>F<sub>N</sub></strong>.43<br />Then follows a line with the <strong>N</strong> - 1 space-separated integers <strong>H<sub>1</sub></strong> through <strong>H<sub>N-1</sub></strong>.44<br />Then, <strong>M</strong> lines follow, the <em>i</em>th of which contains the space-separated integers <strong>X<sub>i</sub></strong> and <strong>Y<sub>i</sub></strong>.45</p>46 47 48<h3>Output</h3>49 50<p>51For the <em>i</em>th warehouse, print a line containing "Case #<em>i</em>: " followed by52a string of <strong>M</strong> characters, the <em>i</em>th of which is "Y" if Fred can visit all <strong>N</strong> sections from the <em>i</em>th starting situation, or "N" otherwise.53</p>54 55 56<h3>Constraints</h3>57 58<p>591 &le; <strong>T</strong> &le; 90 <br />602 &le; <strong>N</strong> &le; 8,000 <br />611 &le; <strong>M</strong> &le; 8,000 <br />620 &le; <strong>F<sub>i</sub></strong> &le; 100,000 <br />631 &le; <strong>H<sub>i</sub></strong> &le; 100,000 <br />641 &le; <strong>X<sub>i</sub></strong> &le; <strong>N</strong> <br />650 &le; <strong>Y<sub>i</sub></strong> &le; 1,000,000,000 <br />66</p>67 68<p>69The sum of <strong>N</strong> across all <strong>T</strong> test cases is no greater than 80,000. <br />70The sum of <strong>M</strong> across all <strong>T</strong> test cases is no greater than 80,000.71</p>72 73 74<h3>Explanation of Sample</h3>75 76<p>77In the first case, the warehouse is arranged as follows:78</p>79 80<img src={{PHOTO_ID:668467847037494}} width="100px" />81  82<p>83If Fred begins in section 1 holding 0 fridges, he can't climb over the wall to visit section 2, whereas if he's holding 1 fridge, he can place it in section 1 and then climb over. 84On the other hand, if he begins in section 2, he can climb over the wall to visit section 1 using the existing fridge, regardless of whether he's holding any himself.85</p>86  87<p>88In the second case, consider the first starting situation, in which Fred begins in section 3 holding 4 fridges:89</p>90  91 92<img src={{PHOTO_ID:3188801037832284}} width="200px" />93  94<p>95He could begin by placing 3 of his fridges in section 3, and using them to climb over the wall into section 4 while still holding 1 fridge:96</p>97 98<img src={{PHOTO_ID:268184757597716}} width="200px" />99  100<p>101He could then place his remaining fridge in section 4, climb back to section 3, pick up a fridge there, and climb over to section 2 while holding that 1 fridge:102</p>103  104<img src={{PHOTO_ID:281442036550128}} width="200px" />105  106<p>107Finally, he could place his final fridge in section 2 and climb over to section 1:108</p>109 110<img src={{PHOTO_ID:657561505101033}} width="200px" />111 112