Datatähti 2006: Alkukilpailu
Tehtävä 1: Mayojen numerot
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.
1.1. Syöttö
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.
1.2. Tulostus
Ohjelmasi kirjoittaa tulosteensa tekstitiedostoksi nimeltä maya.out. Sen ainoana rivinä pitää olla syötteenä annetun luvun n esitys seuraavalla Maya-intiaanien tavalla:
Maya-intiaanit käyttivätkin peräti 20 erilaista numeromerkkiä, eikä vain 10 kuten meillä.
Peräkkäisten numeromerkkien väliin jätettiin tilaa. Tilan ASCII -vastine olkoon yksi välilyöntimerkki.
Numeromerkkinä '0' eli nollana käytettiin simpukankuoren kuvaa. Simpukankuoren ASCII-vastine olkoon merkki '@'.
Muut numeromerkit '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).
1.3. Pisteytys
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ä.
Tehtävä 2: Sonic the Screwdriver
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.
Jos nappulasi on nyt laudan reunaruudussa, niin voit siirtää sen pois laudalta, ja olet voittanut pelin.
Muuten voit siirtää oman nappulasi mihin tahansa naapuriruutuun, kunhan siinä ei ole seinää eikä robottia. Vinoittain et kuitenkaan saa siirtää, joten mahdollisia naapuriruutuja on aina korkeintaan 4 kappaletta.
Voit myös pitää nappulasi paikoillaan sen nykyisessä ruudussa, jos niin haluat.
Sitten jokainen roboteista tekee oman siirtonsa. Ne siirtyvät muuten samalla lailla kuin sinäkin, paitsi että
jos jokin robotti pystyy siirtymään samaan ruutuun, jossa oma nappulasi nyt on, niin se vangitsee nappulasi, ja häviät pelin
robotti ei koskaan siirry pois laudalta.
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.
2.1. Syöttö
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:
Tässä ruudussa on seinä.
Tässä ruudussa on oma nappulasi. Näitä merkkejä on tasan yksi kappale syötteessä.
Tässä ruudussa on jokin roboteista.
Tässä ruudussa on käytävä, jossa ei tällä hetkellä seiso yhtään nappulaa.
Esimerkiksi seuraavassa kuvassa on 10*10 ruudun ruudukko, jossa on oman nappulasi lisäksi 2 robottia:
#.#......#
#.#.....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.)
2.2. Tulostus
Ohjelmasi kirjoittaa tulosteensa tekstitiedostoksi nimeltä maze.out. Sen sisältönä täytyy olla yksi kokonaisluku seuraavasti:
Jos syötteenä saatu pelitilanne on tylsä, niin tulostuksena pitää olla pienin askelmäärä, jolla nappulasi pääsee pois laudalta sellaista reittiä pitkin, jota robotit eivät pysty estämään. Esimerkiksi edellisessä esimerkkisyötteessä tämä tulostettava luku on 20.
Jos taas syötteenä saatu pelitilanne ei olekaan tylsä, niin tulostetaankin luku 0.
2.3. Pisteytys
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:
Jos syöte on tylsä, ja ohjelmasi antaa sille täysin oikean vastauksen resurssirajoja rikkomatta, niin se saa täydet 5 pistettä.
Jos syöte on tylsä, mutta ohjelmasi löytää turhan pitkän reitin resurssirajoja rikkomatta, niin se saa vain 2 pistettä.
Jos syöte ei olekaan tylsä, ja ohjelmasi havaitsee sen resurssirajoja rikkomatta, niin se saa täydet 5 pistettä.
Muuten ohjelmasi saa 0 pistettä.
90% kaikista testisyötteistä on tylsiä. 50% kaikista testisyötteistä on sellaisia, jossa n on korkeintaan 100.
3. Sääntöjä ja ohjeita
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!
3.1. Lähdekooditiedosto
Kirjoita jokaisen tehtävän ratkaisu omaksi lähdekooditiedostokseen, jonka loppuliite x määräytyy sen ohjelmointikielestä seuraavasti:
Aloita tiedosto kommentilla, jossa on seuraavat tiedot:
otsikkoteksti "Datatähti 2006 -alkukilpailu"
tehtävän numero (1 tai 2)
oma syntymäaikasi
Muuten tiedoston kirjoitusasu on vapaa.
Ohjelmasi on noudatettava seuraavia vaatimuksia, tai seurauksena saattaa olla pistemenetyksiä:
Ohjelma saa lukea ja kirjoittaa vain tehtävässä nimettyjä tiedostoja.
Erityisesti näppäimistöltä lukeminen tai näytölle tulostaminen on kiellettyä.
Tulostiedoston täytyy aina päättyä rivinvaihtoon.
Ohjelmointikielissä C ja C++ pääohjelman main suorituksen pitää päättyä lauseeseen return 0;.
(Ohjelmointikielessä Pascal sinun ei tarvitse huolehtia siitä, koska kääntäjä tekee sen puolestasi.)
Ohjelmointikielessä pitää rajoittua vain sen standardoituihin peruspiirteisiin, ja välttää laite- tai kääntäjäkohtaisia erikoisuuksia.
Ohjelmointikielissä C ja C++ on käytössä standardoitu matematiikkakirjasto (eli käännettäessä annetaan valitsin -lm).
Ohjelmointikielessä C++ on käytössä myös kirjasto Standard Template Library (STL), koska se on osa kielen standardia.
3.2. Resurssirajat
Tehtävissä viitattiin seuraaviin resurssirajoihin:
käsittää kaiken muun ohjelmasi käyttämän muistin paitsi sen suorituskelpoista ohjelmakoodia.
Keskusyksikköaika
sisältää sen ajan, jonka tietokoneen keskusyksikkö käyttää suorittaessaan sinun omaa ohjelmakoodiasi sekä sen kutsumia kirjastoaliohjelmia. Se ei sisällä sitä aikaa, jonka keskusyksikkö käyttää suorittaessaan käyttöjärjestelmäpalveluita, kuten tiedostojen avaamisia ja sulkemisia.
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".)
3.3. Käytetyt kääntäjät
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
3.4. Ratkaisujen palautus
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.
3.4.1. Sähköpostitse
Lähetä sähköpostiviestisi osoitteeseen matti.nykanen@cs.helsinki.fi. Viestin rakenne on seuraava:
Kirjoita otsikkokenttään subject: teksti "Datatähti 2006 -alkukilpailun vastaukset".
Kirjoita viestin rungoksi omat yhteystietosi:
Kumpikin lähdekooditiedosto liitetään tähän viestiin omana MIME-liitteenään. (Sähköpostiohjelmissa tämän toiminnon nimi on yleensä "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.
3.4.2. Kirjeitse
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:
ratkaisujen lähdekooditiedostot
tekstitiedosto nimeltä 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!
3.4.3. Verkkopalvelun kautta
Järjestäjät suunnittelevat erillisen verkkopalvelun perustamista ratkaisujen vastaanottamiseksi. Jos verkkopalvelu saadaan toimintaan, niin siitä ilmoitetaan kisasivustolla.
3.5. Kysymys- ja vastauspalsta
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
sunnuntaina 13.11.2005
tiistaina 8.11.2005
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.
Nämä algoritmitehtävät on laatinut