Zkouška 22.6.2009

Táák dneska jsme měli jako úlohu spočítat objem pódia.

Máme dva typy součástek, ze kterých můžeme skládat krychle, a ty pak složí dohromady podium:

• **Nosník **(ten je tří typů) - pojmenovaný (ID) podle nějakého rockového CD

• • K(rátký) .. odpovídá straně krychle a má délku 0,5m

• • D(dlouhý) .. odpovídá stranové úhlopříčce

• • H(hodně dlouhý) .. odpovídá tělesové úhlopříčce v krychli

• Spojovací díl - pojmenovaný (ID) podle nějaké rockové skupiny

VSTUP:
Soubor, kde dostaneme na každém řádku 3 údaje:

• Typ nosníku

• ID nosníku

• ID spojovacího dílu

takže např:
K;The Piper at the Gates of Dawn;Pink Floyd

VÝSTUP:
objem sestaveného podia

• podium jde sestavit jednoznačně

• na výpočet máme 10kB paměti

• nosníků i spojovacích dílů je max 1 000 000

No, zkoušku jsem sice neudělal, ale nedalo mi to a myslím, že mám řešení - kdyžtak nechť mě někdo opraví.

Ze vstupního souboru si vyrobím vnějším tříděním dva soubory, jeden setříděný podle ID spojovacího dílu, druhý podle ID nosníku, dlouhé a hodně dlouhé jsou k ničemu.

Pak vyhledám BÚNO nějaký spojovací díl s nejnižším počtem spojení (min 3) a přečtu ID nosníku, pak vyhledám v souboru s nosníky odpovídající ID spojovacího dílu "na druhé straně". Takto pokračuji, dokud nepostavím celou kostku. Pak si zapamatuji, že kostka byla postavena, čítač kostek zvýším o jedna a odstraním ze souborů (označím jako použité, či cokoliv) ty díly které se nacházejí v právě postavené kostce. Tím se můžu zbavit i všech dílů (pokud to byla kostka poslední), nebo u dalších spojovacích dílů snížím počet spojení o jedničku, opakuji, dokud je co odebírat.

Doufám, že to je správně a alspoň sám před sebou obhájím svoji čest.

ja jsem to delal takhle:

• pro moje reseni uhlopricky nemeli vyznam - takze jsem je vyhazel ze zadani
  pak jsem mel setridene zadani nejdriv podle hran - hrany.txt a pak podle vrcholu - vrcholy.txt.
  ve vrcholech jsem nasel vsechny co maji stupen 3 (koukam do vrcholy txt a tam kde jsou prave tri radky u nejakyho id tak ten to je..na jeden pruchod hotovy) - to jsou takove ktere nalezi kostce co je nekde narohu/nahraji atd.. - tyhle vrcholy a jejich hrany jsem si nekam napsal 3.txt
  idea je takova ze tyhle vrcholy odeberu a za kazdy odebrany se pricte jedna krychle k objemu - zaroven vzniknou novy krychle co maji nejakej vrchol stupne tri a takhle postupne muzu rozebrat celej 'graf'.
  (abych neco neodecet tak si udelam 3supr.txt kde budou vrcholy kde nemaji zadnou spolecnou hranu, ale ani to moc nefunguje..proste existujou krychle kde jsou treba 4 vrcholy se stupne tri a ja potrebuju aby se to nepocitalo vickrat zejo..)
  z hrany.txt odeberu vsechny hrany co byly v 3.txt..to jde tak nejak linearne (oboje je/muze byt setrideny) a znovu si udelam vrcholy.txt

... holan rikal ze reseni to je celkem dobry, ale nenapsal jsem to tam uplne idealni, slozitost vychazela jako neco krat n log n (kvuli tomu trideni porad), treba vam to aspon trochu pomuze, asi jsem to nenapsal uplne nejlip..

kdyztak sem kouknu kdyby to nekoho zajimalo jeste.

ideu mas takmer rovnaku ako ja, az na to ze som si vytvaral zbytocne zlozity druhy subor v ktorom riadok mal format
id vrcholu, pocet hran tohto vrcholu(n), hrana1,hrana2,...hranan
potom som rpehladal tento subor a ak som natrafil na riadok kde vrchol mal pocet hran=3 tak som si jeho hrany ulozil do fronty...tento riadok vymazal a pre kazdu hranu ktora viedla z tohhto vrcholu som nasiel ten druhy vrchol do ktoreho vchadzala a riadok tohto vrcholu som upravil takto:
id vrcholu, pocet hran(k-1), tu boli hrany, ale tu podla ktorej som namatchoval tento riadok som vymazal...
po tomto ukone som dvihol velkost objemu o 1.
tym padom ale mohol vzniknut problem a to taky ze niektore riadky boli
id vrcholu, 2, hrana1, hrana2
tieto riadky som nasiel a vymazal pricom hranu1 a hranu2 som opat nasiel este pri nejakom inom vrchole, tam som znizil cislo a vymazal ju zo zoznamu...
takto som to opakoval v cykle az kym nezmizli vsetky riadky <=3, pricom increase som robil iba ak som odstranoval vrchol s 3 hranami.