## UTS Open '15 #4 - Subway

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Ms. Evans is meeting some venture capitalists who may be able to fund her startup. Unfortunately, she is running late, and the meeting is in () minutes. The subway system is a network of stations () numbered from to which are connected to each other by one-way links (). The link connects station to station () and could take anywhere from to minutes to traverse (). The time taken is an integer number of minutes chosen uniformly at random from all integers between and inclusive.

The subway system is very unpredictable.

Since the system is complicated, Ms. Evans follows a simple procedure: at every point, she uses a link selected uniformly at random from all links leaving her current station. Ms. Evans ends her trip when she reaches the meeting or when she reaches a station without any outgoing links.

Ms. Evans starts at station and the meeting will be held in station . Ms. Evans arrived at the meeting after minutes, and she was on time (that is, ). Calculate the expected value of .

Portion of marksConstraints on Constraints on Constraints on

#### Input Format

The first line will contain , , and . The of the next lines will contain , , , and in sequence. It is guaranteed that the chance of Ms. Evans arriving on time will exceed .

#### Output Format

A single line containing the answer to the problem. Your answer will be considered correct if its absolute or relative error does not exceed .

#### Sample Input 1

2 1 4
1 2 1 100000

#### Sample Output 1

2.5000000000

#### Explanation

In this case, the answer is the average of the values that would let Ms. Evans be on time: .

#### Sample Input 2

3 2 3
1 2 1 100000
2 3 1 100000

#### Sample Output 2

2.6666666667

#### Sample Input 3

3 3 2000
1 3 1 1
1 2 1 1
2 1 1 1

#### Sample Output 3

3.0000000000

#### Explanation

The answer is close to .

#### Sample Input 4

2 3 10
1 2 6 10
1 2 1 2015
1 2 8 17

#### Sample Output 4

8.2203841034

#### Sample Input 5

3 4 3
1 2 1 2
2 3 2 2
2 3 1 6
1 3 1 10

#### Sample Output 5

2.4938271605

#### Picture

• commented on May 5, 2015, 9:10 p.m.

Can someone please explain how sample 5 obtained that output? Even after doing it by hand I could only get ~2.12 as the answer.

• commented on May 5, 2015, 10:52 p.m. edit 3

1 to 3:

1/20 * 1

1/20 * 2

1/20 * 3

1 to 2:

1/4 * 1

1/4 * 2

2 to 3:

1/8 * 3

1/48 * 2

1/48 * 3

1/48 * 3

This totals to ~0.842.

0.842 / (1/8 + 3(1/48) + 3(1/20)) = ~2.494.

• commented on May 8, 2015, 6:34 p.m.

Thanks m8 I'll tell bruce to give you a sticker next class.

• commented on April 30, 2015, 11:13 p.m.

Would the answer for test case 2 be 1.833333? It would be 1/6 2 + 1/6 3 + 1/3 * 3 no?

• commented on May 1, 2015, 9:16 p.m.

The time taken is an integer number of minutes chosen uniformly at random from all integers between xi and yi inclusive.

In sample case 2, the probability to station 2 for 1 minute is 1/100000, for 2 minutes is 1/100000. Similarly, the probability to station 3 for 1 minute is 0, for 2 minutes is (1/100000)*(1/100000), for 3 minutes is (1/100000)*(1/100000)+(1/100000)*(1/100000) (first term: move to 2 for 1 minute and from 2 to 3 for 2 minutes; second term: move to 2 for 2 minutes and from 2 to 3 for 1 minute).

So, the expected value to 3 is

{(2 minutes to 3)*(probability of 2 minutes to 3) + (3 minutes to 3)*(probability of 3 minutes to 3)}/(overall probability to 3 within 3 minutes)

= {2*(1/100000)*(1/100000)+3*[(1/100000)(1/100000)+(1/100000)\(1/100000)]} / [(1/100000)*(1/100000) + (1/100000)*(1/100000)+(1/100000)*(1/100000)]

= 8/3

= 2.6666666667