Meksikossa Jukatanin niemimaalla eläneillä Maya-intiaaneilla oli kehittynyt lukujärjestelmä, jossa luvut kirjoitettiinkin toisin kuin meillä. Laadi tietokoneohjelma, joka lukee syötteenään yhden luvun meille tutussa 10-järjestelmässä, ja tulostaa sen Maya-intiaanien tavalla.
Ohjelmasi lukee syötteensä tekstitiedostosta nimeltä
maya.in.
Tiedoston ainoa rivi koostuu yhdestä kokonaisluvusta n, joka on väliltä 0 ... 1 000 000 000 000 000 000.
Ohjelmasi kirjoittaa tulosteensa tekstitiedostoksi nimeltä
maya.out. Sen ainoana rivinä pitää olla syötteenä
annetun luvun n esitys seuraavalla
Maya-intiaanien tavalla:
0' eli nollana käytettiin
simpukankuoren kuvaa. Simpukankuoren ASCII-vastine olkoon
merkki '@'.1'...'19'
saatiin periaatteessa kirjoittamalla yhtä monta
pistettä. Pisteen ASCII-vastine olkoon
merkki '*'.
Mayat ottivat kuitenkin käyttöön vielä
lyhennysmerkinnän: 5 pisteen sijasta
piirretäänkin 1 pystyviiva. Pystyviivan ASCII-vastine
olkoon merkki "!".
Silloin kunkin numeromerkin sisällä korvataan niin monta pistettä viivoilla kuin mahdollista oikealta alkaen.
Esimerkiksi meidän lukuamme 13 vastaava ASCII-esitys on
***!!
koska 13=5+5+3 eli voimme käyttää enimmillään 2 pystyviivaa, ja sen jälkeen jäljelle jää vielä 3 pistettä. Ensin siis kirjoitetaan pisteet ja sitten pystyviivat.
Silloin esimerkiksi luvun 15 000 ASCII-esitys on
* **!!! !! @
koska 15 000 = 1*203 + 17*202 + 10*201 + 0*200, ja tyhjien rivien erottelemat luvut ovat vasemmalta lukien 1 (1 piste), 17 (2 pistettä ja 3 pystyviivaa), 10 (2 pystyviivaa) ja 0 (simpukka).
Kirjoita ohjelmasi lähdekooditiedostoksi nimeltä
maya.x missä x on käyttämäsi
ohjelmointikielen mukainen loppuliite.
Ohjelmasi saa kutakin testiä varten 1 sekunnin keskusyksikköaikaa ja 16 megatavua keskusmuistia.
Ohjelmaasi testataan 20 syötteellä. Saat kustakin testistä täydet 5 pistettä, jos ohjelmasi tulostaa syötettä vastaavan ASCII-esityksen resurssirajoja rikkomatta, ja muuten 0 pistettä.
Tämän tehtävän maksimi on siis 100 pistettä.
Tarkastellaan seuraavaa peliä:
Pelilautana on n rivin ja n sarakkeen kokoinen ruudukko, jonka jokainen ruutu on joko käytävää tai seinää.
Tässä labyrintissä vaeltaa yksi oma nappulasi, joka yrittää päästä sieltä ulos. Vastustajinasi on m kappaletta robottinappuloita, jotka yrittävät estää ulospääsysi.
Ensin on sinun siirtovuorosi.
Sitten jokainen roboteista tekee oman siirtonsa. Ne siirtyvät muuten samalla lailla kuin sinäkin, paitsi että
Näin peli jatkuu vuorotellen, kunnes jompi kumpi voittaa. Peli voi myös jatkua ikuisesti: nappulat voivat esimerkiksi jäädä kiertämään kehää.
Annettu pelitilanne on tylsä jos voisit ilmoittaa etukäteen sellaisen reitin, jota pitkin nappulasi pääsee pois laudalta, eivätkä robotit voi sitä estää, vaikka saivatkin kuulla reittisi etukäteen.
Tehtävänäsi on kirjoittaa ohjelma, joka ilmoittaa syötteenä annetusta pelitilanteesta, onko se tylsä vaiko ei.
Ohjelmasi lukee syötteensä tekstitiedostosta nimeltä
maze.in. Syöte kuvaa yhden pelitilanteen seuraavalla
tavalla.
Syötteen ensimmäisenä rivinä on kokonaisluku n joka ilmoittaa pelilaudan sivun pituuden. Se on väliltä 1 ... 1 000.
Sen jälkeen tiedostossa on vielä n riviä. Jokaisella rivillä on n merkkiä ennen rivinvaihtoa. Tämä n rivin ja n sarakkeen merkkiruudukko kuvaa laudan vastaavien ruutujen sisällöt seuraavasti:
#XR.Esimerkiksi seuraavassa kuvassa on 10*10 ruudun ruudukko, jossa on oman nappulasi lisäksi 2 robottia:
10 ########## #......... #.######## #.#......# #.#......# #.#.....R# #.#......# #.#..R...# #....X.... ##########
Tämä syöte on tylsä: Voisit ilmoittaa "Minun
nappulani X lähtee suoraan vasemmalle tunneliin!"
eikä kumpikaan robotti R saisi estettyä sen
pakoa.
(Jos olisitkin ilmoittanut "Minun nappulani X
lähtee suoraan oikealle kohden lähintä ulko-ovea!" niin
oikeanpuoleinen robotti olisi huomannut siitä, että sen
kannattaisi lähteä suoraan alas estämään pakoreittisi.)
Ohjelmasi kirjoittaa tulosteensa tekstitiedostoksi nimeltä
maze.out. Sen sisältönä täytyy olla yksi
kokonaisluku seuraavasti:
0.Kirjoita ohjelmasi lähdekooditiedostoksi nimeltä
maze.x missä x on käyttämäsi
ohjelmointikielen mukainen loppuliite.
Ohjelmasi saa kutakin testiä varten 1 sekunnin keskusyksikköaikaa ja 64 megatavua keskusmuistia.
Ohjelmaasi testataan 20 syötteellä. Kukin testi pisteytetään seuraavasti:
Tämän tehtävän maksimi on siis 100 pistettä.
90% kaikista testisyötteistä on tylsiä. 50% kaikista testisyötteistä on sellaisia, jossa n on korkeintaan 100.
Allaoleviin sääntöihin ja ohjeisiin voi ilmestyä lisäyksiä ja
selvennyksiä kisasivustolle osoitteessa
http://www.cs.helsinki.fi/matti.nykanen/datatahti/.
Seuraa siis sitä kilpailun kuluessa!
Kirjoita jokaisen tehtävän ratkaisu omaksi lähdekooditiedostokseen, jonka loppuliite x määräytyy sen ohjelmointikielestä seuraavasti:
| kieli | liite |
|---|---|
| C | c |
| C++ | cpp |
| Pascal | pas |
Aloita tiedosto kommentilla, jossa on seuraavat tiedot:
Datatähti 2006
-alkukilpailu"1 tai 2)Muuten tiedoston kirjoitusasu on vapaa.
Ohjelmasi on noudatettava seuraavia vaatimuksia, tai seurauksena saattaa olla pistemenetyksiä:
Erityisesti näppäimistöltä lukeminen tai näytölle tulostaminen on kiellettyä.
main
suorituksen pitää päättyä lauseeseen
return 0;.
(Ohjelmointikielessä Pascal sinun ei tarvitse huolehtia siitä, koska kääntäjä tekee sen puolestasi.)
-lm).Tehtävissä viitattiin seuraaviin resurssirajoihin:
Ohjelmat testataan sellaisella tietokoneella, jossa keskusyksikkönä on Intel Pentium 4 jonka kellotaajuus on 3,00GHz (5993,58 bogoMips). Sen perusteella voit yrittää arvioida, kuinka pitkä vastaava keskusyksikköaikaraja on omalla koneellasi.
(Testikoneen käyttöjärjestelmänä on Linux, ja keskusyksikköaika on sen ns. "user time".)
| kieli | kääntäjä | versio | kielistandardi (valitsimet) | Optimointitaso |
|---|---|---|---|---|
| C | gcc |
4.0.y | ANSI/ISO C89/90 (-ansi) |
-O2 -static |
| C++ | g++ |
4.0.y | ISO C++ (-ansi) |
-O2 -static |
| Pascal | Free Pascal | 2.0.z | Borland Turbo Pascal 7.0 (-Mtp -Sg) |
-O2 -XS |
Jos samalta henkilöltä tulee kilpailuaikana useita eri ratkaisuja, niin viimeinen niistä arvostellaan.
Jos kilpailija lähettää vastauksensa myöhästyneenä, niin järjestäjillä on oikeus jättää se huomiotta.
Palautukseen on useita eri tapoja.
Lähetä sähköpostiviestisi osoitteeseen matti.nykanen@cs.helsinki.fi.
Viestin rakenne on seuraava:
subject: teksti
"Datatähti 2006 -alkukilpailun vastaukset".Liitä tiedosto",
"Attach File" tai vastaava.)
Viestin katsotaan lähteneen ajoissa, jos sen aikaleima on kilpailuajan sisällä. Tämä aikaleima katsotaan viestin välittäneestä palvelinkoneesta.
Huomaa: Palauta ratkaisusi kirjeitse vain jos muut tavat eivät ole mahdollisia!
Valmista yksi 3,5 tuuman DOS-formatoitu levyke, jonka juurihakemistossa on seuraavat tiedostot:
contents.txt, joka
sisältää samat yhteystietosi kuin
sähköpostiviestin runkoon vaadittiin.Laita (mielellään pehmustettuun) kirjekuoreen levykkeen
lisäksi tämä tiedosto contents.txt tulostettuna
paperille (siltä varalta, että levykkeesi hajoaakin matkalla).
Lähetä kirje seuraavaan osoitteeseen:
(Levykettä ei palauteta.)
Kirjeen katsotaan lähteneen ajoissa, jos sen postileima on kilpailuajan sisällä. Huomaa: Postin käsittelyn hitauden vuoksi tämä tarkoittaa käytännössä sitä, että kirje on postitettava jo hyvissä ajoin ennen kilpailuajan viimeistä iltaa!
Järjestäjät suunnittelevat erillisen verkkopalvelun perustamista ratkaisujen vastaanottamiseksi. Jos verkkopalvelu saadaan toimintaan, niin siitä ilmoitetaan kisasivustolla.
Voit esittää täsmennyskysymyksiä algoritmitehtävistä sähköpostitse tai kirjeitse. Käytä edellä annettuja vastausten palautusosoitteita.
Kysymykset ja vastaukset laitetaan näkyviin kisasivustolle. Kirjeitse esitettyihin kysymyksiin lähetetään myös henkilökohtainen vastaus.
Viimeinen päivä lähettää kysymyksiä on
jotta niihin ehditään vastata vielä maanantaina 14.11.2005.
Myöhemmin lähetettyihin kysymyksiin järjestäjät eivät valitettavasti voi enää luvata vastausta kilpailuajan kuluessa.