Avançado Informática - Semana 18

Cavalos

O jogo de xadrez como conhecido hoje foi inventado por volta do século XV, na Europa Medieval. Uma das suas peças mais interessantes é o cavalo, que se movimenta e ataca outras peças conforme a figura abaixo:

Na figura, o símbolo '•' representa as posições que o cavalo na casa central ataca.

Existem vários quebra-cabeças interessantes envolvendo os movimentos do cavalo; um deles pergunta quantos cavalos podem ser colocados em um tabuleiro M × N de forma que nenhum par de cavalos se ataque:

Soluções do quebra-cabeça para (a) um tabuleiro (a) 5 × 3 (b) um tabuleiro 2 × 6

A sua tarefa é escrever um programa que, dados M e N , determina quantos cavalos podem ser colocados em um tabuleiro M × N de forma que nenhum par de cavalos ataque-se simultaneamente.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira (e única) linha da entrada contém dois inteiros, M e N, (1 ≤ M ≤ 1000, 1 ≤ N ≤ 1000) indicando, respectivamente, o número de linhas e o número de colunas do tabuleiro.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro indicando o maior número de cavalos que podem ser colocados no tabuleiro sem que dois deles se ataquem.

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 30 pontos, 1 ≤ M ≤ 6.
  • Em um conjunto de casos de teste que totaliza 55 pontos, 1 ≤ M ≤ 100.

Exemplos

Exemplo de entrada

5 3
Exemplo de Saída

8	

 

Exemplo de entrada

2 6
Exemplo de Saída

8

 

Exemplo de entrada

1 4
Exemplo de Saída

4