Charles University in Prague Technical University of Ostrava Slovak University of Technology Pavol Jozef Sˇaf´arik University in Koˇsice
University of Zˇilina Masaryk University Matej Bel University in Bansk´a Bystrica University of West Bohemia
plankton.c, plankton.cpp, Plankton.java, plankton.py
Only few ZOOs can afford to cultivate all types of plankton food they need to feed to various sea vertebrates and invertebrates which live in their voluminous aquariums. Some ZOOs might be from time to time in a short supply of a particular kind of plankton food which is momentarily difficult to obtain. On the other hand, they also might store some reserves of other plankton food types which they do not need to spend immediately and those reserves might be huge.
The director is currently in a pressing need for a particular type of plankton food as the con- struction of a new aquarium with thermal vents is being finished. Fortunately, there are many colleagues in other ZOOs willing to help. They presented the director with various offers. After many lengthy calls, the director has built a comprehensive list of all available offers. Now it is obvious to him that he might need to trade in more steps to obtain the desired food type. In the first trade step, he would exchange the type A, of which there is plenty in his ZOO, for some other type B, which in fact he does not need at all but which can be exchanged with another ZOO for some amount of another type C food, and so on until the final exchange is made which brings in the appropriate food type.
Looking into the list the director is not sure whether a desired chain of exchanges indeed does exist. He calls in his economy vice-director and asks for help. The vice-director studies the list carefully and finally says:
“The amount of food the ZOOs are willing to give in exchange is sometimes bigger and sometimes smaller than the amount of food they would receive and that depends, of course, on the type of the food and generosity of a particular ZOO. I cannot say now if the desired chain of exchanges exists. If it exists, then maybe it would be possible to utilize the offers in such a way that we receive theoretically an unlimited supply of the desired food for only a small investment of the food we have. All these possibilities have to be checked.”
You are presented with the list of offers of all other ZOOs. You have to decide if a sequence of exchanges might be organized in such a way that it brings in a theoretically unlimited supply of the needed type of the plankton food in exchange for a limited volume of the unnecessary food (provided that the sources in the other ZOOs are unlimited). We suppose that any exchange based on a particular trade offer might happen arbitrary number of times.
There are more test cases. Each test case starts with a line containing four positive integers T , F , Fu, Fn. T represents the number of trade offers, F represents the number of types of plankton food. The types of food are labeled 1, 2, ..., F . Fu is the label of the unnecessary food which the organizing ZOO is offering, Fn is the label of the necessary food which it wants to obtain by the trade. Next, there are T lines, each line represents a particular trade offer of a particular ZOO. The offer is expressed by three values Fr , Fg ,U . Fr and Fg are labels of particular food types. The third number, U , is the natural logarithm (the use of logarithms in the ZOO is very popular
because of the large range of sizes of the animals) of the amount of units of plankton food of type Fg which the offering ZOO is willing to give in exchange of receiving 1 unit of plankton food of type Fr . The value of U is a decimal number with at most three digits after the decimal point and with absolute value less than or equal to 1 000. Note that the identification of the offering ZOO has been stripped away, as it is not essential for the solution of the problem. The value of T does not exceed 10 000, the value of F does not exceed 5 000.
The input is terminated by a line with four zeros.
For each test case print on a separate line either “TRUE” or “FALSE”. Print “TRUE” if and only if there is a way to organize the exchanges in such way that an investment of a limited volume of the unnecessary food type can result in theoretically unlimited supply of the necessary food type.
3 3 1 3
1 2 0.001
2 3 -0.002
3 1 0.001
3 3 1 3
1 2 1.5
2 3 0.5
3 1 -1.999
6 5 1 5
1 2 -0.1
2 3 0.1
3 4 0.1
4 2 0.1
2 5 -0.1
1 5 0
0 0 0 0
FALSE TRUE TRUE