TMC bonusviikko 2

Tehtävien deadline: 21.12 klo 04:01

Huom. Bonusviikolla on kaksi viikkoa aikaa tehdä tehtäviä

Tehtävä 1

Talossa on hajonnut vesiputkia. Tehtävänäsi on laskea, kuinka kauan kestää, ennen kuin koko talo (kaikki lattiaruudut) on veden vallassa.

Talon pohjapiirros annetaan samassa muodossa kuin tehtävissä 2 ja 3 viikolla 9, mutta merkki P tarkoittaa hajonnutta putkea. Vesi etenee talossa niin, että jos tietyssä lattiaruudussa on vettä, seuraavalla kierroksella myös kaikissa ruudun naapuriruuduissa on vettä.

Toteuta metodi int putkirikko(char[][] talo), joka laskee montako kierrosta menee kaikkien lattiaruutujen peittymiseen.

Voit olettaa, että hajonneista putkista on yhteys kaikkiin talon lattiaruutuihin.

Esimerkki 1

##########
#.#...##.#
#.#P#...P#
#.....##.#
##########

Kesto: 5

Seuraavaan kuvaan on merkitty ajanhetket, joina vesi saavuttaa talon lattiaruudut yllä olevassa tapauksessa:

##########
#5#123##1#
#4#P#321P#
#32123##1#
##########

Esimerkki 2

Pohjapiirros:

##########
#.#...##P#
#.#P#P...#
#P....##.#
##########

Kesto: 2

Tehtävä 2

Sinulle annetaan syötteenä luvut n ja m, jotka ovat kummatkin välillä 1-6. Tarkoituksenasi on laskea kuinka monta erilaista sellaista polkua n×m ruudukossa (missä n siis ruudukon korkeus ja m leveys) on, jossa jokaisessa ruudussa käydään tasan kerran ja polku alkaa vasemmasta yläkulmasta, sekä päättyy oikeaan yläkulmaan. Saat liikkua ruudukossa ainoastaan alas,ylös,oikealle ja vasemmalle, et siis esimerkiksi diagonaalisesti.

Esimerkkejä

2×2 ruudukossa on vain yksi tällainen polku:

14
23

luvut tarkoittavat missä järjestyksessä ruudukot käydään läpi.

3×3 ruudukossa mahdollisia reittejä onkin jo kaksi kappaletta.

189    129
276    438
345    567

Vaikka tehtävään läpäimiseen ei vaaditakaan mitään ihmeellisiä optimointeja, saattaa olla hauska lisätehtävä testata kuinka isoille ruudukoille saat laskettua vastauksen. Varsin yksinkertaisilla optimoinneilla esimerkiksi 8×8 ruudukolle saa laskettua vastauksen alle minuutissa. Edistyneemmällä algoritmilla esimerkiksi 20×20 kokoiselle ruudukolle saa laskettua vastauksen muutamissa tunneissa.

Tehtävä 3

Toteuta metodi boolean etsi(int[] taulukko, int k) joka tutkii onko taulukossa neljää lukua, joiden summa on k. Tässä tehtävässä sama taulukon luku saa kuulua summaan useamman kerran. Ratkaisusi tulee olla tehokas, syötteenä annetussa taulukossa voi olla jopa 500 lukua.

Huom! syötteessä voi olla myös negatiivisia lukuja!

Esimerkkejä

Kaikissa näissä esimerkeissä k=10.

Näille taulukoille etsi palauttaa true:

{2,3}
{1,2,3,4}
{4,2,3,1}
{4,4,1,1,1,6,6}
{4,3,1,5,5,6,6}

Näille taulukoille etsi palauttaa false:

{5}
{1,1,1,1}
{4,6,5,5}
{6,4,5,5}
{6,6,6,4}
{9,1,1,1,1,5,6}

Tehtävä 4

Tehtävänä on löytää kokonaislukutaulukosta suurin keskiarvo. Keskiarvossa olevien lukujen ei tarvitse olla peräkkäin, eli voi esimerkiksi valita ensimmäisen, viidennen ja kymmennen luvun keskiarvon. Keskiarvoon voi valita kuinka monta lukua tahansa.

Toteuta luokkaan Keskiarvo metodi public static double suurinKeskiarvo joka palauttaa desimaaliluvun kokonaisluvun joka on suurin keskiarvo jonka voi muodostaa valitsemalla joku määrä taulukon lukuja. Luvut mahtuvat int muuttujiin ja taulukon pituus voi olla 50*10^6.

Esimerkki

Taulukon [1,6,2] keskiarvot ovat:
1 : 1
2 : 2
6 : 6
1,2 : 0.5
1,6 : 3.5
6,2 : 4
1,2,6 : 3
suurin näistä on 6

Tehtävä 5

Saat syötteenä matriisin, jonka jokaisessa solussa on joko 0 tai 1. Tehtävänäsi on selvittää suurin mahdollinen ala sellaiselle suorakulmiolle, joka sisältää vain lukua 0. Algoritmin on toimittava nopeasti, ruudukon leveys ja korkeus ovat enintään 2000, joten algoritmin aikavaativuus on oltava kutakuinkin O(w*h) tai O(w*h*log(w)), missä w on matriisin leveys ja h korkeus.

Esimerkit

Esimerkiksi matriisissa

0100
0001
0000

suurin pelkkiä nollia sisältävä suorakulmio on

0100
0001
0000

eli vastaus tässä tapauksessa on 6. Toisaalta matriisissa

suurin tehtävänannon mukainen suorakulmio on

joten vastaus on myös 6.

Tehtävä 6

Uolevi on setänsä kanssa päättänyt lähteä tutkimaan aavikkoa. Aavikolla kuluu paljon vettä, mutta onneksi siellä on keitaita joissa vesivarastoja pystyy täydentämään. Kuitenkin Uolevin kameli pystyy kantamaan vain tietyn määrän vettä, joten tietyin väliajoin on pakko pysähtyä jollain keitaalla. Tehtävänäsi on selvittää pystyvätkö Uolevi ja hänen setänsä tutkimaan koko aavikon, eli käymään kaikissa paikoissa, ja palaamaan lopuksi lähtöpisteeseen.

Aavikko on jaettu kartalla ruutuihin:

.K..
.V..
..V.
.K..

. on aavikkoa joka halutaan tutkia
V tarkoittaa vuoristoa jonka läpi ei voi kulkea, näihin ruutuihin ei voi mennä
K tarkoittaa keidasta, jossa Uolevi ja setä voivat täydentää vesivarastojaan

Uolevi ja setä liikkuvat aina joka ylös, alas, vasemmalle tai oikealla, mutta ei vinottain (paitsi vuoristoruutuihin ei voi liikkua)

Uolevin kameli pystyy kantamaan enintään A yksikköä vettä, jossa jokainen matka ruudusta viereiseen kuluttaa yhden yksikön vettä. Esimerkiksi jos A on kuusi, kameli voi kantaa kuusi yksikköä vettä, joten kuuden siirtymän päästä se on loppu. Luonnollisesti vesi ei saa päästä loppumaan keskellä aavikkoa. Keitaalle tullessaan kamelin ottaa taas lisää vettä kantoon. Kamelin omaa vedenkulutusta ei tarvitse huomioida.

Uolevi ja setä lähtevät joltain keitaalta.

Toteuta luokkaan TutkimusMatka metodi public boolean loytyykoReitti(int x, int y), joka tarkastaa voivatko Uolevi ja setä tutkia koko aavikon lähtien kohdasta kartta[x][y], jossa on keidas. Metodin tulee palauttaa true, mikäli sopiva reitti löytyy. Luokka saa konstruktorissa aavikon kartan, ja kamelin kantokyvyn (eli kuinka paljon vettä voi kuljettaa).

Esimerkki

Esimerkiksi kartalle:

....K.
.K.V..
....V.
...K..

Reitti löytyy kun esimerkiksi lähtöpiste on (1,1) ja kantokyky on 6

Toisaalta, jos kantokyky on 5, reittiä ei löydy koska alavasen kulma on liian kaukana.