Untitled
unknown
plain_text
a year ago
15 kB
7
Indexable
Never
Visit departments
Jang keeps visiting and helping a number of departments right after he comes to work.
There is a rule in his movement. He stays at a department exactly for 10 minutes.
You are given a probability graph of their movements. Fig. 1 is an example graph.
/// Fig 1
Jang stays at dept. 1 for 10 minutes; then he moves to dept. 2 with a probability of 0.3 (then stays there for 10 minutes) or moves to dept. 3 with a probability of 0.7 (then stays there for 10 minutes). We do not consider the time for moving between departments.
There may be more than one outgoing arrow from a department; the sum of the chances of outgoing arrows from a department should be always 1.
The first department which he visit is always dept. 1.
Given a probability graph and a time T(in minutes), generate a program that finds the department at which Jang stays with the highest chance at time T.
In addition you have to report the corresponding probability.
In the Fig. 1 above, the department with the highest chance at time 10 is dept. 3 and the chance is 0.7. At time 9, Jang does not start moving; so he is at dept. 1 with a probability of 1.
Look at the situation at time 20. The chance of being at dept. 1 or dept. 2 is 0. He leaves dept. 1 exactly at time 10, and if he moves to dept. 2 then he leaves dept. 2 exactly at time 20.
The chance of being at dept. 4 at time 20 is 0.3*1.0+0.7*0.8=0.86.
When he arrives at a department without any outgoing arrow, the department becomes the last one that he finally visits; he stays at the department for 10 minutes and leaves work.
With the graph of Fig. 2, Jang is not in work at time 50; in case of Fig. 1, he may stay at work forever if he keeps staying at the same department with a loop probability, e.g, departments 3, 4, or 6
In addition, there is another person, Kang, who moves in the same way as Jang.
Jang always comes to work at time 0, but Kang comes at another time later than time 0. You also have to report the same type of contents for Kang.
If Kang’s arrival time is 4, answers related to him is computed exactly the same principle as Jang’s except he starts working 4 minutes later than Jang; in this case with Fig. 2, Kang stays at dept. 1 from time 4 to time 13 while Jang stays at dept. 1 from time 0 to time 9.
[Input]
10 test cases are given. Each case is given in two lines. Thus the input needs totally 20 lines.
For each case, the first line provides N (the number of departments), E (the number of arrows), K (Kang’s arrival time), and T (the time in minutes).
1<=N<=100. 1<=E<=200. 1<=K<=1000. 0<=T<=1000. K<=T.
The next line enumerates E arrows. Each arrow is denoted by “source-dept destination-dept probability”. The index for source dept. or destination dept. is an integer in 1 through 100, inclusive.
The time integer K and T are in minutes. For example, if the time T is 8, you have to determine the departments at which Jang and Kang, respectively, stay with the highest probabilities at time 8. The elements in the same line are separated by a space. There is no special order in which the arrows are enumerated.
[Output]
You write the 10 answers in 10 lines.
Each line starts with “#x” (Here, x means the case index.), puts a space, and writes the answer.
The answer consists of the department index with the highest chance followed by the corresponding probability. The dept. index is an integer and the probability is a real number, separated by a space.
If there is more than one department with the highest chance, you write the dept. of the lowest index.
If Jang is not at any department at the specified time, you write just “0 0.000000”. The probability is a real number in 0 through 1, inclusive; it should be accurate to six decimal places.
Another set of a department and the corresponding probability has to be provided for Kang. Thus the answer consists of four numbers in total.
Input
6 7 100 100
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 7 1 23
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 10 8 40
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
6 10 10 10
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
6 10 9 20
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
Output
#1 0 0.000000 1 1.000000
#2 4 0.790000 4 0.790000
#3 6 0.774000 5 0.774000
#4 3 0.700000 1 1.000000
#5 4 0.860000 3 0.700000
*** test case
10 10 0 9
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 1 1
20 20 130 709
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 1 1
10 18 0 100
1 1 0.33 1 2 0.67 2 2 0.82 2 3 0.18 3 3 0.52 3 4 0.48 4 4 0.83 4 5 0.17 5 5 0.0 5 6 1.0 6 6 0.15 6 7 0.85 7 7 0.4 7 8 0.6 8 8 0.03 8 9 0.97 9 9 0.76 9 10 0.24
10 19 249 1000
1 1 0.81 1 2 0.19 2 2 0.96 2 3 0.04 3 3 0.32 3 4 0.68 4 4 0.61 4 5 0.39 5 5 0.72 5 6 0.28 6 6 0.41 6 7 0.59 7 7 0.51 7 8 0.49 8 8 0.82 8 9 0.18 9 9 0.77 9 10 0.23 10 10 1
30 58 999 1000
8 8 0.14 21 21 0.74 2 2 0.58 1 2 0.26 3 4 0.02 12 13 0.43 6 7 0.52 16 17 0.85 20 20 0.87 25 25 0.36 2 3 0.42 26 27 0.73 20 21 0.13 4 5 0.48 12 12 0.57 9 10 0.81 6 6 0.48 1 1 0.74 3 3 0.98 28 28 0.69 23 23 0.05 10 11 0.86 10 10 0.14 25 26 0.64 21 22 0.26 5 5 0.37 28 29 0.31 17 18 0.28 11 11 0.95 15 15 0.48 26 26 0.27 17 17 0.72 18 18 0.89 11 12 0.05 13 14 0.8 9 9 0.19 8 9 0.86 19 20 0.97 15 16 0.52 24 24 0.15 13 13 0.2 29 30 0.25 22 22 0.82 18 19 0.11 27 27 0.42 16 16 0.15 4 4 0.52 27 28 0.58 22 23 0.18 29 29 0.75 19 19 0.03 7 7 0.81 24 25 0.85 14 15 0.8 23 24 0.95 7 8 0.19 5 6 0.63 14 14 0.2
50 99 741 1000
1 2 0.34 20 21 0.3 39 40 0.35 25 25 0.13 40 41 0.28 43 43 0.43 40 40 0.72 35 36 0.43 36 36 0.0 34 35 0.07 13 14 0.05 19 20 0.95 19 19 0.05 47 47 0.89 30 31 0.18 12 13 1.0 25 26 0.87 7 8 0.05 48 48 0.24 7 7 0.95 5 5 0.48 49 50 0.43 3 3 0.37 2 3 0.47 34 34 0.93 45 46 0.25 26 27 0.27 38 38 0.79 47 48 0.11 32 33 0.87 8 8 0.41 43 44 0.57 33 34 0.94 12 12 0.0 13 13 0.95 11 11 0.63 46 47 0.07 4 5 0.56 6 7 0.88 20 20 0.7 44 44 0.13 21 21 0.79 24 25 0.61 37 37 0.1 42 42 0.17 15 15 0.97 38 39 0.21 48 49 0.76 14 15 0.29 8 9 0.59 28 28 0.85 41 42 0.41 4 4 0.44 32 32 0.13 27 28 0.65 27 27 0.35 17 18 0.52 46 46 0.93 16 16 0.62 18 19 0.06 5 6 0.52 17 17 0.48 24 24 0.39 23 24 0.6 6 6 0.12 9 10 0.54 10 11 0.8 31 31 0.01 22 22 0.07 14 14 0.71 16 17 0.38 33 33 0.06 35 35 0.57 49 49 0.57 30 30 0.82 36 37 1.0 9 9 0.46 21 22 0.21 26 26 0.73 50 50 1 44 45 0.87 28 29 0.15 45 45 0.75 2 2 0.53 31 32 0.99 29 30 0.45 29 29 0.55 1 1 0.66 15 16 0.03 37 38 0.9 42 43 0.83 41 41 0.59 18 18 0.94 22 23 0.93 3 4 0.63 23 23 0.4 10 10 0.2 39 39 0.65 11 12 0.37
10 100 13 1000
1 1 0.07 1 2 0.13 1 3 0.1 1 4 0.12 1 5 0.08 1 6 0.1 1 7 0.11 1 8 0.11 1 9 0.05 1 10 0.13 2 1 0.08 2 2 0.11 2 3 0.09 2 4 0.13 2 5 0.08 2 6 0.12 2 7 0.09 2 8 0.11 2 9 0.11 2 10 0.08 3 1 0.07 3 2 0.11 3 3 0.15 3 4 0.07 3 5 0.1 3 6 0.11 3 7 0.08 3 8 0.13 3 9 0.08 3 10 0.1 4 1 0.1 4 2 0.18 4 3 0.06 4 4 0.11 4 5 0.09 4 6 0.11 4 7 0.06 4 8 0.1 4 9 0.09 4 10 0.1 5 1 0.09 5 2 0.13 5 3 0.13 5 4 0.09 5 5 0.11 5 6 0.07 5 7 0.08 5 8 0.05 5 9 0.12 5 10 0.13 6 1 0.13 6 2 0.06 6 3 0.07 6 4 0.14 6 5 0.08 6 6 0.15 6 7 0.13 6 8 0.1 6 9 0.05 6 10 0.09 7 1 0.11 7 2 0.14 7 3 0.08 7 4 0.09 7 5 0.06 7 6 0.13 7 7 0.1 7 8 0.11 7 9 0.1 7 10 0.08 8 1 0.06 8 2 0.08 8 3 0.04 8 4 0.12 8 5 0.12 8 6 0.1 8 7 0.12 8 8 0.1 8 9 0.06 8 10 0.2 9 1 0.15 9 2 0.11 9 3 0.09 9 4 0.14 9 5 0.03 9 6 0.06 9 7 0.08 9 8 0.1 9 9 0.12 9 10 0.12 10 1 0.08 10 2 0.03 10 3 0.07 10 4 0.16 10 5 0.1 10 6 0.13 10 7 0.15 10 8 0.08 10 9 0.07 10 10 0.13
10 100 242 1000
7 7 0.08 2 8 0.15 10 4 0.08 8 4 0.18 5 1 0.04 6 2 0.13 10 3 0.09 7 2 0.07 10 5 0.06 8 7 0.11 10 2 0.1 7 8 0.13 3 7 0.1 5 10 0.07 4 2 0.04 8 3 0.08 4 5 0.1 2 2 0.07 4 6 0.12 2 10 0.06 6 7 0.06 4 1 0.16 6 8 0.11 4 8 0.14 10 6 0.16 3 4 0.12 3 8 0.09 1 6 0.1 6 3 0.08 9 10 0.16 5 8 0.15 9 7 0.1 4 9 0.09 6 6 0.13 1 5 0.15 3 2 0.09 9 8 0.11 1 2 0.08 8 1 0.11 5 2 0.07 4 7 0.06 1 1 0.08 3 10 0.11 4 10 0.09 3 5 0.09 2 5 0.08 8 9 0.09 9 3 0.08 3 6 0.1 7 3 0.09 1 10 0.1 5 7 0.14 6 5 0.17 10 9 0.03 4 4 0.13 5 4 0.1 2 4 0.07 7 6 0.13 9 4 0.08 7 1 0.04 10 1 0.11 8 10 0.04 5 6 0.11 4 3 0.07 8 6 0.09 7 4 0.07 2 7 0.13 1 7 0.12 2 1 0.15 2 3 0.1 1 4 0.06 9 9 0.12 7 9 0.08 9 1 0.09 6 1 0.07 2 6 0.08 8 5 0.12 5 5 0.15 6 9 0.07 9 6 0.09 10 10 0.13 8 2 0.12 7 10 0.14 3 3 0.08 9 2 0.07 5 3 0.09 8 8 0.06 5 9 0.08 2 9 0.11 1 3 0.1 10 7 0.13 9 5 0.1 10 8 0.11 6 4 0.09 3 9 0.14 1 9 0.12 7 5 0.17 3 1 0.08 1 8 0.09 6 10 0.09
100 200 498 1000
58 57 0.25 86 85 0.77 93 92 0.71 71 72 0.64 68 67 0.16 95 94 0.34 45 44 0.97 92 91 0.64 89 90 0.28 11 12 0.62 37 36 0.36 24 23 0.69 65 66 0.52 13 12 0.47 20 21 0.53 46 47 0.15 19 18 0.2 24 25 0.31 41 40 0.51 79 80 0.47 17 16 0.76 44 43 0.2 69 68 0.64 9 8 0.31 22 23 0.86 91 90 0.32 35 34 0.95 78 79 0.91 64 63 0.98 42 43 0.52 81 80 0.32 39 38 0.46 85 86 0.02 7 6 0.7 29 28 0.37 49 48 0.33 20 19 0.47 2 3 0.53 3 4 0.75 100 99 0.08 26 25 0.47 88 87 0.56 53 54 0.55 98 99 0.01 74 73 0.65 68 69 0.84 23 22 0.59 81 82 0.68 28 27 0.26 54 53 0.73 62 63 0.2 9 10 0.69 76 77 0.18 83 84 0.35 72 73 0.21 25 24 0.83 42 41 0.48 74 75 0.35 61 62 0.84 26 27 0.53 75 76 0.86 84 85 0.57 71 70 0.36 66 67 0.86 75 74 0.14 82 83 0.71 63 64 0.63 59 58 0.78 83 82 0.65 2 1 0.47 40 41 0.96 23 24 0.41 62 61 0.8 78 77 0.09 30 31 0.51 55 56 0.62 29 30 0.63 34 33 0.54 87 88 0.27 25 26 0.17 3 2 0.25 69 70 0.36 52 51 0.21 88 89 0.44 51 50 0.11 63 62 0.37 50 49 0.62 31 30 0.9 8 7 0.56 21 20 0.67 77 76 0.52 41 42 0.49 46 45 0.85 37 38 0.64 32 33 0.22 27 26 0.75 50 51 0.38 60 61 0.18 4 5 0.07 18 17 0.07 79 78 0.53 55 54 0.38 94 93 0.93 60 59 0.82 17 18 0.24 97 98 0.91 61 60 0.16 97 96 0.09 96 95 0.8 73 72 0.06 85 84 0.98 16 15 0.31 48 49 0.45 43 44 1.0 100 1 0.92 90 89 0.95 54 55 0.27 39 40 0.54 84 83 0.43 47 46 0.53 32 31 0.78 48 47 0.55 19 20 0.8 66 65 0.14 1 100 0.03 27 28 0.25 47 48 0.47 96 97 0.2 21 22 0.33 80 79 0.49 80 81 0.51 30 29 0.49 12 11 0.39 36 35 0.06 7 8 0.3 16 17 0.69 5 6 0.71 33 32 0.65 82 81 0.29 11 10 0.38 15 14 0.44 67 68 0.96 57 56 0.44 70 69 0.17 5 4 0.29 45 46 0.03 99 98 0.83 70 71 0.83 57 58 0.56 8 9 0.44 94 95 0.07 98 97 0.99 13 14 0.53 34 35 0.46 53 52 0.45 4 3 0.93 52 53 0.79 86 87 0.23 6 7 0.26 87 86 0.73 73 74 0.94 33 34 0.35 38 39 0.94 58 59 0.75 36 37 0.94 28 29 0.74 51 52 0.89 14 13 0.03 59 60 0.22 89 88 0.72 31 32 0.1 92 93 0.36 64 65 0.02 1 2 0.97 95 96 0.66 12 13 0.61 76 75 0.82 18 19 0.93 38 37 0.06 93 94 0.29 99 100 0.17 10 9 0.55 43 42 0.0 15 16 0.56 44 45 0.8 22 21 0.14 65 64 0.48 90 91 0.05 56 57 0.43 77 78 0.48 35 36 0.05 72 71 0.79 14 15 0.97 49 50 0.67 56 55 0.57 6 5 0.74 10 11 0.45 91 92 0.68 40 39 0.04 67 66 0.04
100 200 802 1000
15 16 0.79 84 83 0.45 49 50 0.93 76 77 0.8 36 35 0.21 77 76 0.8 7 6 0.74 10 9 0.42 51 52 0.99 14 15 0.55 41 42 0.44 79 78 0.73 13 12 0.52 42 43 0.2 82 83 0.62 74 75 0.74 62 61 0.25 96 95 0.25 29 30 0.35 53 54 0.88 52 51 0.01 50 49 0.07 79 80 0.27 39 38 0.0 9 10 0.31 19 18 0.21 27 28 0.51 97 98 0.67 57 58 0.18 88 87 0.73 83 84 0.6 77 78 0.2 53 52 0.12 66 67 0.91 49 48 0.07 3 2 0.47 89 88 0.11 22 21 0.79 64 63 0.17 22 23 0.21 43 44 0.96 37 38 0.81 87 88 0.64 70 71 0.43 11 10 0.67 76 75 0.2 54 55 0.43 18 17 0.85 56 57 0.24 46 45 0.18 93 92 0.8 69 70 0.9 78 79 0.73 60 59 0.67 71 72 0.84 16 15 0.92 58 59 0.54 47 46 0.97 45 46 0.18 52 53 0.99 32 31 0.8 99 98 0.82 56 55 0.76 23 22 0.82 35 34 0.77 24 25 0.15 8 7 0.34 54 53 0.57 46 47 0.82 51 50 0.01 4 3 0.16 91 90 0.65 9 8 0.69 30 31 0.21 11 12 0.33 43 42 0.04 6 7 0.92 20 19 0.37 61 62 0.51 89 90 0.89 7 8 0.26 29 28 0.65 44 43 0.38 59 58 0.26 80 81 0.54 75 74 0.93 37 36 0.19 90 89 0.61 23 24 0.18 73 74 0.9 25 24 0.41 17 16 0.34 10 11 0.58 84 85 0.55 94 95 0.55 27 26 0.49 8 9 0.66 32 33 0.2 66 65 0.09 57 56 0.82 26 27 0.11 61 60 0.49 90 91 0.39 68 69 0.38 18 19 0.15 97 96 0.33 72 71 0.75 94 93 0.45 34 33 0.83 33 32 0.6 78 77 0.27 63 64 0.93 5 6 0.4 80 79 0.46 48 49 0.03 58 57 0.46 64 65 0.83 63 62 0.07 82 81 0.38 100 1 0.58 99 100 0.18 2 1 0.41 88 89 0.27 24 23 0.85 92 91 0.57 62 63 0.75 55 56 0.52 28 29 0.5 12 13 0.27 38 37 0.81 65 64 0.49 1 100 0.36 83 82 0.4 45 44 0.82 31 32 0.33 96 97 0.75 42 41 0.8 73 72 0.1 21 22 0.3 4 5 0.84 98 99 0.6 30 29 0.79 14 13 0.45 41 40 0.56 91 92 0.35 85 86 0.52 85 84 0.48 34 35 0.17 100 99 0.42 31 30 0.67 70 69 0.57 87 86 0.36 28 27 0.5 81 82 0.41 44 45 0.62 50 51 0.93 1 2 0.64 67 66 0.95 35 36 0.23 86 85 0.99 75 76 0.07 93 94 0.2 3 4 0.53 67 68 0.05 47 48 0.03 55 54 0.48 95 94 0.54 38 39 0.19 5 4 0.6 21 20 0.7 68 67 0.62 65 66 0.51 40 41 0.07 2 3 0.59 19 20 0.79 86 87 0.01 17 18 0.66 15 14 0.21 40 39 0.93 69 68 0.1 95 96 0.46 13 14 0.48 59 60 0.74 20 21 0.63 36 37 0.79 98 97 0.4 12 11 0.73 81 80 0.59 72 73 0.25 26 25 0.89 74 73 0.26 92 93 0.43 25 26 0.59 39 40 1.0 33 34 0.4 6 5 0.08 60 61 0.33 71 70 0.16 16 17 0.08 48 47 0.97
*** output
#1 1 1.000000 1 1.000000
#2 11 1.000000 18 1.000000
#3 4 0.386860 4 0.386860
#4 10 0.946340 10 0.851171
#5 3 0.150855 1 1.000000
#6 15 0.284926 7 0.505935
#7 4 0.118507 4 0.118507
#8 5 0.121474 5 0.121474
#9 3 0.591954 3 0.637576
#10 7 0.314579 6 0.280350
*** code mau
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std ;
int n , e , k , time1 ;
int A[110][101];
float xs[101][101] ;
float P[101][101] ;
int max(int t)
{
int max1 = 0 ;
for(int i = 1 ; i <= n ; i++ )
{
if(P[i][t] > P[max1][t])
{
max1 = i ;
}
}
for(int i = 1 ; i <= n ; i++ )
{
if(P[i][t] == P[max1][t])
{
if(max1 > i)
{
max1 = i ;
}
}
}
return max1 ;
}
int main()
{
//freopen("input.txt" , "r" , stdin) ;
for(int tc = 1 ; tc <= 10 ; tc ++)
{
cin >> n >> e >> k >> time1 ;
for(int i = 1 ; i <= 101 ; i++ )
{
for(int j = 1 ; j <= 101 ; j++ )
{
P[i][j] = 0 ;
A[i][j] = 0 ;
xs[i][j] = 0 ;
}
}
for(int i = 0 ; i < e ; i++)
{
int x , y ;
float xs1;
cin >> x >> y ;
scanf("%f",&xs1);
xs[x][y] = 0 ;
A[x][0] ++ ;
A[x][A[x][0]] = y ;
xs[x][y] = (float)xs1 ;
}
int t = 1 ;
P[1][1] = 1 ;
while(t <= (time1/10))
{
for(int i = 1 ; i <= n ; i++)
{
if(P[i][t] != 0)
{
for(int j = 1 ; j <= A[i][0]; j++)
{
P[A[i][j]][t+1] += P[i][t] * xs[i][A[i][j]];
}
}
}
t++ ;
}
int kq1 = max(t) ;
int kq2 = max((time1- k)/10 + 1);
printf("#%d %d %.6lf %d %.6lf" , tc,kq1,P[kq1][t] ,kq2, P[kq2][(time1- k)/10 + 1] );
//cout << "#" << tc << " " << kq1 << " " << << " " << kq2 <<" " <<<< endl ;
cout << endl ;
}
return 0 ;
}