Polish version    English version  
  History of OI -> I OI 1993/1994 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
Problems
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
I Olympiad in Informatics 1993/1994

Task: PRZ
Author: Maciej M. Sysło
Undertaking

II stage contest  

An undertaking consists of some number of jobs numbered by successive integers from 1 to N <= 1000. The undertaking is accomplished when all the jobs are.

For every job we know the time - being a positive integer - necessary to accomplish it, and the collection of those jobs which have to be accomplished before this one is started.

An undertaking is realizable if it does not contain any subset of jobs that forms a cycle. For example, suppose that a job a has to be accomplished before a job b is started, the job b has to be accomplished before a job c is started, the job c has to be accomplished before a job d is started, and the job d has to be accomplished before the job a is started. Then those jobs form a cycle (a, b, c, d), and the undertaking is not realizable, for none of the jobs from the cycle can be started.

Task

Write a program, that successively for every undertaking data set read from a text file PRZ.IN:

  1. states whether the undertaking is realizable,
  2. determines the shortest time to accomplish the undertaking,
  3. answers questions whether extending the accomplishing time for a given job by a given amount extends the time needed to accomplish the whole undertaking, and writes the results to a text file PRZ.OUT.

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

The file PRZ.IN is always nonempty and may contain many sets of data on different undertakings.

Every set of data on an undertaking has the following form:

In the first line a number N of jobs comprising the undertaking is written.

After that line there are N descriptions of jobs.

Every job description is a finite, at least two-element sequence of positive integers separated by a space or an end-of-line character. The first number of the sequence is the number of the job, the second one is the time necessary to do it, and the following ones are the numbers of jobs that have to be accomplished before. A job description is terminated by a semicolon followed by the end of the line.

After the last description of a job there may appear a sequence of questions whether extending a job of a given number by a given amount of time causes a delay in realisation of the undertaking.

Every question has the form of a pair of numbers separated by a space and is terminated by a semicolon, which may be followed by a space or the end of the line. The first number is the number of a job and the second one is the suggested extension to its accomplishing time.

Consecutive data sets in the file PRZ.IN are separated by an empty line. After the last data set there is the end of the file.

We assume that the data in the file PRZ.IN are written faultlessly and your program needs not check its correctness.

The file PRZ.OUT should contain one set of results for each set of data on an undertaking from the file PRZ.IN.

A set of results is:

  • the word CYKL ("cycle"), if the undertaking is not realizable, or
  • a natural number (the shortest time to accomplish the undertaking), if the data set does not contain questions, or
  • a natural number and the words TAK ("yes") or NIE ("no") - written in separate lines - which are answers to the successive questions.

Consecutive sets of results are separated by an empty line, and the last set is followed by the end of the file.

Nothing else should be written in the file PRZ.OUT.

Example

For the file PRZ.IN:

6
1 1;
2 1 1 6;
5 4 1;
3 5 5 4;
4 5;
6 2 4;
4 1; 2 1; 6 2; 1 1; 2 3; 6 3;
(empty line)
4
1 1 3;
2 1 1 ;
3 2 1 2;
4 1 3;
2 1; 3 2;
(empty line)
4
1 1;
2 2;
3 3 1;
4 2 3;
1 1; 2 3; 2 5;(end of file)
your program should create the following file PRZ.OUT:
10
TAK
NIE
NIE
TAK
TAK
TAK
(empty line)
CYKL
(empty line)
6
TAK
NIE
TAK(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.




Print friendly version