HW04: Dlužníček

Právě jste byli přijati do firmy jako náhrada za bývalého zaměstnance Ládínka, kterého vyhodili pro neschopnost v práci s gitem. Bohužel se vám nikdo z kolegů nemůže věnovat, jsou totiž zaneprázdněni opravováním následků git push --force do mainu. Vaším úkolem je převzít práci po nedávno vyhozeném kolegovi a do dvou týdnů ji dokončit. Jedná se pouze o vnitrofiremní prezentaci, není tedy nutné vyvinout kompletní aplikaci, stačí pouze backend s dostatečnou funkcionalitou.

Rozhodnutí, zda aplikaci pouze upravíte, nebo ji napíšete celou od začátku, je pouze na vás.

Obecně platí, že prázdný řádek je validní a program jej při načítání přeskočí. Naopak nic nepředpokládejte o délce souborů, ani o délce řádků (a z toho vyplývající délky jednotlivých řetězců). Dále počítejte s tím, že testy mohou programu podstrčit soubory v nevalidním formátu.

Prázdný řádek je složen pouze z bílých, anebo žádných znaků. Žádný term (znázorněný ve špičatých závorkách) nemá jako svůj první ani poslední znak bílý znak. Pokud není v popisu termu řečeno jinak, neobsahuje bílé znaky ani uprostřed.

Formát výstupu je přesně následující:

Dodržte formát výstupu přesně včetně mezer. Kontrolní skript může, ale nemusí být, v tomto ohledu benevolentní. Pro jistotu zde je uvedený formátovací řetězec pro funkci printf(3):

Jedná se o definiční soubor, pomocí kterého se vytváří seznam osob, u kterých se očekává, že si budou navzájem dlužit peníze. Každá osoba má své jméno a unikátní id.

Možné chyby, které mohou nastat:

Jedná se o definiční soubor, pomocí kterého je možné definovat měny a jejich směnný kurz. Každá měna je definována svým id a koeficientem, který stanovuje, kolik jednotek základní měny má hodnotu jedné jednotky aktuální měny. Základní měna má hodnotu koeficientu rovnu nule. Není třeba kontrolovat, že koeficient má nejvýše určený počet číslic.

Možné chyby, které mohou nastat:

Jedná se o soubor, který s využitím údajů z předchozích dvou uvedených souborů vytváří seznam uskutečněných plateb. Každá platba se skládá ze čtyř údajů:

Seznam plátců i seznam dlužníků se skládá id osob. V každém seznamu může být osoba uvedena vícekrát — takovým způsobem lze stanovit váhu osoby, s jakou se podílela na platbě. Měna je uvedena pomocí id měny. Soubor je validní i v případě, že neobsahuje žádnou platbu. Dále je validní, pokud je stejná osoba uvedena v seznamu plátců i v seznamu dlužníků.

Může nastat situace, kdy bude částka záporná. To je naprosto v pořádku — jedná se o situaci, kdy některý člen skupiny realizuje příjem. Není třeba kontrolovat, že částka má nejvýše určený počet číslic.

Možné chyby, které mohou nastat:

Výstup programu obsahuje informaci, kdo má komu poslat jakou částku tak, aby došlo k vyrovnání dluhů v rámci celé skupiny. Pokud není co vyrovnávat, je legitimní, když bude výstup programu prázdný. Při vyrovnání není nutné, aby dlužník vracel dlužnou částku tomu, kdo za něho platil.

Pro nebonusové řešení jsou na výsledný seznam transakcí kladeny tyto podmínky:

Při vyrovnání dluhu může nastat zaokrouhlovací problém — například pokud se částka 100 korun rozdělí mezi 3 osoby. V tom případě je tolerována výsledná odchylka o jednu setinu základní měny u každé zúčastněné osoby. Navzdory této toleranci musí mít program snahu dluh co nejvíce eliminovat.

Načítáte-li do programu číslo, můžete předpokládat, že nepřekročí velikostní limity stanovené v sekci Formát vstupních souborů. Číslo ve výstupu taktéž nepřekročí limit uvedený v sekci Formát výstupu (za předpokladu, že jste algoritmus naimplementovali korektně). Je však žádoucí kontrolovat, zda je načítaná sekvence znaků číslem.

Bonusová část tohoto úkolu spočívá v tom, že implementujete algoritmus vyrovnání dluhů tak, aby bylo potřeba vykonat minimální počet transakcí. Různé naivní přístupy mohou vést k jejich vyššímu počtu. Pro lepší pochopení je vhodné si odkazovanou diplomovou práci nastudovat důkladněji.

Protože výsledný algoritmus může vést k časově náročnějšímu výpočtu, bude se optimální algoritmus spouštět pouze v případě, že program obdrží jako svůj první argument --bonus (další argumenty budou logicky posunuté o jednu pozici).

Využijte testů napsaných Vaším bývalým kolegou k opravení jím naimplementované funkcionality, můžete je samozřejmě i upravovat či mazat.

Zamyslete se nad interní reprezentací desetinných čísel. Jak velké jsou typy pro desetinná čísla v jazyce C? Budou vám stačit? Zkuste zkonzultovat dokumentaci.