Šance pro programátory

Co jsme před týdnem slíbili, je tady! IBM ve spolupráci s Computerworldem vyhlašují čtenářskou soutěž u příležit...


Co jsme před týdnem slíbili, je tady! IBM ve spolupráci s Computerworldem
vyhlašují čtenářskou soutěž u příležitosti středoevropského finále studentské
soutěže v programování ACM (o této akci jsme psali v minulém čísle CW).
Čtenáři mohou řešit libovolné ze dvou níže uvedených zadání v kterémkoli z
následujících jazyků: C norma ANSI, C++ norma ANSI, Pascal norma ISO, nebo
Java. Povoleny jsou pouze standardní knihovny.
Problém č. 1 průnik hyperkvádrů
Vaším úkolem je vytvořit klíčovou část navigačního systému kosmické lodi,
pohybující se hyperprostorem. Jedná se o utilitu, která vypočítává objem
průniku hyperprostorových kvádrů, jejichž hrany jsou rovnoběžné s hranami
pravoúhlého souřadného systému.
Specifikace vstupu: Vstup se skládá z N zadání. První řádek vstupního souboru
obsahuje přirozené číslo N. Dále následují jednotlivá zadání. Na prvním řádku
zadání jsou uvedena dvě celá čísla D a T oddělená mezerou, 2 ú D ú 1 000 000, 1
ú T ú 1 000 000. D je dimenze hyperkvádrů, T je počet jednotlivých hyperkvádrů.
Dále následuje T řádků, každý z těchto T řádků obsahuje 2D celých čísel. Každá
dvojice omezuje velikost hyperkvádru v jednom rozměru, tj. Xmin, Xmax, Ymin,
Ymax, Zmin, Zmax,...
Specifikace výstupu: Pro každé zadání musí výstup obsahovat právě jeden řádek,
na kterém je právě jedno celé číslo V objem průniku všech zadaných hyperkvádrů.
Problém č. 2 drak
Fraktální množiny můžeme jednoduše definovat jako množiny (bodů na obrazovce),
jejichž části se podobají celku. Příkladem takového fraktálu je tzv. drak.
Vznikne tak, že úzký proužek papíru přeložíme na polovinu, pak stejným způsobem
opět na polovinu atd. Celkový počet přeložení nazveme úrovní. Přeložený proužek
rozložíme tak, aby překladové hrany svíraly vždy úhel 90? a položíme takto
rozložený proužek papíru na stůl. Pro úroveň 0 až 4 vypadá drak takto:
Úseky takto vzniklé lomené čáry nazveme segmenty. Jednotlivé segmenty mají
stejnou jednotkovou délku. Pro úroveň L bude tedy počet segmentů 2L. Procházíme-
li po této lomené čáře z počátku [0,0], pak každý segment má určitý směr a
začíná na jisté souřadnici. Očíslujeme-li segmenty od 0, pak segment číslo 2
začíná na souřadnici [1,1] a směřuje na jih. Vaším úkolem je napsat program,
který pro zadané číslo segmentu určí souřadnice jeho počátku a směr, kterým
segment směřuje. Nultý segment začíná na souřadnici [0,0] a směřuje na sever.
Směry jsou značeny stejně jako obvykle na mapách, tj. nahoru je sever, dolů
jih, doleva západ a doprava východ.
Specifikace vstupu: První řádek obsahuje přirozené číslo N udávající počet úloh
k řešení. Dále následuje N řádků. Na každém řádku je vždy jedno přirozené číslo
z intervalu 0...1 000 000 000 udávající číslo segmentu, který nás zajímá.
Specifikace výstupu: Pro každou úlohu musí program vygenerovat právě jeden
řádek, který obsahuje jeden znak směru daného segmentu, souřadnici X a
souřadnici Y začátku daného segmentu navzájem oddělené mezerou. Znak určující
směr segmentu může být N, E, S nebo W N = sever (nahoru), E = východ (doprava),
S = jih (dolů), W = západ (doleva).
Zdrojový kód řešení zašlete nejpozději do 30. 11. 1998 na e-mailovou adresu
submit@contest.felk.cvut.cz (případně na adresu redakce). Z úspěšných řešení
budou vylosováni tři výherci, kteří získají některý z profesionálních
vývojových nástrojů nebo jiný software z dílny IBM (vymáhání výhry právní
cestou je vyloučeno). Výsledky zveřejníme v CW do konce letošního roku.(Maf)
8 2703 / Maf









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.