Thanks to Clive Fraser for this amusingly-informative problem :)
Whisky is matured in casks but every cask, even for the same whisky, gives rise to a distinctly different final result. When whisky is put into bottles for sale it is necessary for the contents of all bottles carrying the same label to contain identical contents. In order to achieve this the contents of different casks are mixed in order to create a large volume of whisky with the same overall characteristics. There is much more to the blending process than this but, for the purpose of this problem, we will concentrate on the process of mixing two different samples of whisky, from different casks.
To keep things simple we will consider only the alcohol content of the whisky. This is one of the items on the
bottle label so this must be the same for all bottles having the same label. The alcohol strength of the whisky
is given by its ABV value which denotes the percentage by volume of the whisky which is alcohol. Normal
bottles have values around 40 but specialist whiskies can have values up to 70 or more.
Suppose that we want to create 500 litres of whisky with a strength of 46 and that we have available 250
litres of whisky of strength 40 and 400 litres of whisky of strength 50. We can create the necessary 500
litres with strength 46 by mixing 200 litres of strength 40 with 300 litres of strength 50. This is
easily demonstrated by the following calculation:
(200*40 + 300*50)/500 = 46
Note that the division by 500 results from the fact that the total volume of whisky in the mixture is now 500
litres. Clearly we did not use all of the whisky from the two available samples but these can always be used in another mixing later.
Next suppose that we want to create 520 litres of whisky with a strength of 65. We have available 250
litres of whisky with strength 70 and 400 litres of whisky with strength 40. Although the total volume of
whisky is greater than the required 520 litres there is no combination of the two whiskies which will
provide the required strength.
You will be given a number of sets of data. Each of these will have a target strength and quantity for the mixture. You will be provided with two different whiskies (along with their strength and volume). You need to determine whether or not it is possible to create the required target (both strength and volume).
Input and Answer
The first line of the problem will be a single integer N denoting the number of test cases. Each of the
following N lines will hold 7 separate integer values. The first of these is the number of the test case.
The next 6 are (in order) target strength, target volume, sample 1 strength, sample 1 volume,
sample 2 strength, sample 2 volume. For each test case you must determine whether or not the target can be
created. Give the numbers of the test cases where the target can be created, separated by spaces, as a single string.
Example:
input:
4
1 46 500 40 250 50 400
2 65 520 70 250 40 400
3 71 721 57 464 71 637
4 49 452 60 373 42 518
answer:
1 4