Viikko 4: TMC-tehtävät

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

Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta mainita. Viikon aiheena on jono- ja pinorakenteen soveltaminen. Javasta läytyvät valmiit toteutukset Stack ja ArrayDeque.

Tehtävä 1

Eräänä päivänä kävellessään puistossa Uolevi huomasi, että puistossa on monia hienoja kiviä. Koska Uolevi on ahkera kivien kerääjä, alkoi hän poimimaan maassa lojuvia kiviä. Hän kerää kivensä erityiseen kivikoteloon, johon kivet menevät sopivasti päällekkäin. Uusi kivi menee aina kotelon päällimmäiseksi.

Uolevi ei kuitenkaan halua kokoelmaansa useita samanlaisia kiviä, joten jos hän jossain vaiheessa huomaa, että uusi kivi on samanlainen kuin kotelon päällimmäinen kivi, heittää hän sekä kotelon päällimmäisen kiven, että uuden kiven pois. Tehtävänäsi on selvittää kuinka monta uutta kiveä Uolevilla on kävelynsä jälkeen.

Toteutus

Toteuta seuraava metodi:

int montakoKivea(int[] kivet)

Taulukko kivet sisältää Uolevin löytämät kivet löytämisjärjestyksessä. Kivet ovat samanlaiset jos niitä vastaavat kokonaisluvut ovat samat. Metodin tulee palauttaa uusien kivien määrä kävelyn jälkeen.

Taulukon kivet pituus on korkeintaan 100000 ja sen sisältämät luvut ovat välillä 0..109.

Esimerkit

Tehtävä 2

Sinulle on annettu merkkijono, joka muodostuu merkeistä ( ja ). Tehtäväsi on tarkistaa, onko merkkijono oikein sulutettu eli voiko merkkijonon saada matemaattisesta lausekkeesta poistamalla kaikki muut merkit paitsi sulut.

Esimerkiksi merkkijonot ((())) ja (())() ovat oikein sulutettuja, kun taas merkkijonot (()))( ja ())(() eivät ole oikein sulutettuja.

Toteutus

Toteuta seuraava metodi:

boolean sulutus(String mjono)

Parametri mjono on sulut sisältävä merkkijono. Sen pituus on välillä 1..105.

Metodin tulee palauttaa true, jos merkkijono on oikein sulutettu, ja muuten false.

Esimerkit

Tehtävä 3

Tehtäväsi on toteuttaa pinolaskin, joka suorittaa annetun ohjelman. Pinoa voi käsitellä vain sen lopusta (oikealta puolelta). Aluksi pinossa on luku 1. Ohjelman komennot suoritetaan järjestyksessä, ja mahdolliset komennot ovat:

• @: lisää pinoon kopio pinon viimeisestä luvusta
• +: poista pinon kaksi viimeistä lukua ja lisää niiden summa pinoon
• *: poista pinon kaksi viimeistä lukua ja lisää niiden tulo pinoon

Esimerkiksi ohjelma @@+@* suoritetaan näin:

1. Aluksi pinon sisältö on [1].
2. Komennon @ jälkeen sisältö on [1, 1].
3. Komennon @ jälkeen sisältö on [1, 1, 1].
4. Komennon + jälkeen sisältö on [1, 2].
5. Komennon @ jälkeen sisältö on [1, 2, 2].
6. Komennon * jälkeen sisältö on [1, 4].

Tehtäväsi on suorittaa annettu ohjelma ja palauttaa pinon viimeinen luku ohjelman suorituksen jälkeen.

Toteutus

Toteuta seuraava metodi:

int laskin(String ohjelma)

Parametri ohjelma on suoritettava ohjelma. Se muodostuu merkeistä @, + ja *, ja sen pituus on 1..10⁵ merkkiä.

Metodin tulee palauttaa pinon viimeinen luku ohjelman suorituksen jälkeen. Voit olettaa, että kaikki pinossa ohjelman suorituksen aikana olevat luvut, mukaan lukien viimeinen luku, ovat välillä 1..10⁹. Pinolaskimen saama ohjelma on aina hyvin koodattu, eli kaikki operaatiot voidaan suorittaa ongelmitta, eli esimerkiksi merkin '+' kohdalla pinossa on vähintään kaksi lukua.

Esimerkit

Tehtävä 4

Läheisen yökerhon korruptoitunut ovimies on päättänyt hankkia lisätienestejä kiristämällä jonottavia asiakkaita. Välillä hän veloittaa x euroa jokaiselta jonossa sillä hetkellä olevalta henkilöltä, ja koska kaikki jonottajat haluavat päästä sisään, maksavat he ovimiehelle aina hänen pyytämänsä summan. Tehtäväsi on auttaa ovimiestä pitämään kirjaa siitä, kuinka paljon hän on onnistunut saamaan rahaa kultakin asiakkaalta.

Toteutus

Tehtävänäsi on toteuttaa tehtäväpohjassa oleva luokka Laskuri ja siihen seuraavat metodit:

• Laskuri() luo tyhjän jonon.
• void lisaaJonoon() lisää jonon perälle uuden asiakkaan.
• void veloita(long x) veloittaa jokaiselta jonossa tällä hetkellä olevalta jonottajalta x euroa.
• long paastaSisaan() päästää jonossa ensimmäisenä olevan asiakkaan sisään ja palauttaa tiedon siitä, kuinka monta euroa kyseinen asiakas on joutunut maksamaan ovimiehelle jonossa pysyäkseen.

Testeissä luokan metodeja kutsutaan korkeintaan 500000 kertaa. Luku x on välillä 1..109. Jos jonossa ei ole asiakkaita, niin metodin long paastaSisaan() tulee palauttaa 0.

Tehtävä 5

Uolevin sedän huoltoasema haluaa saada näkyvyyttä autoilijoiden keskuudessa, joten läheisen tien laidalla olevaan aitaan halutaan liimata suorakulmion muotoinen mainosjuliste. Aidassa on kuitenkin yksi ongelma: se on rakennettu vaihtelevan korkuisista laudoista. Lisäksi tyyliseikkojen vuoksi julisteen on oltava oikeasta reunastaan juuri oikean korkuinen Mikä on suurin mahdollinen pinta-ala julisteelle?

Selittävä esimerkki

Jos aidan lautojen korkeudet ovat [3, 1, 4, 4, 5], eli aita näyttää tältä:

    x
  xxx
x xxx
x xxx
xxxxx

    x
  xxx
x xxx
x xxx
xxxxx

    x
  xxx
x xxx
x xxx
xxxxx

x    
xx   
xxx  
xxxx 
xxxxx

Toteutus

Toteuta metodi long suurinAla(long[] aita), joka palauttaa suurimman mahdollisen pinta-alan (neliömetreinä) kelpaavalle mainosjulisteelle. Syötteenä tulevassa taulukossa on kuvattuna aidan laudat vasemmalta oikealle siinä järjestyksessä, jossa ne esiintyvät tien laidalla. Jokainen lauta on metrin levyinen ja i:nnen laudan korkeus on aita[i] metriä.

Aidassa on korkeintaan 200000 lautaa ja lautojen korkeudet ovat välillä 1..109.

Tehtävässä alkuun auttava vinkki (valkoista tekstiä valkoisella pohjalla): tehtävää kannattaa lähestyä siten, että etsii jokaisella oikean reunan valinnalla leveimmän mahdollisen julisteen, jonka oikea päätepiste on valitussa kohdassa.

Esimerkkisyötteet