NWERC 2005
The 2005 ACM Northwestern European Programming Contest
KTH - Royal Institute of Technology, Stockholm, Sweden
The Problem Set
A Unequalled Consumption
B Declaration of Content
C Laserbox
DBowlstack
E Pesky Heroes
F Reduced ID Numbers
G Tantrix
H Guardian of Decency
I Up the Stairs
Almost blank page
Problem A: Unequalled Consumption
1
Problem A: Unequalled Consumption
The Association of Candy Makers is preparing
to launch a new product. Its idea is old with
a novel twist: it simply sells boxes of candies.
But since people are what they consume and ev-
eryone wants to be unique these days, the ACM
wants every candy box to be unique, in the sense
that no two boxes should contain the same com-
position of candy types.
The ACM is only able to make a small num-
ber n of different types of candy, but while lim-
ited in imagination, it is virtually limitless in re-
sources, so it is able to produce as many as it
wants of each type of candy. Furthermore, the
candy types have different weights (though some may weigh the same), and in order to
simplify pricing matters, the ACM wants all candy boxes to have the same total weight.
With these restrictions, the ACM will only be able to make a limited number of boxes.
For instance, if there are three types of candy, weighing 5, 5 and 10 grams respectively, 4
different boxes can be made with total weight 10 grams (using either two of type 1, or two
of type 2, or one of type 3, or one each of types 1 and 2). The ACM would like to be able
to make at least one box for everyone in the cosmos. So, given queries in the form of the
number of people P in the cosmos, your job is to find the smallest possible total weight w
such that P different boxes containing exactly w grams of candies can be made.
Input
The input consists of several data sets (at most 20). Each data set consists of four lines. The
first line contains an integer 1
≤ n ≤ 5, the number of candy types. The next line contains n
integers w
1
,...,w
n
,where1≤ w
i
≤ 10 is the weight (in grams) of the i:th candy type. The
third line contains an integer 1
≤ q ≤ 10, the number of queries. The last line of a data set
contains q integers P
1
,...,P
q
,where1≤ P
j
≤ 10
15
is the j:th query. Input is terminated by
an incomplete data set where n
= 0, which should not be processed.
Output
For the i:th data set, write a line “Set i”, followed by q lines giving, for each query P
j
,the
minimal possible positive weight W
j
(in grams) of a candy box. If there is no weight W
j
such
that at least P
j
candy boxes can be made, print “no candy for you” for that query. You
may assume that W
j
, if it exists, will be at most 100 · P
j
.
2
Problem A: Unequalled Consumption
Sample input Sample output
3
5510
1
4
4
3142
2
142 700
1
10
1
100
0
Set 1
10
Set 2
23
42
Set 3
no candy for you
Problem B: Declaration of Content
3
Problem B: Declaration of Content
Most food you can buy at your local gro-
cery store has a declaration of content. The
declaration of content lists the ingredients of
the product. It does not necessarily tell you
the exact amount of every ingredient, only
the ordering of the ingredients, from most
common to least common. For some ingre-
dients, an exact percentage might be given,
either required by law or because the pro-
ducer wants you to know how much of the
fine expensive ingredients they have used.
Given a set of different products and their respective declarations of content you should
determine which contain the most or the least of some given ingredients. For simplicity, we
assume in this problem that the percentage of each ingredient always is an integer.
Input
The input consists of several test cases. Each test case consists of two parts.
The first part of a test case begins with an integer P,1
≤ P ≤ 10, the number of different
products in this test case, on a line of its own. Then follows the description of the P products.
Each product description consists of a line giving the name of the product, followed by a line
containing an integer n,1
≤ n ≤ 100, giving the number of ingredients in this product. Then
follow n lines, the i:th of which contains the name of the i:th most common ingredient of the
product. In case of ties, the ingredients will be listed in arbitrary order. Optionally, every
ingredient name can be followed by space, an integer p,0
≤ p ≤ 100 and a percentage sign.
If this is present, it specifies the exact amount of this ingredient in the product. Otherwise,
because all percentages in this problem are integers, the ingredient makes up at least one
percent of the total product.
The second part of a test case begins with an integer Q,1
≤ Q ≤ 100, the number of
queries. Then follow Q lines, each containing a query. A query is of the form “least X”, or
“most X”, where X is the name of an ingredient. In the “most X” case, the ingredient X is
guaranteed to be present in at least one of the products.
A name of a product or an ingredient is a string of alphabetic characters (A-Z and a-z),
digits (0-9) and underscore. Case is significant. No name will be longer than 30 characters.
You may assume that each declaration of content is valid.
The last test case to be processed is followed by a line consisting of the integer 0.
Output
The output consists of one line for every query in the input data. For each query, output
the name of the product containing the most or the least of ingredient X, as indicated by the
query. If there are several possible such products, output all of them, in the same order as the
products were presented in the test case input data. The product names should be separated
by a single space.
