Viikko 7: TMC-tehtävät

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:

• void lisaaLehti(int numero)
  Uolevi ostaa lehden, jonka numero on numero (kokonaisluku väliltä 1..10⁹)
• int valitseLehti(int numero)
  palauttaa Uolevin kokoelmassa olevan lehden, jonka numero on mahdollisimman lähellä parametria numero (kokonaisluku väliltä 1..10⁹)

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

Testauksessa metodeita kutsutaan yhteensä enintään 10⁵ 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:

• void lisaaLehti(int numero)
  Uolevi ostaa lehden, jonka numero on numero (kokonaisluku väliltä 1..10⁹)
• void poistaLehti(int numero)
  poistaa Uolevin kokoelmasta yhden lehden, jonka numero on annettu parametri numero. Jos kokoelmassa on esimerkiksi 2 lehteä halutulla numerolla, niin poiston jälkeen niitä on vielä 1.
• int suurinLehti()
  kertoo suurimman Uolevin kokoelmasta löytyvän lehden numeron. Jos kokoelma on tyhjä, niin metodin tulee palauttaa -1.

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:

• void lisaaLehti(int numero)
  Uolevi ostaa lehden, jonka numero on numero (kokonaisluku väliltä 1..10⁹)
• int pieninPuuttuva()
  palauttaa pienimmän lehden numeron, joka puuttuu vielä Uolevin kokoelmasta

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

Testauksessa metodeita kutsutaan yhteensä enintään 10⁵ 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:

• Lauta(int pituus)
  alustaa laudan, jonka pituus on annettu parametri.
• int leikkaa(int kohta)
  leikkaa laudan annetusta kohdasta. Tässä ajatellaan, että laudan vasen päätepiste on kohdassa 0 ja oikea päätepiste kohdassa pituus.
• int pisinPatka()
  palauttaa suurimman yhtenäisen laudanpätkän pituuden.

Laudan pituus on enintään 2×10⁹. Testauksessa lautaan tehdään enintään 10⁵ 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)

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..10⁹, ja kunkin taulukon pituus on korkeintaan 10⁵. 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.
......