Day 1 Task 3: Életminőség

Alberta városai R*C méretű négyzetrácsos elrendezésűek. A mezőket északról délre 0-tól R-1-ig, nyugatról keletre pedig 0-tól C-1-ig sorszámozzuk.

Az életminőség minden egyes mezőre egy-egy páronként különböző, 1 és R*C közötti egész szám. Az 1 a legjobb, az R*C a legrosszabb.

Keresünk egy H*W méretű téglalap alakú területet, ahol az életminőség mediánja a lehető legjobb. A medián az az érték, amelyre ugyanannyi nála kisebb, illetve nála nagyobb érték van.

Ird meg a rectangle(R,C,H,W,Q) függvényt, ahol R és C a város mérete, H<=R és W<=C páratlan számok, a Q pedig az életminőségek tömbje. Q[a][b] az északról délre a, nyugatról keletre b sorszámú mező életminősége.

A rectangle függvényednek a legjobb (azaz legkisebb) mediánt kell megadni a H*W méretű téglalapokra.

1. példa

 
R=5, C=5, H=3, W=3, 
Q=  5 11 12 16 25
   17 18  2  7 10
    4 23 20  3  1
   24 21 19 14  9
    6 22  8 13 15

Itt a legjobb (azaz legkisebb) medián a 9, a középen, jobboldalt levő téglalapra, amit a Q–ban vastagon látsz. 

 
rectangle(R,C,H,W,Q)=9

2. példa

 
R=2, C=6, H=1, W=5, 
Q=  6  1  2 11  7  5
    9  3  4 10 12  8

Itt  a helyes válasz  5.

 1. részfeladat [20 pont]

R és C legfeljebb 30.

2. részfeladat [20 pont]

R és C legfeljebb 100.

3. részfeladat [20 pont]

R és C legfeljebb 300.

4. részfeladat [20 pont]

R és C legfeljebb 1 000.

5. részfeladat [20 pont]

R és C legfeljebb 3 000.

Megvalósitás