Piscinus

Time limit: 0.03s Memory limit: 64MB Input: piscinus.in Output: piscinus.out

Cerință

Armando și-a cumpărat o piscină dreptunghiulară formată din n×m×1n \times m \times 1 regiuni cubice cu latura de 11 metru, pe care vrea să o umple cu apă.

Din cauza ratelor mari la piscină, Armando nu și-a mai putut plăti facturile la apă. Prin urmare, el va trebui să își ia apa pentru piscină de la râul din apropiere, cu ajutorul unei găleți moștenite de la tatăl său.

Cu o găleată plină, Armando poate umple o regiune cubică de 1×1×11\times 1\times1 metri din piscină.

Când o regiune neumplută este adiacentă pe linie sau pe coloană cu două sau mai multe regiuni pline cu apă, atunci și aceasta se va umple ca prin minune. Acest proces va continua ori până se umple piscina, ori până nu se mai poate umple nicio altă regiune cu apă:

  • [100010101][110111111][111111111]\begin{bmatrix}1&0&0\\0&1&0\\1&0&1\end{bmatrix} \rightarrow \begin{bmatrix}1&1&0\\1&1&1\\1&1&1\end{bmatrix} \rightarrow \begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}
  • [110001000][111011000][111111000]\begin{bmatrix}1&1&0\\0&0&1\\0&0&0\end{bmatrix} \rightarrow \begin{bmatrix}1&1&1\\0&1&1\\0&0&0\end{bmatrix} \rightarrow \begin{bmatrix}1&1&1\\1&1&1\\0&0&0\end{bmatrix}

Care este numărul minim de găleți de apă pe care trebuie să le care Armando pentru a umple piscina?

Date de intrare

Pe prima linie a fișierului de intrare piscinus.in se vor afla două numere nn și mm - lungimea, respectiv lățimea piscinii lui Armando.

Date de ieșire

Fișierul de ieșire piscinus.out va conține numărul minim de găleți cu apă pe care trebuie să le care Armando pentru a umple piscina.

Restricții și precizări

  • 1n,m1091 \le n,m \le 10^9
    # Punctaj Restricții
    1 10 n=1n=1
    2 10 n=mn=m
    4 25 n,m5n,m \le 5
    5 55 Fără restricții suplimentare

Exemplul 1

piscinus.in

2 2

piscinus.out

2

Explicație

Armando va căra două găleți cu apă, cu care va umple regiunile (1,1)(1,1) și (2,2)(2,2): [1001][1111]\begin{bmatrix}1&0\\0&1\end{bmatrix} \rightarrow \begin{bmatrix}1&1\\1&1\end{bmatrix}

Exemplul 2

piscinus.in

4 3

piscinus.out

4

Explicație

Armando va căra patru găleți cu apă, cu care va umple regiunile (1,2)(1,2), (2,3)(2,3), (3,1)(3,1) și (4,3)(4,3):
[010001100001][011011100001][011111111001][111111111011][111111111111]\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\\0&0&1\end{bmatrix} \rightarrow \begin{bmatrix}0&1&1\\0&1&1\\1&0&0\\0&0&1\end{bmatrix} \rightarrow \begin{bmatrix}0&1&1\\1&1&1\\1&1&1\\0&0&1\end{bmatrix} \rightarrow \begin{bmatrix}1&1&1\\1&1&1\\1&1&1\\0&1&1\end{bmatrix} \rightarrow \begin{bmatrix}1&1&1\\1&1&1\\1&1&1\\1&1&1\end{bmatrix}

Log in or sign up to be able to send submissions!