Viikko 7: TMC-tehtävät

TMC viikko 7

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

Viikon teemana on tasapainoitetun binäärihakupuurakenteen soveltaminen. Javasta löytyvät valmiit toteutukset TreeSet ja TreeMap, joissa on muutamia lisäominaisuuksia jo tuttuihin rakenteisiin HashSet ja HashMap verrattuna.


Tehtävä 1

Uolevi on innokas sarjakuvien keräilijä, jolle on vuosien saatossa kertynyt mittava kokoelma. Joskus Uolevi haluaisi lukea lehden, joka puuttuu hänen kokoelmastaan. Silloin hän valitsee lehden, jonka numero on mahdollisimman lähellä haluttua numeroa. Tehtäväsi on auttaa Uolevia lehden valinnassa.

Toteutus

Toteuta luokka Kokoelma, joka tarjoaa seuraavat metodit:

Aluksi Uolevin kokoelmassa ei ole yhtään lehteä.

Testauksessa metodeita kutsutaan yhteensä enintään 105 kertaa. Metodia valitseLehti ei kutsuta ennen kuin lehtiä on ainakin yksi. Jos vaihtoehtoja on kaksi, valitse niistä pienempi.

Esimerkki

Seuraava koodi testaa luokkaa:

Kokoelma k = new Kokoelma();
k.lisaaLehti(3);
System.out.println(k.valitseLehti(4));
System.out.println(k.valitseLehti(8));
k.lisaaLehti(9);
System.out.println(k.valitseLehti(4));
System.out.println(k.valitseLehti(8));

Koodin tulostuksen tulisi olla seuraava:

3
3
3
9

Tehtävä 2

Joskus Uolevi heittää jonkin lehdistään pois. Auta Uolevia selvittämään, mikä on suurin lehden numero, joka hänen kokoelmassaan esiintyy.

Toteutus

Toteuta luokka Kokoelma, joka tarjoaa seuraavat metodit:

Aluksi Uolevin kokoelmassa ei ole yhtään lehteä.

Testauksessa metodeita kutsutaan yhteensä enintään 500000 kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Kokoelma k = new Kokoelma();
System.out.println(k.suurinLehti());
k.lisaaLehti(1);
k.lisaaLehti(2);
System.out.println(k.suurinLehti());
k.poistaLehti(2);
System.out.println(k.suurinLehti());
k.lisaaLehti(3);
k.lisaaLehti(3);
System.out.println(k.suurinLehti());
k.poistaLehti(3);
System.out.println(k.suurinLehti());
k.poistaLehti(3);
System.out.println(k.suurinLehti());
k.poistaLehti(1);
System.out.println(k.suurinLehti());

Koodin tulostuksen tulisi olla seuraava:

-1
2
1
3
3
1
-1

Tehtävä 3

Aiemmin julkaistut lehdet ovat Uolevin mielestä parhaita, minkä vuoksi hän haluaisi saada kokoelmansa täydelliseksi ainakin niiden osalta. Auta Uolevia selvittämään, mikä on pienin kokoelmasta puuttuva numero.

Toteutus

Toteuta luokka Kokoelma, joka tarjoaa seuraavat metodit:

Aluksi Uolevin kokoelmassa ei ole yhtään lehteä.

Testauksessa metodeita kutsutaan yhteensä enintään 105 kertaa.

Esimerkki

Seuraava koodi testaa luokkaa:

Kokoelma k = new Kokoelma();
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(3);
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(2);
System.out.println(k.pieninPuuttuva());
k.lisaaLehti(1);
System.out.println(k.pieninPuuttuva());

Koodin tulostuksen tulisi olla seuraava:

1
1
1
4

Tehtävä 4

Uolevin eno on ostanut talonrakennusta varten pitkän laudan, jota pilkotaan osiin. Auta Uolevia toteuttamaan ohjelma, joka osaa kertoa pisimmän yhtenäisen laudanpätkän pituuden.

Toteutus

Toteuta luokka Lauta, ja sille sauraavat metodit:

Laudan pituus on enintään 2×109. Testauksessa lautaan tehdään enintään 105 leikkausta.

Esimerkki

Seuraava koodi testaa luokkaa:

Lauta l = new Lauta(10);
l.leikkaa(5);
System.out.println(l.pisinPatka());
l.leikkaa(5);
System.out.println(l.pisinPatka());
l.leikkaa(6);
System.out.println(l.pisinPatka());
l.leikkaa(3);
System.out.println(l.pisinPatka());
l.leikkaa(8);
System.out.println(l.pisinPatka());
l.leikkaa(1);
System.out.println(l.pisinPatka());

Koodin tulostuksen tulisi olla seuraava:

5
5
5
4
3
2

Tehtävä 5

Vahva länsituuli on yön aikana kaatanut puita. Jotkut puista ovat kaatuneet autojen päälle, tuhoten näin allejäävät autot. Tehtäväsi on selvittää myrskytuhojen laajuus, eli kuinka monta autoa tuhoutui yön aikana.

Toteutus

Toteuta metodi

int rikkinaisiaAutoja(int[] y, int[] v, int[] o, int[] autoX, int[] autoY)
joka selvittää montako autoa tuhoutui kuvatussa tilanteessa.

Puut ovat kuvattu kolmessa ensimmäisessä taulukossa: y[i] kertoo puun numero i y-koordinaatin, v[i] sen vasemman päätepisteen ja o[i] sen oikean päätepisteen. Voit olettaa, että nämä kolme ensimmäistä taulukkoa ovat yhtä pitkiä ja että v[i]<o[i].

Autot on kuvattu kahdessa viimeisessä taulukossa. Luvut autoX[j] ja autoY[j] kertovat auton numero j y- ja x-koordinaatit. Nämä kaksi taulukkoa ovat aina yhtä pitkät.

Taulukoissa esiintyvät luvut ovat välillä 0..109, ja kunkin taulukon pituus on korkeintaan 105. Huomaathan, että auto voi tuhoutua vain kerran, eli autoa ei lasketa kahdesti, jos se jää kahden puun alle. Mitkään kaksi autoa eivät ole samassa paikassa.

Esimerkki

Oletetaan, että olemme saaneet seuraavan syötteen:

y = {1, 3, 5, 5};
v = {0, 1, 1, 2};
o = {3, 2, 4, 5};

autoX = {1, 3, 4, 1};
autoY = {1, 4, 1, 3};

Nyt puut sijoittuvat kartalle seuraavasti:

.PPPPP
......
.PP...
......
PPPP..
......

ja autot seuraavasti:

......
...A..
.A....
......
.A..A.
......

Yhteentörmäykset tapahtuvat X:llä merkityissä kohdissa:

.PPPPP
...A..
.XP...
......
PXPPA.
......
Täten haluttu vastaus tällä syötteellä olisi 2.