-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathindex.html
102 lines (93 loc) · 7.53 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>DSA2: PA3: Weighing Children</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
</head>
<body>
<header id="title-block-header">
<h1 class="title">DSA2: PA3: Weighing Children</h1>
</header>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/e/e0/HK_%E8%A5%BF%E7%87%9F%E7%9B%A4_Sai_Ying_Pun_Dr_doctor_clinic_shop_January_2021_SS2_03.jpg/1024px-HK_%E8%A5%BF%E7%87%9F%E7%9B%A4_Sai_Ying_Pun_Dr_doctor_clinic_shop_January_2021_SS2_03.jpg" style="width:33%;float:right;margin-left:20px;border-radius:10px" /></p>
<p>Professor Pettit is bringing his children to their annual pediatrician’s appointment. As always, they are weighted and measured to check their growth. Normally a scale like the one to the right is used – a weigh-beam scale, it’s called. However, the scale at Pediatrics Incorporated is broken, and they have to use a different means to weigh each of his children.</p>
<p>The only tools available are an old-fashioned <a href="https://commons.wikimedia.org/wiki/File:Balance_scale_IMGP9722.jpg">balance scale</a> and a number of boxes of standard kilogram weights, which are all in powers of 10. We’ll assume that Professor Pettit knows the weight of each child, and the physician just has to go through the motions to verify it.</p>
<p>Thus, the pediatrician needs to weigh a child weighing <span class="math inline"><em>m</em></span> kilograms by balancing the child on a balance scale with weights of standard masses on the other side that are all powers of 10 (1 kg weights, 10 kg weights, 100 kg weights, etc.). Thus, the pediatrician has to choose a set of standard weights with total sum equal to <span class="math inline"><em>m</em></span> kg.</p>
<p>Standard weights come in <span class="math inline"><em>b</em></span> sealed boxes. A given box contains some number of identical mass weights of <span class="math inline">10<sup><em>x</em></sup></span> kg. The pediatrician wants to open the minimal number of boxes to take a set of weights with the sum of their weights of <span class="math inline"><em>m</em></span> kg.</p>
<p>The goal is to minimize the number of (sealed) boxes that need to be opened.</p>
<p>Consider the following example, where the pediatrician wants to measure out 176 kg (no, none of Professor Pettit’s children weigh 176 kg, which is 387 lbs). There are five boxes of weights available:</p>
<p><br clear='all'></p>
<p><img src="pa3.svg" /></p>
<p>There are a few possible solutions. In both solutions discussed here, the box of 100 kg weights and the box of 1 kg weights have to be opened. In the first solution, the box of 8 x 10 kg weights is opened, leading to a result of 3 boxes (box numbers 1, 3, and 5). The second solution is to open both the 5 x 10 kg weights box and the 3 x 10 kg weights box, leading to 4 boxes being opened. (There are technically other solutions where you open the 8 x 10 kg box and one or both of the others, but we’ll ignore those). The first solution is the optimal one, as it opens the fewest number of boxes. The greyed boxes are the ones that have to be opened, and the greyed weights are the ones that sum to 176 kg.</p>
<p>Note: you may not use a weight of a given power of 10 if there is a zero value in that digit’s position. For example, if the weight is 201 kg, you cannot use any 10 kg weights, since there is a 0 digit in the 10’s place. (The reason is that otherwise this becomes a dynamic programming problem without a greedy solution).</p>
<h3 id="input">Input</h3>
<p>The first line of the input contains <span class="math inline">1 ≤ <em>c</em> ≤ 10<sup>3</sup></span>, the number of test cases.</p>
<p>The first line of each test case contains two positive integers: <span class="math inline">1 ≤ <em>m</em> ≤ 10<sup>18</sup></span>, the number of kg to measure out, and <span class="math inline">1 ≤ <em>b</em> ≤ 10<sup>5</sup></span>, the number of sealed boxes. The next <span class="math inline"><em>b</em></span> lines contain pairs of positive integers <span class="math inline">0 ≤ <em>k</em><sub><em>i</em></sub> ≤ 18</span>, the weight of the masses in that box as an exponent of 10, and <span class="math inline"><em>q</em><sub><em>i</em></sub></span>, the number of such weights in the box. Note that <span class="math inline">1 ≤ <em>q</em><sub><em>i</em></sub> ⋅ 10<sup><em>k</em><sub><em>i</em></sub></sup> ≤ 10<sup>18</sup></span>. The boxes may be listed in any order. Not all exponent values of 10 may be present.</p>
<h3 id="output">Output</h3>
<p>On the first line output the minimal number of boxes that should be opened. On the second line output the numbers of these boxes in <em>ascending sorted</em> order. Boxes are numbered in the order they appear in the input file starting from 1 (not 0!). If there are multiple possible optimal solutions, any one will suffice.</p>
<p>If it is impossible to measure exactly <span class="math inline"><em>m</em></span> kg with the provided boxes of weights, output a single line with -1.</p>
<h3 id="sample-input">Sample input</h3>
<p>The first test case corresponds to the diagram above. The blank lines are only present to separate test cases for easy viewing; they will not be present in the actual input, and are not present in the <a href="sample.in">sample.in</a> file.</p>
<pre><code>5
176 5
2 4
1 5
1 8
1 3
0 25
40 3
2 3
1 6
0 30
5550 3
3 5
2 5
1 99999
5500 3
3 5
2 5
1 99999
87 1
1 9</code></pre>
<p>Note that the third and fourth test cases are rather tricky, so focus on getting the others to work first.</p>
<p>Your program will be run as follows (if in Python):</p>
<pre><code>$ python pa3.py < sample.in</code></pre>
<p>Or, if Java:</p>
<pre><code>$ java PA3 < sample.in</code></pre>
<p>The <code><</code> will provide the contents of the <a href="sample.in">sample.in</a> file as standard input to your program.</p>
<h3 id="sample-output">Sample output</h3>
<p>There should NOT be blank lines between test cases – that is only to help illustrate which values are the output for which test cases. The blank lines are not present in the <a href="sample.out">sample.out</a> file.</p>
<pre><code>3
1 3 5
1
2
3
1 2 3
2
1 2
-1</code></pre>
<h3 id="requirements">Requirements</h3>
<p>This needs to be a greedy solution. Brute force solutions will time out with the test cases we are going to provide.</p>
<p>There is no skeleton code being provided for this (or future) programming assignments. You can look at <a href="../pa2/index.html">PA2</a> for how to read in the input from standard input (but note that the input for this assignment is quite different than for PA2).</p>
<p>Your source code file must be named either <code>pa3.py</code> or <code>PA3.java</code>.</p>
</body>
</html>