Vuoden 2001 alkukilpailun ensimmäisessä ohjelmointitehtävässä pitää tehdä ohjelma, jonka avulla voidaan verrata kahta DNA-sekvenssiä ja laskea niiden "samanlaisuus". DNA-sekvenssejä ajatellaan tässä tehtävässä merkkijonoiksi, jotka koostuvat kirjaimista A (adeniini), C (sytosiini), T (tymiini) ja G (guaniini).
DNA-sekvenssien "samuudella" halutaan ilmaista niiden operaatioiden vähyyttä (ja harvinaisuutta), joita evoluutio on kohdistanut DNA-sekvensseihin.
Tässä ongelmassa ajatellaan, että DNA-sekvensseihin voi kohdistua neljänlaisia operaatioita:
Edelliset operaatiot vaikuttavat johonkin sekvenssin tai sekvenssien osaan. Mihin tahansa sekvenssin kirjaimeen voi kohdistua vain yksi operaatio. Erityisesti, peilikuvan mihinkään merkkiin ei voi kohdistua muita operaatioita.
Kullakin edellisistä operaatioista on kustannus: yhden merkin lisäyksellä, poistolla ja muuttumisella toiseksi sekä mielivaltaisen pituisella peilauksella on kustannus 1 (yksi).
Tehtävässä on on annettuna kaksi DNA-sekvenssiä R[1...r] ja S[1...s] ja sinun tulee laskea sekvenssien samuusarvo, joka on minimaalinen kustannus edellä kuvattuja operaatioita kohdistettuna R:ään niin, että R muuttuu sekvenssiksi S. (Minimaalinen kustannus R:n muuttamiseksi S:ksi on aina sama kuin minimaalinen kustannus S:n muuttamiseksi R:ksi.)
Esimerkiksi sekvenssien CATTGTGCAT ja TTACGATGCCT samuusarvo on 3, joka saadaan soveltamalla seuraavia operaatioita:
Ohjelmasi tulee lukea syötteensä oletushakemiston tekstitiedostosta DNACMP.IN. Tiedoston sisältö on seuraava:
Ohjelmasi tulosteena tulee olla oletushakemistossa tekstitiedosto DNACMP.OUT. Tiedoston loppua pitää edeltää rivinvaihto, mutta muuten tiedostossa ei saa olla muita rivinvaihtoja ja välilyöntejä kuin mitä alla on sanottu.
Jos tiedostossa DNACMP.IN on
10 11 5 CATTGTGCAT TTACGATGCCT
jolloin tulos on DNACMP.OUT:
3 M 1 4 CATT -> TTAC - 5 G I A - 6 T - 7 G - 8 C R 9 A -> C - 10 T
Toinen esimerkki, DNACMP.IN:
5 4 3 CAAGT AACT
jolloin tulos on DNACMP.OUT:
2 M 1 3 CAA -> AAC D 4 G - 5 T
Tehtävän ratkaisuna sinun pitää palauttaa asianmukaisesti kommentoitu lähdekielinen ohjelma. Sallittuja ohjelmointikieliä ovat Pascal, C ja C++. Laita ohjelmasi alkuun kommentiksi yhteystietosi ja mahdolliset ohjeet ohjelman kääntämistä varten. Ohjelmalla pitää olla vain edellä määritellyt syötteet ja tulosteet. Erityisesti sen ei pidä lukea mitään näppäimistöltä tai tulostaa mitään näyttöruudulle.
Arvosteluvaiheessa ohjelmasi käännetään (Unix-ympäristössä) ja suoritetaan useilla erilaisilla testisyötteillä. Pisteitä saa käännetyn ohjelman oikeasta ja nopeasta toiminnasta joukolla testisyötteitä. Lähdekielistä ohjelmaa ei siis arvostella, kunhan vain sen käännös onnistuu. Siirrettävyysongelmien välttämiseksi pitäydy kielen peruspiirteissä.
Testausympäristössä on kääntäjinä käytettävissä ainakin GNU C/C++ ja Pascal sekä Free Pascal (jonka pitäisi olla Turbo Pascal -yhteensopiva). Käännökset tehdään kääntäjien oletusarvoisilla optioilla. Jos käytät ohjelmien tekemiseen Turbo Pascal:a tai C++:aa, kerro se palauttaessasi ohjelmaa. Jos käytettävissä olevista kielen piirteistä tms. on epäselvyyttä, kysy asiasta sähköpostitse. Seuraa myös sivua http://www2.cs.utu.fi/datatahti/DTalku-01/tiedoituksia.htm, jolle tarpeen mukaan tulee tiedoituksia koskien tehtäviä.
Testisyötteistä osa testaa vain ohjelman oikeellisuutta. Kustakin tällaisesta syötteestä saa tietyn määrän pisteitä, jos ohjelma tuottaa oikean tulosteen kohtuullisessa ajassa. Syötteiden koot ja aikarajat valitaan siten, että hitaallakin ohjelmalla saa pisteitä, kunhan se on muuten toimiva. Osa testisyötteistä testaa ohjelman tehokkuutta. Näillä syötteillä ohjelman saama pistemäärä vähenee sitä mukaa, kun suoritusaika kasvaa. Testisyötteet ovat aina tarkalleen ylläolevan kuvauksen mukaisia. Pisteytyksen yksityiskohtia ja tarkkoja aikarajoja ei tässä vaiheessa julkisteta. Vertailukohdaksi voidaan kuitenkin antaa, että tehtävän laatijan ratkaisu vaatii alle 500 kilotavua muistia ja vie suurimmilla testisyötteillä alle yhden sekunnin suoritusaikaa (GNU C, Linux, 667 MHz Pentium III).
Palauta ratkaisusi mieluiten sähköpostiviestinä osoitteeseen Ville.Leppanen@cs.utu.fi. Älä käytä yli 80 merkin rivejä! Voit myös toimittaa ratkaisusi 3,5 tuuman DOS-formatoidulla levykkeellä osoitteeseen
Pakkaa levyke huolellisesti ja laita mielellään toinen samansisältöinen mukaan varmuuskopioksi. Talleta ohjelmasi juurihakemistoon nimellä dt2001a.pas, dt2001a.c tai dt2001a.cpp.
Alkukilpailun toisessa ohjelmointitehtävässä pitää tehdä ohjelma, jonka avulla muodostetaan ns. taikaneliö.
Tässä tehtävässä taikaneliöllä tarkoitetaan nxn -muotoista numeroista koostuvaa neliötä, johon on sijoiteltu numerot 1, 2, ..., n*n (kukin numero esiintyy tasan kerran) ja jolle on voimassa seuraava: kunkin vaakarivin alkioiden summa on sama ja lisäksi kunkin pystyrivin alkioiden summa on sama. (Yleisesti, mutta ei tässä tehtävässä, taikaneliöissä vaaditaan vielä päädiagonaaleistakin samaa.)
Taikaneliö on tiettävästi olemassa kaikille neliön sivun koon arvoille n paitsi arvolle n=2. Triviaalisti 1 muodostaa tällaisen taikaneliön. Tapauksessa n=3 eräs taikaneliö on seuraava:
| 4 | 3 | 8 |
| 9 | 5 | 1 |
| 2 | 7 | 6 |
jonka kunkin vaaka- ja pystyrivin alkioiden summa on 15 (tässä tapauksessa myös kummallakin diagonaalilla olevien alkioiden summa on 15). Tapauksessa n=4 eräs taikaneliö on seuraava:
| 4 | 14 | 15 | 1 |
| 5 | 11 | 10 | 8 |
| 12 | 7 | 6 | 9 |
| 13 | 2 | 3 | 16 |
Nyt vaaka- ja pystyriveillä olevien alkioiden summa on 34 (mutta diagonaaleilla olevien alkioiden summa ei enää ole 34; on mahdollista tehdä sellainen 4x4-taikaneliö, jolle diagonaalialkioiden summa on myös 34).
Tässä tehtävässä sinun pitää tehdä ohjelma, joka muodostaa nxn-taikaneliön annetun sivun koon n ja joidenkin ruutuihin valmiiksi "sijoitettujen" arvojen perusteella.
Valmiiksi sijoitettuja arvoja ei saa muuttaa. Tehtävällä on aina vähintään yksi ratkaisu. Sinun ohjelmasi tulee löytää mikä tahansa ratkaisuista.
Esimerkiksi, jos annettuna olisi n=5 ja alla olevat numerot
| ?? | 6 | ?? | 5 | 12 |
| 9 | ?? | 15 | 16 | ?? |
| ?? | 20 | ?? | ?? | 21 |
| ?? | 4 | 17 | 23 | 10 |
| 25 | ?? | 1 | ?? | 19 |
voisi tuloksena olla seuraava taikaneliö:
| 18 | 6 | 24 | 5 | 12 |
| 9 | 22 | 15 | 16 | 3 |
| 2 | 20 | 8 | 14 | 21 |
| 11 | 4 | 17 | 23 | 10 |
| 25 | 13 | 1 | 7 | 19 |
Ohjelmasi tulee lukea syötteensä oletushakemiston tekstitiedostosta SQUARE.IN. Tiedoston sisältö on seuraava:
Neliön indeksointi on [1...n][1...n], eli 1 <= xi, yi <= n.
Ohjelmasi tulosteena tulee olla oletushakemistossa tekstitiedosto SQUARE.OUT. Tiedoston loppua pitää edeltää rivinvaihto, mutta muuten tiedostossa ei saa olla muita rivinvaihtoja ja välilyöntejä kuin mitä alla on sanottu.
Tiedosto koostuu n:stä rivistä. Kullakin rivillä on tulostettuna n taikaneliön lukua. Ensimmäisellä rivillä on taikaneliön ensimmäisen rivin luvut, toisella toisen rivin luvut, jne. Kunkin rivin alkiot tulostetaan järjestyksessä kolmen merkin mittaiseen kenttään niin, että luku tulostuu kentän oikeaan laitaan ja sitä edeltää tarpeellinen määrä välilyöntejä.
Jos tiedostossa SQUARE.IN on
4 8 1 2 14 1 3 15 2 3 10 3 2 7 3 4 9 4 4 16 4 2 2 2 2 11
kelpaa tulokseksi SQUARE.OUT:
4 14 15 1 5 11 10 8 12 7 6 9 13 2 3 16
Tehtävän ratkaisuna sinun pitää palauttaa asianmukaisesti kommentoitu lähdekielinen ohjelma. Sallittuja ohjelmointikieliä ovat Pascal, C ja C++. Laita ohjelmasi alkuun kommentiksi yhteystietosi ja mahdolliset ohjeet ohjelman kääntämistä varten. Ohjelmalla pitää olla vain edellä määritellyt syötteet ja tulosteet. Erityisesti sen ei pidä lukea mitään näppäimistöltä tai tulostaa mitään näyttöruudulle.
Arvosteluvaiheessa ohjelmasi käännetään (Unix-ympäristössä) ja suoritetaan useilla erilaisilla testisyötteillä. Pisteitä saa käännetyn ohjelman oikeasta ja nopeasta toiminnasta joukolla testisyötteitä. Lähdekielistä ohjelmaa ei siis arvostella, kunhan vain sen käännös onnistuu. Siirrettävyysongelmien välttämiseksi pitäydy kielen peruspiirteissä.
Testausympäristössä on kääntäjinä käytettävissä ainakin GNU C/C++ ja Pascal sekä Free Pascal (jonka pitäisi olla Turbo Pascal -yhteensopiva). Käännökset tehdään kääntäjien oletusarvoisilla optioilla. Jos käytät ohjelmien tekemiseen Turbo Pascal:a tai C++:aa, kerro se palauttaessasi ohjelmaa. Jos käytettävissä olevista kielen piirteistä tms. on epäselvyyttä, kysy asiasta sähköpostitse. Seuraa myös sivua http://www2.cs.utu.fi/datatahti/DTalku-01/tiedoituksia.htm, jolle tarpeen mukaan tulee tiedoituksia koskien tehtäviä.
Testisyötteistä osa testaa vain ohjelman oikeellisuutta. Kustakin tällaisesta syötteestä saa tietyn määrän pisteitä, jos ohjelma tuottaa oikean tulosteen kohtuullisessa ajassa. Syötteiden koot ja aikarajat valitaan siten, että hitaallakin ohjelmalla saa pisteitä, kunhan se on muuten toimiva. Osa testisyötteistä testaa ohjelman tehokkuutta. Näillä syötteillä ohjelman saama pistemäärä vähenee sitä mukaa, kun suoritusaika kasvaa. Testisyötteet ovat aina tarkalleen ylläolevan kuvauksen mukaisia. Pisteytyksen yksityiskohtia ja tarkkoja aikarajoja ei tässä vaiheessa julkisteta. Ohjelmallesi tullaan antamaan aikaa joissakin tapauksissa vähintään 20 sekuntia (Linux, 667 MHz Pentium III).
Palauta ratkaisusi mieluiten sähköpostiviestinä osoitteeseen Ville.Leppanen@cs.utu.fi. Älä käytä yli 80 merkin rivejä! Voit myös toimittaa ratkaisusi 3,5 tuuman DOS-formatoidulla levykkeellä osoitteeseen
Pakkaa levyke huolellisesti ja laita mielellään toinen samansisältöinen mukaan varmuuskopioksi. Talleta ohjelmasi juurihakemistoon nimellä dt2001b.pas, dt2001b.c tai dt2001b.cpp.