Viikko 9: TMC-tehtävät

TMC viikko 9

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

Viikon aiheena on leveys- ja syvyyshaku, sekä niiden sovellukset. Lyhyt lisämateriaali vieruslistojen toteuttamisesta Javalla.

Tehtävä 1

Uolevi ja Maija ovat tällä hetkellä eri kaupungeissa. Pystyvätkö he pääsemään toistensa luokse?

Toteutus

Toteuta seuraava metodi:

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

Parametri n on kaupunkien määrä, kokonaisluku välillä 2..10⁵. Kaupungit on numeroitu 1..n. Uolevi on kaupungissa 1 ja Maija on kaupungissa n.

Taulukot mista ja minne kuvaavat tiet kaupunkien välillä. Taulukko mista kertoo, mistä kaupungista tie lähtee, ja taulukko minne kertoo, mihin kaupunkiin tie johtaa. Kaikki tiet ovat kaksisuuntaisia, ja niiden määrä on 0..10⁵.

Metodin tulee palauttaa true, jos Uolevi ja Maija voivat päästä toistensa luokse, ja muuten false.

Esimerkit

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

Tehtävä 2

Sinulle on annettu talon pohjapiirros ja tehtäväsi on laskea talon huoneiden määrä.

Pohjapiirroksessa 0 tarkoittaa lattiaa ja 1 tarkoittaa seinää. Kaikki reunaruudut ovat seinää. Jokainen huone muodostuu lattiaruuduista, joihin pääsee kulkemalla vasemmalle, oikealle, ylöspäin ja alaspäin.

Esimerkiksi seuraavassa talossa on 3 huonetta:

Toteutus

Toteuta seuraava metodi:

int laskeHuoneet(int[][] kartta)

Taulukko kartta sisältää talon kuvauksen. Taulukon korkeus ja leveys ovat välillä 1..100 ja jokainen alkio on 0 (lattia) tai 1 (seinä).

Metodin tulee palauttaa talon huoneiden määrä.

Esimerkki

Seuraava koodi testaa metodia:

int[][] kartta = {{1,1,1,1,1,1,1,1},
                  {1,0,0,1,0,0,0,1},
                  {1,0,0,1,0,1,1,1},
                  {1,0,0,1,0,1,0,1},
                  {1,1,1,1,1,1,1,1}};
System.out.println(laskeHuoneet(kartta));

Koodin tulisi tulostaa luku 3.

Tehtävä 3

Sinulle on annettu labyrintin pohjapiirros, ja tehtäväsi on etsiä lyhin reitti kahden ruudun välillä.

Pohjapiirroksessa 0 tarkoittaa lattiaa, 1 tarkoittaa seinää, 2 tarkoittaa alkukohtaa ja 3 tarkoittaa loppukohtaa. Labyrintissa saa liikkua vasemmalle, oikealle, ylöspäin ja alaspäin.

Esimerkiksi seuraavassa labyrintissa lyhin reitti on 7 askelta:

Reitissä mennään ensin 4 askelta vasemmalle, sitten 2 askelta ylöspäin ja lopuksi 1 askel oikealle.

Toteutus

Toteuta seuraava metodi:

int lyhinReitti(int[][] kartta)

Taulukko kartta sisältää labyrintin kuvauksen. Taulukon korkeus ja leveys ovat välillä 1..100 ja jokainen alkio on 0 (lattia), 1 (seinä), 2 (alkukohta) tai 3 (loppukohta).

Metodin tulee palauttaa askelten määrä lyhimmällä reitillä. Jos kuitenkaan mitään reittiä ei ole olemassa, metodin tulee palauttaa -1.

Esimerkki

Seuraava koodi testaa metodia:

int[][] kartta = {{1,1,1,1,1,1,1,1},
                  {1,0,3,1,0,0,0,1},
                  {1,0,1,1,0,1,0,1},
                  {1,0,0,0,0,2,0,1},
                  {1,1,1,1,1,1,1,1,}};
System.out.println(lyhinReitti(kartta));

Koodin tulisi tulostaa luku 7.

Tehtävä 4

Uolevin ystäväpiiri riitautui pahasti lomamatkan aikana. Jotkut ystävyksistä riitautuivat niin pahasti, etteivät he halua enää olla missään tekemisissä toistensa kanssa. Matkan ajalta jäi kuitenkin selvittämättä velkoja.

Saat kustakin henkilöstä tiedon siitä, kuinka paljon kyseisellä henkilöllä on saatavia yhteensä (eli siis kuinka paljon hänelle ollaan velkaa - kuinka paljon hän on velkaa muille). Saat myös tiedon siitä, ketkä ovat vielä puheväleissä. Tehtäväsi on selvittää, voivatko entiset ystävykset tasata velkansa siirtämällä rahaa ainoastaan niiden ihmisten välillä, jotka ovat vielä puheväleissä.

Toteutus

Toteuta seuraava metodi:

boolean velat(int n, int[] saatavia, int[] mista, int[] minne)

Parametri n on Uolevin ystäväpiirin koko. Se on kokonaisluku välillä 1..10⁵. Ystävät on numeroitu kokonaisluvuin 1..n.

Taulukko saatavia, sisältää tiedon jokaisen henkilön saatavista. Taulukon pituus on n+1 (yksi lisäindeksi tulee siitä, ettei nollaindeksi ole käytössä). Voit olettaa, että taulukon lukujen summa on 0, eli velat olisi mahdollista tasata ainakin silloin, jos kaikki olisivat vielä puheväleissä.

Taulukot mista ja minne kuvaavat ystävyyssuhteet. Ystävyyssuhteiden määrä on 0..10⁵. Ystävyyssuhteet ovat aina kaksisuuntaisia, mutta toista suuntaa ei välttämättä ilmoiteta eksplisiittisesti syötteessä.

Metodin tulee palauttaa true, jos velkojen tasaaminen on mahdollista, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`velat(3, {0, 1, 3, -4}, {1, 3}, {2, 1})`	`true`
2	`velat(4, {0, 1, 1, 1, -3}, {1, 2, 3}, {2, 3, 4})`	`true`
3	`velat(4, {0, 1, 1, 1, -3}, {1, 2}, {2, 3})`	`false`

Tehtävä 5

Uolevi aikoo mennä Maijan luokse lyhintä reittiä, mutta joskus reitti ei ole yksikäsitteinen. Tehtäväsi on laskea, montako erilaista lyhintä reittiä Uolevilla on valittavana.

Toteutus

Toteuta seuraava metodi:

long reittimaara(int n, int[] mista, int[] minne)

Parametrit kuvaavat kaupungit ja tiet samalla tavalla kuin aiemmissa tehtävissä. Kaupunkien määrä on välillä 1..10⁵ ja samoin teiden määrä on välillä 1..10⁵.

Metodin tulee palauttaa, montako erilaista lyhintä reittiä on olemassa kaupungista 1 kaupunkiin n. Voit olettaa, että vastaus on enintään 10¹⁸.

Tehtävässä alkuun auttava vinkki: leveyshaulla lyhintä reittiä kahden solmun välillä etsiessä lasketaan itseasiassa lyhimpien polkujen pituus jostain lähtösolmusta kaikkiin muihin solmuihin. Samalla tavalla kannattaa toimia tässä.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`reittimaara(2, new int[] {1}, new int[] {2})`	`1`
2	`reittimaara(5, new int[] {1,1,2,3,4}, new int[] {2,3,4,4,5})`	`2`
3	`reittimaara(5, new int[] {1, 1, 1, 2, 3, 4}, new int[] {2, 3, 4, 5, 5, 5})`	`3`
4	`reittimaara(7, new int[] {1,2,3,1,1,4,5,6}, new int[] {2,3,7,4,5,6,6,7})`	`3`

Tehtävä 6

Tämä on ylimääräinen lisätehtävä, joka ei kasvata kurssin "maksimipistemäärää". Tehtävästä saa kuitenkin TMC-pisteen normaalisti.

Saat syötteenä kokonaisluvun n. Tehtävänäsi on tehdä verkko, jossa solmujen 1 ja 100000 välillä on tasan n lyhintä polkua.

Toteutus

Toteuta seuraava metodi:

Verkko rakenna(int n)

Luku n on korkeintaan 10⁹. Palautetussa verkossa saat käyttää ainoastaan solmuja 1..100000, ja siinä saa olla korkeintaan 10⁵ kaarta.

Tehtävässä ei tehtävän luonteen vuoksi voi olla lokaalia testiä, joka laskisi lyhimpien polkujen 1->100000 määrän generoidulle verkolle ja tämän oikeellisuus tarkistetaan vasta palvelimelle lähetettäessä. Jos olet tehnyt tehtävän 9.5 (joka kannattaa tehdä ennen tätä tehtävää), niin voit helposti testata siinä tekemälläsi algoritmilla, että reittien määrä on oikea.