Viikko 1: TMC-tehtävät

Tehtävien deadline: keskiviikkona 27.01 23:59.

Huomaathan viikkoon liittyvän lisämateriaalin. Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta mainita.

Tehtävä 1

Saat syötteenä merkkijonon s, joka koostuu merkeistä A..Z, sekä kirjaimen c. Tehtävänäsi on laskea kuinka monta kertaa kirjain c esiintyy merkkijonossa s.

Toteutus

Toteuta metodi int laske(String s, char c), joka laskee kirjaimen c esiintymismäärän merkkijonossa s

Syötteenä olevan merkkijonon pituus on korkeintaan 105.

Esimerkit

Tehtävä 2

Lue lisämateriaalista summataulukosta kertova osa.

Toteutus

Tehtävänäsi on toteuttaa tehtäväpohjan mukana tulevaan luokkaan Summataulukko metodit Summataulukko(long[] taulukko) ja long summa(int l, int r), jotka hoitavat summataulukon luonnin ja välin summan kyselyn. Voit olettaa, että r on vähintään yhtäsuuri kuin l. Lisäksi l ja r pysyvät aina taulukon rajojen sisällä.

Taulukon alkioita on korkeintaan 105, ja ne ovat kaikki välillä -109..109. Testit tarkastavat toteutuksesi tehokkuuden, metodia summa kutsutaan korkeintaan 105 kertaa yhden taulukon kohdalla.

Huomaathan, että tavalliseen 32-bittiseen int-muuttujaan ei pysty tallentamaan tarpeeksi suuria lukuja tämän tehtävän ratkaisemiseksi. Käytäthän siis long-tyyppisiä muuttujia!

Tehtävä 3

Lue lisämateriaalista tehokkuudesta kertova osa.

Olet saanut kaksi kuvaa pyöreästä pöydästä ja yrität selvittää, ovatko kuvat mahdollisesti samasta pöydästä. Ainoa tuntomerkki, josta arvelet olevan apua pöytien erottamiseen, on pöydän reunalle kirjoitetut luvut, jotka kiertävät pöydän reunaa mukaillen pöydän ympäri. Kummassakin kuvassa pöytiin on kirjoitettu luvut 1..n, missä n on enintään 105. Olet kirjoittanut kummankin pöydän numerot muistiin valitsemalla ensin jonkin mielivaltaisen luvun pöydän reunalta, ja sitten kirjoittamalla kaikki luvut valitusta luvusta alkaen myötäpäivään. Ohjelmasi saa syötteenä muistiinpanosi.

Toteutus

Toteuta metodi boolean ovatkoSamat(int[] a, int[] b), jonka tulee palauttaa true, jos on mahdollista, että taulukoiden kuvaamat pöydät ovat samat ja false, jos pöytien on oltava erilaiset pelkästään annettujen tietojen perusteella.

Esimerkit

Tehtävä 4

Lue lisämateriaalista binäärihausta kertova osa.

Syrjäiselle vuoristopolulle ollaan rakentamassa lepoalueita, jotta matkaajat selviäisivät raskaasta vaelluksesta. Byrokratiasyistä lepopaikkoja ei voida kuitenkaan rakentaa aivan vapaasti, vaan ne on pakko rakentaa tasavälein. Tehtävänäsi on selvittää miten harvasti lepoalueet voidaan rakentaa.

Vuoristopolku jakautuu n etappiin. Saat syötteenä taulukon int[] polku, jonka pituus on n. Taulukko sisältää jokaisesta etapista tiedon siitä, miten paljon etapin läpi kulkevan matkaajan energiataso muuttuu. Jos energiataso tippuisi negatiiviseksi seuraavan etapin aikana, ei matkaa pystytä jatkamaan. Matkan alussa energiataso on aina 1000, mutta se voi matkan aikana nousta korkeammallekin.

Matkantekoa voi helpottaa rakentamalla lepopaikkoja, joihin saapuessaan matkaajan energiataso nousee 1000 energiayksikköä. Lepopaikat on rakennettava tasavälein, mikä tarkoittaa sitä, että jos ensimmäiseen lepopaikkaan saavutaan kun on kuljettu x etappia, niin seuraava lepopaikka on siitä x etapin päässä, ja sitä seuraava taas x etapin päässä jne... Viimeisen lepopaikan ja polun lopun välillä ei kuitenkaan tarvitse olla x etappia, eli lepopaikkojen kuuluu olla tasavälein alusta lähtien, muttei lopusta lähtien.

Esimerkiksi jos polkua vastaava taulukko on

-500, -500, -100, -900, -600, -500 
            

Edellisen esimerkin polun tapauksessa lepopaikkoja pitäisi rakentaa joka etapin jälkeen, jotta polku olisi mahdollista kulkea.

Toteutus

Toteuta seuraava metodi:

int harvinVali(int[] polku)

Metodin tulee palauttaa suurin kokonaisluku x, siten että vuoripolku on mahdollista kulkea kokonaan, kun lepopaikkoja on rakennettu x etapin välein. Voit olettaa, että polkua ei ole mahdollista kulkea ilman yhtään lepopaikkaa.

Taulukon polku pituus on korkeintaan 105. Sen sisältämät luvut ovat välillä -1000..1000, joten polku on mahdollista kulkea ainakin siinä tapauksessa, että lepopaikkoja rakennetaan jokaisen etapin jälkeen. Kuten syötteen rajoista huomaa, energia voi myös lisääntyä etapin aikana.

Esimerkit

Tehtävä 5

Saat syötteenä taulukon aidosti positiivisia lukuja ja luvun k. Tehtävänäsi on selvittää sellaisten taulukon välien lukumäärä, joihin kuuluvien lukujen summa on tasan k.

Toteutus

Toteuta seuraava metodi:

int valienMaara(long[] taulukko, long k)

Taulukon pituus on korkeintaan 105 ja luku k on korkeintaan 1018. Taulukossa olevat luvut ovat välillä 1..109.

Huomaathan, että tavalliseen 32-bittiseen int-muuttujaan ei pysty tallentamaan tarpeeksi suuria lukuja tämän tehtävän ratkaisemiseksi. Käytäthän siis long-tyyppisiä muuttujia!

Esimerkit