Hurry Chinchilla! | MatCom Online Grader

The 2024 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

H - Hurry Chinchilla!

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
It's been a few years since researchers began studying a theoretical device called a chinchilla router.

When the router receives a packet that is not destined for a computer in its local network, the device randomly chooses one of the other routers connected to it with equal probability and forwards the packet to that router. This process continues until the packet arrives at its intended destination. The routers don't track whether a packet has already passed through before, so a packet may pass through the same router repeatedly on its way to its destination. The device was proposed by a graduate student from the Republic of Incadelia who imagined passing messages by training chinchillas to navigate a series of tubes.

We would like to take a closer look at this model. We say a packet made an *antioptimal* hop if it gets sent to a router without getting closer to the destination. Your task is to create a program that receives a description of a network of chinchilla routers and finds the expected number of antioptimal hops that would occur when sending a packet.
</div>

Input

Output

Sample test(s)

Input

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

Output

NO ROUTE 2.000 2.000 1.667

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

The 2024 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

H - Hurry Chinchilla!

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana