prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem B:</font> Book Replacement</H1>3 4<p>5The deadline of Prof. Hachioji’s assignment is tomorrow. To complete the task, students have6to copy pages of many reference books in the library.7</p>8<p>9All the reference books are in a storeroom and only the librarian is allowed to enter it. To obtain10a copy of a reference book’s page, a student should ask the librarian to make it. The librarian11brings books out of the storeroom and makes page copies according to the requests. The overall12situation is shown in Figure 1.13</p>14<p>15Students queue up in front of the counter. Only a single book can be requested at a time. If a16student has more requests, the student goes to the end of the queue after the request has been17served.18</p>19<p>20In the storeroom, there are m desks <i>D</i><sub>1</sub>, ... , <i>D</i><sub><i>m</i></sub>, and a shelf. They are placed in a line in this21order, from the door to the back of the room. Up to c books can be put on each of the desks. If22a student requests a book, the librarian enters the storeroom and looks for it on <i>D</i><sub>1</sub>, ... , <i>D</i><sub><i>m</i></sub> in23this order, and then on the shelf. After finding the book, the librarian takes it and gives a copy24of a page to the student.25</p>26 27<center>28<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_bookReplacement">29</center>30 31<p>32Then the librarian returns to the storeroom with the requested book, to put it on <i>D</i><sub>1</sub> according to the following procedure.33</p>34 35<ul>36<li>If <i>D</i><sub>1</sub> is not full (in other words, the number of books on <i>D</i><sub>1</sub> &lt; <i>c</i>), the librarian puts the requested book there.</li>37<li>38If <i>D</i><sub>1</sub> is full, the librarian39<ul>40   <li> temporarily puts the requested book on the non-full desk closest to the entrance or,41     in case all the desks are full, on the shelf,</li>42   <li> finds the book on <i>D</i><sub>1</sub> that has not been requested for the longest time (i.e. the least recently used book) and takes it,</li>43   <li> puts it on the non-full desk (except <i>D</i><sub>1</sub> ) closest to the entrance or, in case all the desks except <i>D</i><sub>1</sub> are full, on the shelf,</li>44   <li> takes the requested book from the temporary place,</li>45   <li> and finally puts it on <i>D</i><sub>1</sub> .</li>46</ul>47</ul>48 49<p>50Your task is to write a program which simulates the behaviors of the students and the librarian,51and evaluates the total cost of the overall process. Costs are associated with <i>accessing</i> a desk52or the shelf, that is, putting/taking a book on/from it in the description above. The cost of an53access is <i>i</i> for desk <i>D<sub>i</sub></i> and <i>m</i> + 1 for the shelf. That is, an access to <i>D</i><sub>1</sub>, ... , <i>D<sub>m</sub></i> , and the shelf54costs 1, ... , <i>m</i>, and <i>m</i> + 1, respectively. Costs of other actions are ignored.55</p>56<p>57Initially, no books are put on desks. No new students appear after opening the library.58</p>59 60 61<H2>Input</H2>62 63<p>64The input consists of multiple datasets. The end of the input is indicated by a line containing65three zeros separated by a space. It is not a dataset.66</p>67<p>68The format of each dataset is as follows.69</p>70 71<pre>72      <i>m c n</i>73      <i>k</i><sub>1</sub>74      <i>b</i><sub>11</sub> . . . <i>b</i><sub>1<i>k</i><sub>1</sub></sub>75      .76      .77      .78      <i>k<sub>n</sub></i>79      <i>b</i><sub><i>n</i>1</sub> . . . <i>b<sub>nk<sub>n</sub></sub></i>80</pre>81<p>82Here, all data items are positive integers. <i>m</i> is the number of desks not exceeding 10. <i>c</i> is the number of books allowed to put on a desk, which does not exceed 30. <i>n</i> is the number of83students not exceeding 100. <i>k<sub>i</sub></i> is the number of books requested by the <i>i</i>-th student, which does84not exceed 50. <i>b<sub>ij</sub></i> is the ID number of the book requested by the <i>i</i>-th student on the <i>j</i>-th turn.85No two books have the same ID number. Note that a student may request the same book more86than once. <i>b<sub>ij</sub></i> is less than 100.87</p>88<p>89Here we show you an example of cost calculation for the following dataset.90</p>91 92<pre>933 1 29439560 61 629629770 6098</pre>99 100<p>101In this dataset, there are 3 desks (<i>D</i><sub>1</sub>, <i>D</i><sub>2</sub>, <i>D</i><sub>3</sub> ). At most 1 book can be put on each desk. The102number of students is 2. The first student requests 3 books of which IDs are 60, 61, and 62,103respectively, and the second student 2 books of which IDs are 70 and 60, respectively.104</p>105<p>106The calculation of the cost for this dataset is done as follows. First, for the first request of the107first student, the librarian takes the book 60 from the shelf and puts it on <i>D</i><sub>1</sub> and the first108student goes to the end of the queue, costing 5. Next, for the first request of the second student,109the librarian takes the book 70 from the shelf, puts it on <i>D</i><sub>2</sub>, moves the book 60 from <i>D</i><sub>1</sub> to <i>D</i><sub>3</sub> ,110and finally moves the book 70 from <i>D</i><sub>2</sub> to <i>D</i><sub>1</sub> , costing 13. Similarly, the cost for the books 61,11160, and 62, are calculated as 14, 12, 14, respectively. Therefore, the total cost is 58.112 113 114 115<H2>Output</H2>116 117<p>118For each dataset, output the total cost of processing all the requests, in a separate line.119</p>120 121<H2>Sample Input</H2>122<pre>1232 1 11241125501262 1 21271128501291130601312 1 2132213360 611341135701364 2 3137313860 61 62139114070141214280 811433 1 2144314560 61 62146214770 601481 2 5149215087 95151315296 71 35153215468 215531563 18 93157215857 21592 2 116051611 2 1 3 11620 0 0163</pre>164 165<H2>Output for the Sample Input</H2>166<pre>1674168161692817068171581729817323174</pre>175 176 177 178 179