(Informacje po polsku sa nizej.)

This is my solution for the "company ownership problem". This problem
was one of the task on the 5th International Olympiad in Informatics
(Mendoza, Argentina, October 16 - 25, 1993). The problem is "PROBLEM 2" from this file.
I solved this problem as a part of the recruitment process
in some company (they didn't hire me after all; oh well...).

Here is a reformulation of the problem - my program follows these
requirements:
---
Company ownership

Some companies are partial owners of other companies because they have
acquired part of their total shares. For example, Microsoft owns 1,3%
of Facebook. It is said that a company A controls company B if, at
least, one of the following conditions is satisfied:

    * A owns more than 50% of B
    * The total sum of shares of B which are in possession of A and
      companies controlled by A is greater than 50%

The problem to solve is:

Given a list of triples (i,j,p) which means that the company i owns p%
of company j, calculate all the pairs (h,s) so that company h controls
company s. There are at most 100 companies.

Write a program to:

    * Read from an input stream the list of triples, (i,j,p), to be
      considered for each case (that is, each data set), where i, j
      and p are positive integers. Different cases (data sets) will be
      separated with a blank record.
    * Find all the pairs (h,s) so that company h controls company s.
    * Write to an output stream all the pairs (h,s) found, with
      h different from s. The pairs (h,s) must be written in consecutive
      records and in increasing order of h. The solutions for different
      cases must be separated with a blank record.
---

Here is a part of the README.txt file included in a .zip archive
(see also comments in source file):

Data may come either from stdin or from file(s). If there is no
command-line argument, then program reads it from stdin, otherwise it
processes given files. Different datasets may be separated by an empty
line.

So you can run this program in different ways:
> java -jar CompanyOwnershipProblem.jar inputTestFiles\input1.txt 
( or
> java -jar CompanyOwnershipProblem.jar inputTestFiles/input1.txt
  on Linux/Unix)
> java -jar CompanyOwnershipProblem.jar file1 file2
> java -jar CompanyOwnershipProblem.jar < input-file
> someOtherProgram | java -jar CompanyOwnershipProblem.jar

Run the program with "-h" or "--help" argument to get this help.

There are some testing input files in "inputTestFiles" directory.
For every "input" file there is also corresponding "output" file
which contains proper solution.
Unix shell script "run-tests.sh" run this program on input files
and compares its output with proper solutions in "output" files.
(I wrote this program on Linux, so originally all .txt files had
unixish end-of-lines. I converted line endings in these files
to format used on Windows, so they can be opened in Notepad witout
problems. When running run-tests.sh on Linux, however, you'll need to
convert line endings back to unixish first.)

There is a file with source code in "companyownershipproblem" directory.

Author:  Bartlomiej Brzozowiec , IV/V 2011
License: GPL v3 or later



Program, ktory rozwiazuje "problem wlasnosci firm". Bylo to jedno z
zadan na 5. Miedzynarodowej Olimpiadzie Informatycznej (zob. "PROBLEM 2"
z tego pliku).
Rozwiazalem to zadanie jako wstepny etap rekrutacji w pewnej firmie
informatycznej (nie przyjeli mnie tam jednak; no coz...).
Zadanie w wersji zadania rekrutacyjnego bylo nieznacznie
przeformulowane w porownaniu do oryginalnej wersji z Olimpiady, ale
takze bylo po angielsku. Ponizej moje tlumaczenie tresci zadania,
ktore rozwiazuje moj program:

---
Niektore firmy sa czesciowymi wlascicielami innych firm, gdyz nabyly
czesc z ich calkowitych udzialow. Na przyklad Microsoft posiada 1,3%
Facebooka. Mowi sie, ze firma A kontroluje firme B, jesli, co
najmniej, jeden z nastepujacych warunkow jest spelniony:
- A posiada ponad 50% B
- calkowita suma udzialow B, ktora jest w posiadaniu A i firm
  kontrolowanych przez A, jest wieksza niz 50%.

Problem do rozwiazania jest nastepujacy:

Majac liste trojek (i,j,p), ktora oznacza, ze firma i posiada p% firmy j,
okresl wszystkie pary (h,s) takie, ze firma h kontroluje firme s.
Jest co najwyzej 100 firm.

Napisz program, ktory:
- czyta ze strumienia wejsciowego liste trojek, (i,j,p), rozwazana dla
  kazdego przypadku (tj. kazdego zestawu danych), gdzie i, j i p sa
  dodatnimi liczbami calkowitymi. Rozne przypadki (zestawy danych) beda
  rozdzielone pustym rekordem
- znajduje wszystkie pary (h,s) takie, ze firma h kontroluje firme s
- wypisuje do strumienia wyjsciowego wszystkie znalezione pary (h,s),
  z h roznym od s. Pary (h,s) musza byc wypisane kolejno i w rosnacej
  kolejnosci h. Rozwiazania dla roznych przypadkow musza byc oddzielone
  pustym rekordem.
---

Wiecej informacji (po angielsku) w pliku README.txt w paczce .zip
(zajrzyj tez do pliku z kodem zrodlowym - jest tam obszerny komentarz
na temat uzytych technik zastosowanych w celu rozwiazania zadania).

BB