Viikko 10: TMC-tehtävät

TMC viikko 10

Viikon tavoitetehtävämäärä 4 tehtävää

Tehtävien deadline: sunnuntaina 26.11. 23:59

Viikon tehtävien teemana on erityisesti syklit ja topologinen järjestäminen, ja lisäksi edellisen viikon teema jatkuu osittain. Verkoissa voi olla useita kaaria samojen solmujen välillä.

Tehtävä 1

Saat syötteenä suunnatun verkon. Tehtävänäsi on selvittää, onko verkossa sykliä.

Toteutus

Toteuta seuraava metodi:

boolean onkoSyklia(int n, int[] mista, int[] minne)

Parametri n on solmujen määrä, kokonaisluku välillä 1..10⁵. Solmut on numeroitu 1..n.

Taulukot mista ja minne kuvaavat kaaret solmujen välillä ja näitä kaaria on enintään 10⁵. Kaaret ovat edelliseen viikkoon eroten yksisuuntaisia.

Metodin tulee palauttaa true jos verkossa on sykli ja false muuten.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`onkoSyklia(3, new int[] {1, 2, 3}, new int[] {2, 3, 1})`	`true`
2	`onkoSyklia(3, new int[] {1, 2}, new int[] {2, 3})`	`false`
3	`onkoSyklia(3, new int[] {1, 2, 1}, new int[] {2, 3, 3})`	`false`
4	`onkoSyklia(4, new int[] {2, 3, 4}, new int[] {3, 4, 2})`	`true`

Tehtävä 2

Saat syötteenä suunnatun verkon. Tehtävänäsi on laskea verkon vahvasti yhtenäisten komponenttien määrä.

Toteutus

Toteuta seuraava metodi:

int komponentteja(int n, int[] mista, int[] minne)

Solmujen määrä n on kokonaisluku välillä 1..10⁵ ja solmut on numeroitu kokonaisluvuin 1..n. Verkossa on korkeintaan 200000 kaarta.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`komponentteja(3, new int[] {1,2,3}, new int[] {2,3,1})`	`1`
2	`komponentteja(3, new int[] {1,1}, new int[] {2,3})`	`3`
3	`komponentteja(3, new int[] {1,1,2}, new int[] {2,3,3})`	`3`
4	`komponentteja(3, new int[] {1,1,2}, new int[] {2,3,1})`	`2`

Tehtävä 3

Saat syötteenä n-solmuisen suunnatun verkon. Tehtävänäsi on vastata nopeasti kyselyihin muotoa "mikä on lyhimmän polun pituus solmusta a solmuun b, joka kulkee solmun 1 kautta".

Toteutus

Toteuta luokka Reitinlaskija, joka tarjoaa seuraavat metodit:

Konstuktori Reitinlaskija(int n, int[] mista, int[] minne),
missä parametrit kuvaavat suunnatun verkon kuten aiemmissa tehtävissä.
int lyhinReitti(int a, int b),
joka palauttaa lyhimmän sellaisen polun pituuden, joka kulkee solmusta a
solmun 1 kautta solmuun b. Jos tällaista reittiä ei ole, tulee metodin palauttaa -1.

Syötteen kuvaamassa verkossa on korkeintaan 10⁵ solmua ja 2*10⁵ kaarta. Testauksessa metodia lyhinReitti kutsutaan korkeintaan 10⁵ kertaa.

Tehtävä 4

Uolevin Kaaleppi-serkku täyttää vuosia ja Uolevilla on kova kiire syntymäpäiväjuhliin. Serkun luokse päästäkseen täytyy hänen kuitenkin suunnistaa mutkikasta tieverkkoa pitkin. Lisäksi asioita mutkistaa myös se, että osa teistä on uusia asfaltoituja teitä, ja osa mutaisia metsäpolkuja. Koska Uolevi on kohtelias, ei hän halua liata asfalttia mudalla. Siksi hän haluaisikin löytää reitin, jossa ensin kuljetaan pelkkiä asfalttiteitä pitkin, ja sitten pelkkiä metsäteitä pitkin (myös pelkkiä metsäteitä tai pelkkiä asfalttiteitä käyttävät polut kelpaavat). Mikä on lyhin ehdot toteuttava reitti, jota kulkemalla Uolevi pääsee perille?

Toteutus

Toteuta seuraava metodi:

int lyhinReitti(int n, int[] mista, int[] minne, boolean[] mutaa)

Verkko on kuvattu kuten aiemmissa tehtävissä sillä erotuksella, että jokaiseen kaareen liittyy boolean arvo, joka kertoo, onko kyseessä mutainen metsäpolku vai ei. Tämä tieto löytyy taulukosta mutaa, jonka pituus on sama kuin taulukoilla mista ja minne. Kaikki tiet ovat kaksisuuntaisia.

Uolevi aloittaa matkansa solmusta numero 1 ja Kaaleppi-serkun koti on solmussa numero n. Metodisi tulee palauttaa lyhimmän sellaisen polun 1->n pituus, jolla kuljetaan ensin pelkkiä puhtaita teitä (mutaa-taulukon arvo false), ja sitten pelkkiä mutaisia teitä (mutaa-taulukon arvo true). Jos tällaistä reittiä ei ole olemassa, tulee metodisi palauttaa -1.

Huomaathan, että samojen solmujen välillä voi olla useita kaaria, eli erityisesti samojen solmujen välillä voi olla sekä mutainen, että mudaton tie. Syötteen kuvaamassa verkossa on korkeintaan 10⁵ solmua ja 2*10⁵ kaarta.

Tehtävä 5

Uolevin seikkailupelissä on n huonetta, joihin on piilotettu kolikoita. Huoneiden välillä pääsee liikkumaan ovia pitkin. Nämä ovet ovat siitä hieman outoja, että ne avautuvat vain yhteen suuntaan, joten yhdestä ovesta voi kulkea vain yhteen suuntaan. Lisäksi tiedetään, että huoneistossa ei ole sykliä.

Pelin hahmo aloittaa pelin huoneesta 1. Mikä on suurin mahdollinen määrä kolikoita, jonka pelin aikana voi saada? Uolevi saa päättää pelinsä missä tahansa huoneessa.

Toteutus

Toteuta seuraava metodi:

long kolikoita(int n, long[] k, int[] mista, int[] minne)

Parametri n on kokonaisluku välillä 1..10⁵. Huoneet on numeroitu kokonaisluvuin 1..n.

Taulukot mista ja minne kuvaavat huoneiden väliset ovet. Taulukon k pituus on n+1, luku k[i] kertoo huoneessa i olevien kolikoiden määrän. Tämä on kokonaisluku välillä 0..10⁹.

Metodin tulee palauttaa suurin mahdollinen kolikoiden määrä, jonka pelin aikana voi kerätä.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`kolikoita(3, new long[] {0, 1, 1, 1}, new int[] {1, 2}, new int[] {2, 3})`	`3`
2	`kolikoita(3, new long[] {0, 1, 1, 1}, new int[] {2, 1}, new int[] {1, 3})`	`2`
3	`kolikoita(4, new long[] {0, 1, 1, 1, 10}, new int[] {1, 2, 1}, new int[] {2, 3, 4})`	`11`
4	`kolikoita(4, new long[] {0, 1, 1, 1, 1}, new int[] {1, 1, 1}, new int[] {2, 3, 4})`	`2`