Krdytkyu

I needed an advise on implementing and solving one problem and the others like. I came across two sentences that I think will be helpful. Those are the Chinese remainder theorem and the Diofantic equation, but I do not know exactly how do I apply them to the problem.

Let me introduce this problem f.e. on the sewer pipe, I will try to describe it as a verbal task:

We need to design a sewer pipeline with an exact length of 127 m. We have tubes from 3 different suppliers. Each supplier produces tubes of different fixed lengths that can not be shortened or extended in any way:

first supplier: 12 m

second supplier: 8 m

third supplier: 10 m

At the beginning of the pipeline and at the end of the pipeline there must be bridging pipes having a length of 3 m. Between each and every tube must also be a bridging pipe.

To illustrate this, we'll show the lengths as variables:

(first supplier) X = 12 m

(second supplier) Y = 8 m

(third supplier) Z = 10 m

(bridging pipe) A = 3 m

Therefore, the scheme would be something like this:

A Y A Y A Y A Y A Z A X A X A

We ask how many tubes do we need to order from every supplier and how many solutions there are? Consider these solutions as a number of different admissible orders (one solution may look like f.e from the first sup. we'll order 5, from the second 3 and from the third 7). The bridging pipes are always sufficient and there is no need to order them in any ocasion.

How do you solve this problem? What algorithm can you use to simply achieve the expected results in similar tasks? I recall that the solution that I do not want is the gradual testing and gradual addition, those are naive solutions, I'm looking for an effective algorithm using Chinese remainder theorem or Diophantine equation.

Thanks.