Awaiting submission

You are given a rectangular board of M x N squares. Also you are given an unlimited number of standard domino pieces of 2 x 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

- Each domino completely covers two squares.
- No two dominoes overlap.
- Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

The input is a single line containing two integers M and N, corresponding to the board size. The output is one number, the maximal number of dominoes, which can be placed.

Awaiting submission

May is learning English. She noticed that some words have more vowels (a,e,i,o,u) than consonants. She has asked you to find out how common this is.

Write a program that reads a sentence and determines if there are more vowels than consonants. The program should output `MORE`

, `LESS`

, or `EQUAL`

.

(Your program should ignore spaces and punctuation.)

Awaiting submission

One day, an ant called Alice came to an `M*M`

chessboard. She wanted to go around all the squares. So she began to walk along the chessboard as follows: (you can assume that her speed is one square per second) At the 1st second, Alice was standing at (1,1). Firstly she went up 1 square, then 1 square to the right, and then 1 square downwards. After that, she went a square to the right, then 2 squares upward, and then 2 squares to the left.

For example, her first 25 seconds went like this:

5 | 25 | 24 | 23 | 22 | 21 |

4 | 10 | 11 | 12 | 13 | 20 |

3 | 9 | 8 | 7 | 14 | 19 |

2 | 2 | 3 | 6 | 15 | 18 |

1 | 1 | 4 | 5 | 16 | 17 |

1 | 2 | 3 | 4 | 5 |

(the numbers in the squares stands for the time when she went into the squares)

At the 8th second, she was at (2,3), and at 20th second, she was at (5,4). Your task is to decide where she was at a given time.

The input will contain several lines, and each line contains a number N, which stands for the time. The input will be ended with a line that contains the number `0`

.

For each input line you should print a line with two numbers (x,y), the column and the row number, there must be only a space between them.

Awaiting submission

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money. For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.

Write a program to find the total number of different ways of making change for any amount of money in cents. Your program should be able to handle up to 1,000 cents.

The input contains any number of lines, each one consisting of a number for the amount of money in cents. For each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.