Jenny's beads problem
I've got a program to make but I have no idea how can I do it (I know theoretically). **Here it goes**:
> Jenny has `n` beads numbered from `1 to n`. Some of them are worth
> more than the others - for each one there is a known price. Jenny
> would like to make a necklace from some of her beads. There are many
> ways of making such a necklace. We can say that two methods are
> different if bead collections used in them are different. To make the
> task easier, Jenny decided to arrange all possibilities of making a
> necklace. Most important criterion is the sum of prices in the
> necklace. The higher the price, the further in arrangement a method is.
> If we have two different ways of making a necklace which has the same
> sum of prices, we compare them according to lexicographical order of
> ascending numbers of beads used.
>
> **For example**, let's consider a situation of 4 beads worth in sequence (according to numeration): 3, 7, 4 and 3 dollars. From these
> beads a necklace can be made in 16 ways. Here you can see an arranged
> list of all possibilities according to Jenny's concept:
> http://i.stack.imgur.com/RmHzy.png
>
> Jenny would like to make a necklace, which is `k`th in the
> arrangement. Help her!
**INPUT**
In the first row of stdin: two total positive numbers `n` and `k` divided by a single space. `n` is the amount of beads while `k` stands for the `k`th way of making a necklace (according to Jenny's method). (for example: 4 16)
In the second row of stdin: series of `n` total positive numbers `a1, a2..., an`
divided by single spaces - price of each bead. (for example: 3 7 4 3)
**OUTPUT**
In the first row of stdout: one total number - the sum of values of beads in the solution found. (for example: 17)
In the second row of stdout: series of id's of beads used in the necklace **ascending** divided by spaces (for example: 1 2 3 4)
> Jenny has `n` beads numbered from `1 to n`. Some of them are worth
> more than the others - for each one there is a known price. Jenny
> would like to make a necklace from some of her beads. There are many
> ways of making such a necklace. We can say that two methods are
> different if bead collections used in them are different. To make the
> task easier, Jenny decided to arrange all possibilities of making a
> necklace. Most important criterion is the sum of prices in the
> necklace. The higher the price, the further in arrangement a method is.
> If we have two different ways of making a necklace which has the same
> sum of prices, we compare them according to lexicographical order of
> ascending numbers of beads used.
>
> **For example**, let's consider a situation of 4 beads worth in sequence (according to numeration): 3, 7, 4 and 3 dollars. From these
> beads a necklace can be made in 16 ways. Here you can see an arranged
> list of all possibilities according to Jenny's concept:
> http://i.stack.imgur.com/RmHzy.png
>
> Jenny would like to make a necklace, which is `k`th in the
> arrangement. Help her!
**INPUT**
In the first row of stdin: two total positive numbers `n` and `k` divided by a single space. `n` is the amount of beads while `k` stands for the `k`th way of making a necklace (according to Jenny's method). (for example: 4 16)
In the second row of stdin: series of `n` total positive numbers `a1, a2..., an`
divided by single spaces - price of each bead. (for example: 3 7 4 3)
**OUTPUT**
In the first row of stdout: one total number - the sum of values of beads in the solution found. (for example: 17)
In the second row of stdout: series of id's of beads used in the necklace **ascending** divided by spaces (for example: 1 2 3 4)
Last edited on
Topic archived. No new replies allowed.