Viikko 10: TMC-tehtävät

Tehtävien deadline: su-ma yö 18.4. 1:59.

Viikon teemana on erityisesti syklit ja topologinen järjestäminen. Edellisen viikon aihe jatkuu osittain.

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

Tehtävä 2

Saat syötteenä suunnatun asyklisen verkon, eli suunnatun verkon jossa ei ole syklejä. Tehtävänäsi on järjestää solmut topologisesti.

Toteutus

Toteuta seuraava metodi:

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

Syöte kuvaa verkon samalla tavalla kuin tehtävässä 1. Myös syötteen rajat ovat samat.

Metodin tulee palauttaa luvut 1..n jossain topologisessa järjestyksessä, eli jos solmusta i pääsee solmuun j, on luvun i oltava ennen lukua j palautetussa taulukossa.

Tehtävä 3

Uolevi haluaa antaa lahjan jokaiselle ystävälleen. Uolevi ei halua antaa samaa lahjaa ystäville, jotka tuntevat toisensa, koska muuten lahja ei vaikuta henkilökohtaiselta. Toisaalta Uolevin varastossa on vain kahdenlaisia lahjoja: hän voi antaa joko kirjan tai karkkipussin. Onko Uolevin tavoite mahdollinen?

Oletetaan esimerkiksi, että Uolevin ystävät ovat A, B, C ja D. A tuntee kaikki muut ystävät, kun taas muut eivät tunne toisiaan. Nyt lahjojen jakaminen on mahdollista esimerkiksi niin, että A saa kirjan ja kaikki muut saavat karkkipussin.

Oletetaan sitten, että A ei tunne ketään, kun taas B, C ja D tuntevat kaikki toisensa. Nyt lahjojen jakaminen ei ole mahdollista, koska B:llä tulisi olla eri lahja kuin C:llä ja D:llä ja C:llä ja D:llä ei saa olla samaa lahjaa.

Toteutus

Toteuta seuraava metodi:

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

Parametri n on Uolevin ystävien määrä. Se on kokonaisluku välillä 1..10⁵. Ystävät on numeroitu kokonaisluvuin 1..n.

Taulukot mista ja minne kuvaavat ystävyyssuhteet. Ystävyyssuhteiden määrä on 0..10⁵. Voit olettaa, että ystävyyssuhteet ovat kaksisuuntaisia.

Metodin tulee palauttaa true, jos lahjojen jakaminen on mahdollista Uolevin haluamalla tavalla, ja muuten false.

Esimerkit

Tehtävä 4

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

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