Азия-тынық мұхит математикалық олимпиадасы, 2005 жыл

Кішкентай қалашықта әрбір $1\le i,j\le n$ үшін $(i,j)$ сандар парымен индекстелген ${{n}^{2}}$ үй бар. Егер $|i-k|+|j-l|=1$ болса, $(i,j)$, $(k,l)$ индексті үйлерді "көрші" дейміз. Уақыт 0 мезетінде, $(1,c)$ индексті үйде, мұндағы $c\le \dfrac{n}{2}$, өрт басталды. Әрбір келесі ${[t,t+1]}$ уақыт интервалында өрт сөндірушілер әлі өртке шалынбаған бір үйге өрттен қорғайтын жүйе орнатады, ал $t$ мезетінде өртке оранған үйлердің біреуіне көрші болатын және қорғансыз әрбір үйде өрт басталады. Өрттен қорғайтын жүйе орнатылған үй өртенбейді. Өрттің кеңеюі тоқтатылған кезде процесс аяқталады. Өрт сөндірушілер ең көп дегенде қанша үйді өрттен аман алып қала алады?
Ескерту: Қалашық өлшемі $n\times n$ болатын кесте пішіндес деп ұйғаруға болады, мұндағы үйлер — бірлік шаршылар, $(1,1)$ — сол жақ жоғарғы бұрыштағы үйдің индексі, ал $i$ мен $j$ сәйкесінше $(i,j)$ индексті үйдің қатары мен бағанын көрсетеді.