1403. Anamorphic |

1404. Association |

1405. Crap Streak |

1406. Disorder |

1407. deMorse |

1408. Flush |

1410. String Picker |

15/10/2024 16:31:53

Графы

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

24/06/2010 | Лето 2010 дорешивание ( 3G) |

28/06/2010 | Лето 2010 - 3 (G) |

14/07/2017 | Лето 2017 (командное) - 10 (B) |

*Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Let `(V,\ E)` be a directed graph in which `V` is a finite set of vertices and `E\ sube\ V\ times\ V` is a set
of edges such that `||{\ q\ |\ (p,\ q)\ "isin"\ E\ }||\ ≤\ 1` for all `p\ "isin"\ V`. In other words, `E` can be viewed as a
predecessor-successor relation on vertices in which each vertex has at most one successor. Such
a graph can be seen to contain embedded lists-sequences of vertices `v_1,\ v_2,\ …,\ v_n` in which `v_1`
has no predecessor, `v_{i+1}` is the successor of `v_i` for `i\ =\ 1,\ 2,\ …,\ n-1`, and `v_n` has no successor. In
this problem, you are given a directed graph in which vertices have at most one successor, and are
asked to count the number of embedded lists and compute the average number of vertices in those
lists.

Input Format

The input contains one or more directed graphs, each of which is described on one or more
nonempty lines of input followed by an empty line of input. Each nonempty line of input in a
graph contains one or more pairs of vertices. The vertices are non-white-space ASCII characters
separated by one or more blanks. The pairs of vertices in a graph form the predecessor-successor
relation of the graph. To insure that no vertex has more than one successor, if there are multiple
pairs having the same predecessor, then their vertices are included and their edges except the last
are ignored (e.g. as in the second graph in the input sample below).

Output Format

For each directed graph in the input, count the number of embedded lists containing at least
one vertex, and compute the average number of vertices in those lists, rounded to two decimal
places as shown in the output sample.

Sample Input

a b b c c d d e a b a c a d a b b c c a a c b c c d d e g h h i i h

Sample Output

1 lists averaging 5.00 vertices 3 lists averaging 1.33 vertices 0 lists 2 lists averaging 4.00 vertices