Viikko 12: TMC-tehtävät

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

Viikon aiheena on pienimmät virittävät puut ja union find.

Tehtävä 1

Tehtäväsi on pitää kirjaa tieverkoston rakenteesta, kun kaupunkien välille rakennetaan teitä.

Toteutus

Toteuta luokka Tiet, joka tarjoaa seuraavat metodit:

• Tiet(int n): konstruktorille annetaan kaupunkien määrä, joka on kokonaisluku välillä 1..10⁵. Alussa kaikki kaupungit ovat erillä toisistaan, eli minkään kahden kaupungin välillä ei ole tietä.
• void rakenna(int a, int b): rakentaa (kaksisuuntaisen) tien kaupunkien a ja b välille.
• boolean yhteys(int a, int b): metodin tulee palauttaa true mikäli kaupungit a ja b ovat samassa komponentissa, eli on olemassa polku kaupungista a kaupunkiin b. Muuten metodin tulee palauttaa false.

Testauksessa metodeita kutsutaan enintään noin 300000 kertaa.

Esimerkki

Seuraava koodinpätkä testaa luokan toimintaa:

Tiet t=new Tiet(5);
System.out.println(t.yhteys(1,2));
System.out.println(t.yhteys(1,1));
t.rakenna(1, 2);
System.out.println(t.yhteys(1,2));
System.out.println(t.yhteys(1,3));
t.rakenna(2, 3);
System.out.println(t.yhteys(1,3));
t.rakenna(1, 4);
System.out.println(t.yhteys(4,3));

Tulosteen tulisi näyttää tältä:

false
true
true
false
true
true

Tehtävä 2

Tieverkosto on päässyt huonoon kuntoon, ja se tulisi kunnostaa. Rahaa on kuitenkin vähän, eikä kaikkia teitä voi korjata. Tehtäväsi on etsiä sellainen joukko teitä, että minkä tahansa kahden kaupungin välillä pystyy kulkemaan vain korjattuja teitä ja kokonaiskustannus on mahdollisimman alhainen.

Toteutus

Toteuta seuraava metodi:

long kunnostus(int n, int[] mista, int[] minne, int[] hinta)

Parametri n on kaupunkien määrä, kokonaisluku välillä 1..10⁵. Kaupungit on numeroitu tuttuun tapaan kokonaisluvuin 1..n.

Taulukot mista, minne ja hinta kuvaavat tieverkoston tiet. Taulukko mista kertoo, mistä kaupungista tie alkaa, ja taulukko minne kertoo, mihin kaupunkiin tie päättyy. Kaikki tiet ovat kaksisuuntaisia, ja niiden määrä on välillä 0..10⁵. Lisäksi taulukko hinta kertoo, paljonko tien kunnostaminen maksaisi. Jokainen hinta on kokonaisluku välillä 1..10⁹.

Metodin tulee palauttaa pienin kokonaiskustannus, jolla teitä saadaan korjattua siinä määrin, että minkä tahansa kaupunkiparin välillä pääsee kulkemaan korjattujen teiden kautta.

Esimerkit

Tehtävä 3

Sinulle on annettu tiedot rautatieverkostosta, joka muodostuu kaupungeista ja niiden välisistä radoista. Jokaisesta rataosuudesta tiedetään myös, mikä on maksimipaino siinä ajavalle junalle. Jokaista rataosuutta voidaan tarvittaessa vahvistaa mielivaltaisen paljon. Kuinka montaa rataosuutta joudut vahvistamaan, jotta juna, jonka paino on W, pystyisi matkustamaan minkä tahansa kaupunkiparin välillä?

Toteutus

Toteuta seuraava metodi:

int vahvistuksia(int n, int[] mista, int[] minne, int[] raja, int W)

Parametri n on kaupunkien määrä, kokonaisluku välillä 1..10⁵. Kaupungit on numeroitu tavalliseen tapaan kokonaisluvuin 1..n.

Taulukot mista ja minne kuvaavat yhteydet kaupunkien välillä. Taulukko raja kertoo jokaisesta yhteydestä junan maksimipainon. Yhteyksien määrä on välillä 0..10⁵.

Metodin tulee palauttaa pienin mahdollinen määrä vahvistuksia, jolla W -painoinen juna voi matkustaa minkä tahansa kaupunkiparin välillä. Rautatieverkosto on aina yhtenäinen.

Esimerkit

Tehtävä 4

Tehtävänäsi on selvittää, moneenko eri komponenttiin kaupunkiverkosto jakautuu, kun teitä suljetaan.

Toteutus

Tehtävänäsi on toteuttaa seuraava metodi:

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

Parametrit n, mista ja minne kuvaavat kaupungit ja kaupunkien väliset kaksisuuntaiset tiet kuten aiemmissa tehtävissä. Teiden lukumäärä m on korkeintaan 10⁵.

Taulukko poistot kertoo, missä järjestyksessä teitä suljetaan. Luku poistot[i] on välillä 0..m, ja se tulee tulkita siten, että kaupunkien mista[poistot[i]] ja minne[poistot[i]] välinen tie suljetaan. Jo suljettua tietä ei yritetä enää sulkea. Voit olettaa, ettei mikään tie esiinny kahta kertaa taulukoissa mista ja minne, eli kahden kaupungin välillä on korkeintaan yksi suora tie. Poistoja tehdään korkeintaan 10⁵.

Metodin palauttaman taulukon komponentteja tulee olla yhtä pitkä kuin poistot -taulukon. Luvun komponetteja[i] pitää kertoa tieverkoston komponenttien määrä tien numero poistot[i] sulkemisen jälkeen. Kun tie on suljettu, ei sitä enää avata uudestaan.

Esimerkit

Tehtävä 5

Uolevin sedän huoltoaseman mainoskampanja (TMC4.5) ei juurikaan lisännyt huoltoaseman suosiota. Tämän vuoksi huoltoasemalle on suunnitteilla uusi mainosjuliste, tällä kertaa julisteelle ei ole muita vaatimuksia kuin se, että se on suorakulmion muotoinen, ja että sen voi liimata aitaan (suorassa). Mikä on suurin mahdollinen ala julisteelle?

Toteutus

Toteuta seuraava metodi:

long suurinAla(long[] aita)

Parametrina tuleva taulukko aita kuvaa laudassa käytettyjen aitojen korkeudet siinä järjestyksessä, missä ne esiintyvät aidassa. Aidassa on korkeintaan 10⁵ aitaa, ja lautojen korkeudet ovat välillä 1..10⁹. Jokainen lauta on metrin levyinen ja korkeudet annetaan metreinä. Palautettava pinta-ala tulee olla neliömetreinä.

Esimerkit

Ohessa vielä merkittynä suurimmat mahdolliset julisteet kussakin esimerkissä:

Esim 1:
    x
   xx
  xxx
 xxxx
xxxxx

Esim 2:
x    
xx   
xxx  
xxxx 
xxxxx

Esim 3:
xx xx 
xx xxx
xx xxx
xx xxx
xxxxxx

Esim 4:
xxx