Lähetä tehtävien ratkaisut viimeistään 10.1.2010 sähköpostitse osoitteeseen antti.laaksonen@mbnet.fi. Jos et ehdi tehdä kaikkia tehtäviä, lähetä vain osa ratkaisuista.
Voit käyttää ratkaisuissa C-, C++- ja Pascal-kieliä samaan tapaan kuin Datatähti-alkukilpailussa. Lähetä pelkkä ohjelman lähdekoodi, jonka alussa lukee kommentissa oma nimesi.
Jokaisen ohjelman nimi lukee tehtävän otsikon perässä. Esimerkiksi ensimmäisessä tehtävässä ohjelman nimi on ohjelmointikielestä riippuen fibo.c, fibo.cpp tai fibo.pas. Syöte- ja tulostiedostojen nimet ovat vastaavasti fibo.in ja fibo.out.
Jokaisen ohjelman käytössä on 1 sekunti suoritusaikaa ja 100 Mt keskusmuistia. Ohjelmat suoritetaan tietokoneella, jonka suorittimen kellotaajuus on 3 GHz.
Kaikki tehtävissä mainitut luvut ovat kokonaislukuja. Ohjelman ei tarvitse varautua virheellisiin tai järjettömiin syötteisiin.
Jos tehtävissä on epäselvyyksiä, voit kysyä niistä lähettämällä sähköpostia yllä mainittuun osoitteeseen.
Fibonaccin luvut voidaan määritellä seuraavasti:
Määritelmän mukaan kaksi ensimmäistä Fibonaccin lukua annetaan suoraan ja muulloin Fibonaccin luku saadaan laskemalla yhteen kaksi edellistä Fibonaccin lukua. Kymmenen ensimmäistä Fibonaccin lukua ovat siis 0, 1, 1, 2, 3, 5, 8, 13, 21 ja 34.
Kirjoita ohjelma, joka laskee funktion F(n) arvon, kun n on positiivinen kokonaisluku ja korkeintaan 5000. Ohjelma lukee syötetiedostosta arvon n ja kirjoittaa tulostiedostoon vastaavan Fibonaccin luvun.
7
13
Porrassanan jokainen kirjain on aakkosissa edellisen kirjaimen vieressä. Toisin sanoen jos merkkijonossa esiintyy jossain kohtaa kirjain P, sen jälkeen voi tulla joko O tai Q. Porrassanan alussa ja lopussa voi olla mikä tahansa kirjain. Esimerkiksi porrassanoja ovat ABC, JKLMLKJIHGHIJ ja XYXYZYXWV.
Ohjelma lukee syötetiedostosta sanan pituuden ja kirjoittaa tulostiedostoon, mikä on viimeinen numero siinä luvussa, joka ilmaisee, kuinka monta niin pitkää porrassanaa voidaan muodostaa englannin kielen aakkosista (A–Z). Annettu sanan pituus on korkeintaan 10000 kirjainta.
Esimerkiksi kymmenkirjaimisia porrassanoja on kaikkiaan 11304. Niinpä ohjelma kirjoittaa tiedostoon numeron 4.
10
4
Leveä aita muodostuu laudoista, joiden korkeudet vaihtelevat. Nyt aitaan halutaan kiinnittää suorakulmion muotoinen mainos, jonka pinta-ala pyritään saamaan mahdollisimman suureksi. Mainos täytyy kiinnittää niin, että sen takana on aitaa jokaisessa kohdassa.
Seuraavissa kuvissa näkyvät mainokseton aita sekä sama aita mainoksen kiinnityksen jälkeen. Tämän mainoksen pinta-ala on 12, eikä aitaan mahdukaan tätä suurempaa mainosta.
# # # #
# #### # # MMMM #
# ##### ## # #MMMM ##
########## ###MMMM###
Kirjoita ohjelma, joka ilmoittaa suurimman mainoksen pinta-alan aidan lautojen pituuksien perusteella. Aidassa on korkeintaan 500000 lautaa, ja jokaisen laudan korkeus on enintään 1000.
Syötetiedostossa lukee aidan lautojen määrä sekä kunkin laudan korkeus. Ohjelman täytyy kirjoittaa tulostiedostoon suurimman mainoksen pinta-ala.
10 3 1 2 3 3 4 3 1 4 2
12
Murtoluvun 1/2/3/4 voi tulkita viidellä tavalla suluista riippuen:
Tehtävänä on ilmoittaa annetusta murtoluvusta, voiko sen ympärille laittaa sulkuja niin, että lopputulos on kokonaisluku. Yllä olevassa esimerkissä tällainen sulutus on mahdollinen, nimittäin 1/((2/3)/4) = 6.
Syötetiedoston ensimmäisellä rivillä lukee murtoluvun osien määrä (korkeintaan 1000). Syötetiedoston toisella rivillä ilmoitetaan kaikki murtoluvun osat. Kaikki osat ovat positiivisia kokonaislukuja ja pienempiä kuin 1000000.
Ohjelman täytyy kirjoittaa tulostiedostoon kirjain K, jos murtoluku on kokonaisluku sopivasti sulutettuna, ja muuten kirjain E.
4 1 2 3 4
K
2 1 3
E
Tarkastellaan ruudukkoa, jonka jokaisessa ruudussa on kokonaisluku:
| -4 | 3 | -1 | 1 | -1 |
| 5 | -7 | 5 | 2 | 2 |
| 0 | 2 | -2 | -4 | -5 |
| 1 | 2 | 3 | 4 | -2 |
Tehtävänä on etsiä ruudukon sisältä aliruudukko, jossa olevien lukujen summa on mahdollisimman suuri. Tässä tapauksessa suurin summa on 11 seuraavassa aliruudukossa:
| -4 | 3 | -1 | 1 | -1 |
| 5 | -7 | 5 | 2 | 2 |
| 0 | 2 | -2 | -4 | -5 |
| 1 | 2 | 3 | 4 | -2 |
Vastaavasti seuraavissa aliruudukoissa summat ovat 1 ja -2:
| -4 | 3 | -1 | 1 | -1 |
| 5 | -7 | 5 | 2 | 2 |
| 0 | 2 | -2 | -4 | -5 |
| 1 | 2 | 3 | 4 | -2 |
| -4 | 3 | -1 | 1 | -1 |
| 5 | -7 | 5 | 2 | 2 |
| 0 | 2 | -2 | -4 | -5 |
| 1 | 2 | 3 | 4 | -2 |
Syötetiedoston ensimmäisellä rivillä lukee ruudukon korkeus ja leveys. Tämän jälkeen tiedostossa ovat kaikki ruudukon luvut rivi kerrallaan. Ruudukon korkeus ja leveys ovat korkeintaan 500, ja ruudukon luvut ovat välillä -1000...1000.
Ohjelman täytyy kirjoittaa tulostiedostoon, mikä on suurin summa ruudukon aliruudukossa. Aliruudukossa täytyy olla ainakin yksi ruutu.
4 5 -4 3 -1 1 -1 5 -7 5 2 2 0 2 -2 -4 -5 1 2 3 4 -2
11
Palindromi on merkkijono, joka on sama alusta loppuun ja lopusta alkuun luettuna. Tehtävänä on etsiä pisin merkkijonon osana oleva palindromi.
Esimerkiksi pisin merkkijonon MAALAISTALO osana oleva palindromi on ALA. Vastaavasti pisin merkkijonon PAJUPILLI osana oleva palindromi on ILLI.
Syötetiedoston ainoalla rivillä on tutkittava merkkijono, joka muodostuu englannin kielen aakkosista A–Z ja jossa on korkeintaan 5000000 kirjainta.
Ohjelman täytyy kirjoittaa tulostiedostoon, kuinka monta kirjainta on pisimmässä merkkijonon osana olevassa palindromissa.
MAALAISTALO
3