Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Royal Gems
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 250Accepted: 32

Description

In the game of Royal Gems, you are given an n × m board and arbitrarily large number of ruby, emerald, sapphire, and diamond gemstones. You must put one gemstone in each cell of the board according to the following rules:

1) Every ruby has an emerald, a sapphire and a diamond in his neighbors.
2) Every emerald has a sapphire and a diamond in her neighbors.
3) Every sapphire has a diamond in his neighbors.

A neighbor of a cell is one of the four cells that are directly above, below, left, or right of the cells. Write aprogram that finds the maximum number of ruby gemstones that could be put on the board satisfying the above rules.

Input

There are multiple test cases in the input. Each test case consists of n (1 < n < 8) and m (1 < m < 8). The input terminates with a line containing 0 0.

Output

For each test case, write a single line containing the maximum number of ruby gemstones on the board.

Sample Input

2 2
2 3
3 3
0 0

Sample Output

0
1
2

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator