Nepokoje v nasich vazniciach narastaju do neusosnych medzi

Nepokoje v nasich vazniciach narastaju do neusosnych medzi. A to nielen preto,
ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a
nie tie ich, na kt. si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju cislami,
je tento fakt velmi nevytany.
 
Vsetko vyriesil novy projekt Alcatraz II. Ak pride do tejto vaznice dalsi vazen,
dozorcovia zadaju do pocitaca jeho meno a priezvisko a program vypise NOVY, ak
tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel po prvy raz.
Program tiez vypise cislo vazna. Novemu vaznovi moze program priradit lubovolne
cislo, ktore avsak nema iny vazen, no recidivistovi musi priradit cislo z jeho
predchadzajuceho pobytu. Mozno predpokladat ze cisla su priradovane iba uvedenym
programom. ULOHA:
 
Vytvorte horeuvedeny program tak, aby fungoval co najrychlejsie a pre co
najvacsie mnozstva vaznov. Program bude uvedeny do prevadzky zaroven s otvorenim
vaznice, takze vaznica je na zaciatku prazdna. Kedze Alcatraz II nikdy
neprestane fungovat, mal by aj vas program fungovat v nekonecnej slucke. Mena
vaznov su zlozene z velkych pismen abecedy a z medzier.
 
Priklad vstupu a vystupu:
  ? LEX LUTHOR
   NOVY 3560
  ? JAMES BOND
  NOVY 007
  ? LEX LUTHOR
  RECIDIVISTA 3560
  ? LOIS LANE
  NOVY 806070
  ? JAMES BOND
  RECIDIVISTA 007
 
Lexikograficky strom pre rychle vyhladavanie.
Ovladanie je ESC pre exit a ? klavesa pre vyhladavanie. Program si vie aj
zapamatat novopecenych recidivistov, ktorych si hned poznamena do stromu,
tabulky aj do suboru cez append.
Subor je obycajny textovy. Da sa premazat, ale nechal som dva prve riadky pre
hlavicku Alcatraz II. Preto by mali byt vzdy 2 riadky zhora (program automaticky
preskakuje 2 riadky).
Program pouziva binarny strom, a sice dva. Jeden sluzi pre evidovanie vaznov,
ten je lexikograficky s vetvami nazvov 'a'..'z' a velke pismena sa osetruju hned
na zaciatku ansilowercase-om. Druhy je strom cisielkovy, je naprosto rovnaky,
len s mensim poctom vetiev. Podstatna je len platna cesta.
 
STROM Vaznov (napriklad):                Strom Cisiel vaznov (napriklad):
* * / *            *  *  *                 * * /  *           * *
*[a] = -1          *[c] = 7                 * [0] = nil?*      * [7]=nil?*
(neexistuje)*        (1 index v tab)*          *  * *             * ***
Spolu 26 vetiev v kazdom uzle                   tu je vetiev 10
 
Tabulka cisiel vaznov:
[0] 313
[7] 007
...
Pri vkladani do cisloveho stromu sa len vytvaraju nove vetvy s nil podvetvami.
Je to pre rychle vyhladavanie. Pri vkladani do pismenkoveho stromu sa vytvaraju
nove vetvy takisto, ale kazda novovytvorena vetva sa nastavi na -1 pre cislo
indexu. Okrem poslednej vetvy, kde uz sa vklada priamo cislo.
 
Toto cislo indexu je velmi dolezite, lebo "Karol Koubek" je recidivista. Dozorca
chce zistit, ci novoprijaty Karol Koube je uz v databaze. V beznom pripade ak by
sme neskumali korektnost pomocou -1, by sme presli vetvami az po ..ek a zistime
ze cesta je platna, vazen teda existuje. To je chyba.
Pre istotu som aj do cisloveho stromu dal -1 validator. Keby sa cesta skoncila
predcasne a cislo by nemalo existovat. Napriklad pri generovani noveho cisla pre
noveho recidivistu, stary je zapisany ako 666, vytvori sa nahodou 666. Toto sa
uz nestane.
 
Nesmu byt dvaja rovnaki recidivisti a dve rovnake cisla.
 
Dolezite je este spomenut ze pre tabulku skutocnych cisiel vaznov, pouzivam
hlavny index velkost_pola_recidivistov, ktory sluzi jednak ako posledna aktualna
velkost, a zaroven ako hodnota, ktora sa uklada do stromu vaznov.
 
Pohyb v pismenkovom strome prebieha tak, ze sa retazec rozdeli na znaky, a
zistuje sa len to, ci existuje vetva oznacena ako znak[z]. Pohyb v cisielkovom
strome je rovnaky, pouziva vetvy oznacene ako 'a'..'z'.
Mal som aj lepsie riesenie:
z ciselka berieme poslednu cifierku najpr, teda z 1567 si zoberieme 7 pomocou
1567 mod 10. Potom cisielko este zmensime div 10. Vysledok zapiseme a nastavime
novu vetvu. Ale nesplnalo to kriteria pre 007.
 
Sofistikovane je prevedene zlucenie stromu cisielok a stromu vaznov. A to tak,
ze vo vetve vaznov sa okrem mena eviduje cislo, ale nie konkretne instantne
cislo, ale len poradove cislo indexu na lokalnej tabulke vaznov. Potom konkretne
cislo vazna dostaneme, ked pouzieme toto "cislo" v indexe tabulky, a tym ho
spravne rozlustime. Pole je array of string, a je dynamicke, pre rozny pocet
vaznov a pre setrenie pamate. Jediny sposob ktory mi napadol pre okamzite
zistenie ci novy vazen sa nekryje s inym vaznom (ciselne).
 
Z cisielkoveho stromu je jedno ci cislo berieme v strome od predu alebo od zadu.
Podstatne je len to, aby sme vzdy zvolili rovnaky postup.
 
V zadani som si vsimol aj cislo 007. Rozhodol som sa teda, pre zjednodusenie
vetvy urcit ako typ char.
 
Ostatne veci su uz prijemne, zlozitost programu je O^n, priamo umerna poctu
pismeniek a cisielok.