Statistics

Problem Statement for "CreateMixture"

Problem Statement

You have an unlimited supply of two substances: substance 0 is distilled water and substance 1 is pure chemical X.


You cannot manipulate chemicals directly, you can only use a mixing machine. The mixing machine has ten inputs and one output. Each time you use it, you can use as many inputs as you want (between 1 and 10, inclusive). The machine will take the substances it gets as inputs and produce an output that is their uniform mixture. For example, if you use three inputs, the output chemical will contain one third of each of the input chemicals.

The mixing machine always produces a large amount of the new substance, so you can freely use each new substance as inputs for mixing in the future. The substances you'll produce will be numbered 2, 3, 4, ...


You want to have a diluted sample of chemical X. Your sample should contain concentration promille of chemical X. In other words, out of 1000 parts of this chemical, exactly concentration parts should be chemical X and the rest should be distilled water.

Find one way of producing the desired concentration using the mixing machine. The number N of new substances you'll produce must be at most ten. After the last use of the mixing machine any one of the substances you have must have the correct concentration.


Return a int[] with 10*N elements: 10 for each use of the mixing machine. More precisely, for each use of the mixing machine output 10 numbers that describe the substances you use as the inputs for the machine. Use the value -1 for an input that remains unused. See the examples for a detailed explanation.

Definition

Class:
CreateMixture
Method:
mix
Parameters:
int
Returns:
int[]
Method signature:
int[] mix(int concentration)
(be sure your method is public)

Notes

  • A valid solution exists for each input that matches the constraints.
  • Any valid solution will be accepted.
  • You do not have to minimize the number of times the machine is used, but remember that you may only use the machine at most ten times.

Constraints

  • concentration will be between 0 and 1000, inclusive.

Examples

  1. 500

    Returns: {0, 1, -1, 1, -1, 0, -1, -1, -1, -1 }

    We want a substance that's exactly half water and half chemical X. The example output above produces it by mixing four inputs: two containing water and two containing chemical X. There are many other valid solutions. For example, {0, 1, -1, -1, -1, -1, -1, -1, -1, -1} is one way to describe mixing one input with water and one input with chemical X.

  2. 250

    Returns: {0, 1, -1, 1, -1, 0, -1, -1, -1, -1, 2, 0, -1, -1, -1, -1, -1, -1, -1, -1 }

    Our solution first produces the mixture from the previous example and then mixes it again with water. Here is the example return value separated into individual steps: we produce substance 2: {0, 1, -1, 1, -1, 0, -1, -1, -1, -1} we produce substance 3: {2, 0, -1, -1, -1, -1, -1, -1, -1, -1}

  3. 0

    Returns: { }

    We want water. We already have water, so we don't have to do anything. Again, there are also other valid solutions. For example, {0, -1, -1, -1, -1, -1, -1, -1, -1, -1} and {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} are both correct outputs that produce substance 2 that is also pure water. The output {0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 2, 2, 2, 0, 0, 0, 1, 2, 1, 0} is also valid, even though it produces two new substances with non-zero concentrations of chemical X. In the end you have four substances and one of them (substance 0) has the desired concentration, so everything is OK.

  4. 400

    Returns: {0, 1, -1, 1, -1, 0, -1, -1, -1, -1, 0, 0, 1, 2, 2, -1, -1, -1, -1, -1 }

    Our example output shows that it's not necessary to minimize the number of times you use the machine. Even though it's possible to produce this desired mixture in one use of the machine, we do it in two. Here is the example return value separated into individual steps: we produce substance 2 which has 500 parts of chemical X per 1000: {0, 1, -1, 1, -1, 0, -1, -1, -1, -1} we produce substance 3: {0, 0, 1, 2, 2, -1, -1, -1, -1, -1}

  5. 2

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 3, -1, -1, -1, -1, -1 }

  6. 1

    Returns: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  7. 9

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  8. 10

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  9. 100

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  10. 999

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  11. 998

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  12. 997

    Returns: {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  13. 939

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  14. 910

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  15. 870

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 3 }

  16. 333

    Returns: {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 3 }

  17. 499

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 3 }

  18. 450

    Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 3 }

  19. 123

    Returns: {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  20. 715

    Returns: {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 3 }

  21. 887

    Returns: {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 3 }

  22. 749

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 3 }

  23. 987

    Returns: {1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3 }

  24. 62

    Returns: {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

  25. 729

    Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 3 }

  26. 1000

    Returns: { }

  27. 4

    Returns: {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: