Polish version    English version  
  O olimpiadzie -> Zadania -> I OI 1993/1994


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
Ten dokument nie jest dostępny w polskiej wersji językowej.

Niebieskie ksi.eczki
I Olympiad in Informatics 1993/1994

Task: PRZ
Author: Maciej M. Sysło
Network Capacity

III stage contest  

A city network consists of N (0 < N <= 100) nodes successively numbered from 1 to N, and one-way direct connections between nodes.

There exist at most two direct connections between any two nodes k and l: at most one from k to l and at most one from l to k.

Every direct connection has fixed capacity, being a natural number from the interval [1, 32000].

A nonempty sequence of distinct direct connections is called a route from a node k to l, if:

  1. k is the beginning of the first connection in this sequence,
  2. an end of every connection - except the last one - is a beginning of the next connection,
  3. l is the end of the last connection in this sequence.

The capacity of a route is equal to the minimal capacity of direct connections it comprises.

There may exist many routes of different capacity between two network nodes. There may be no route too.

Task

Write a program, that reads from the text file PRZ.IN data on a city network. Next, it computes answers to queries read from PRZ.IN - each of which is in a form of a pair of numbers k l denoting two distinct nodes. Then it writes the answers in consecutive lines of the text file PRZ.OUT, and each answer is:

  • the number 0, when a route from k to l does not exist, or
  • maximal capacity of such a route.

The data in the text file PRZ.IN is written in the following form:

The number of nodes N is written in the first line.

It is followed by N successive lines each with descriptions of direct connections beginning at successive network nodes (in the i-th of these lines there are connections beginning in the node i).

The N+1 lines are followed by a nonempty sequence of queries and the end of the file.

A description of direct connections beginning at a specified network node k is a sequence of nonnegative integers separated by single spaces. The first element of the sequence is the number nck of those connections. If nck = 0, then the sequence ends, if not then there follow nck descriptions of every of the connections in a form of a pair of numbers. The former is the number of node the connection leads to, the latter is its capacity.

Immediately after the last number of each description of direct connections there is a semicolon followed by the end of the line.

Every query has a form of a pair of node numbers, i.e. numbers in the interval [1, 100]. All the queries form a sequence (of even length) of natural numbers separated by a space or a single end-of-line character.

The last number is directly followed by the end of the file.

The data in the file PRZ.IN is written faultlessly and your program needs not examine this.

The answers should be written to the file PRZ.OUT, in the order corresponding to the order of queries, in a form of a sequence of nonnegative numbers separated by a single end-of-line characters.

The last answer should be directly followed by the end of the file.

Example

For the file PRZ.IN:

5
3 2 3 3 2 5 1;
1 3 1;
1 2 1;
2 3 2 5 4;
1 4 3;
1 4 4 1 2 3 3 4 1 5 5 2 2 4 4 5 3 4 4 2(end of file)
your program should create the following file PRZ.OUT:
1
0
1
0
1
1
0
4
0
1(end of file)

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

Your program should look for the file PRZ.IN in the current directory and create the file PRZ.OUT also in the current directory. The source file containing the program written by you should be named PRZ.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file PRZ.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk, and of the description of your algorithm and the justification of its correctness.




Wersja do druku