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: WAH
Author: Piotr Chrząstowski-Wachtel
Stock Exchange Fluctuations

III stage contest  

By examining a history of a stock exchange we want to calculate the maximal profit (the maximal difference between selling price and buying price) that could have been earned by buying and next selling a single share.

Exchange sessions are held every day. The number of companies changes, because companies might go bankrupt; new companies might enter too. Every day for every company its share price in that day or information on its bankruptcy is announced. A company which has gone bankrupt will not be quoted any longer.

The exchange has a history of many years, but the number of companies quoted the same day has never dropped to 0 nor has been greater then 10000, though together there might have been many more companies during the whole history of the exchange.

The history of the exchange price fluctuations of shares is written in the text file WAH.IN. Every line is nonempty and describes outcomes of one session: there are fluctuations (changes in the price of a share compared with that of the previous day) or information on bankruptcy for every company present at the exchange. In the first line there are differences between share prices of companies on the second and on the first day of the existence of the exchange. In the second line there are price differences between the third and the second day, and so on.

Price fluctuations of stock companies shares are always quoted in the same order. Companies' names are omitted. A company is identified by its position in the line describing the quotation of a given day. A company, that appears first in the first line, may appear only in the first position in the following lines. A company that is second in the first line will always be second until it goes bankrupt, or the first company goes bankrupt leaving the first position to the former, and so on.

When a new company arises, then the first price fluctuation of its share is quoted in the first day after it entered the exchange. New companies are added at the end of the relevant line.

If a line of the file becomes exhausted unexpectedly, not giving information on all the companies that we awaited according to the quotations of the previous day, then the situation is classified as a data error. The situation when the first quotation of a company is the information of its bankruptcy (the number -99) is classified the same.

Fluctuations of shares are quoted as integer numbers in the range [-99, 100]. A negative number distinct from -99 means that the value of the share has dropped, zero - that it has not changed, and a positive number - that it has raised accordingly. The number -99 means that the company has gone bankrupt and it will not be quoted any longer.

Task

Write a program that, for a set of data on a stock exchange from the file WAH.IN, writes to the text file WAH.OUT the following:

  • the word NONSENS ("nonsense"), if the data is not correct,
  • the number zero, when the data is correct but all the stocks make losses, or
  • the maximal profit made with a single share.

Example

For the file WAH.IN

  1  -4   2   4
-99   2  -5   1
 -1   3  -2   5
  6  -2   1   1
 -1  -1   3   1(end of file)
your program should write the number 7 in the file WAH.OUT.

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 WAH.IN in the current directory and create the file WAH.OUT also in the current directory. The source file containing the program written by you should be named WAH.???, 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 WAH.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