Chocolate Bar

You have a rectangular chocolate bar. It consists of m×n (1≤m,n≤1000) squares. You want to break it up into 1×1 pieces (individual squares). What is the minimum number of times that you must break the chocolate bar, or pieces thereof, in order to achieve this? Note that you cannot stack pieces of the bar and break them, because the chocolate bar is thick. As an example, a 2×2 bar requires 3 breaks. First you can break it in half, then break each of the halves in half. You cannot break it in half, stack the two 1×2 pieces, and then use only one more break to achieve your goal.

Input Format
The first line contains an integer N, the number of test cases to follow.
Each of the following N lines contains two space-separated integers, the dimensions m and n of a chocolate bar.

Output Format
A line containing a single integer for each case given in the input: the answer for the corresponding case.

Sample Input
2
1 2
2 2

Sample Output
1
3

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 21, 2009
Author: javic

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

my code worked with the samples, but when i tested it with my own, it came out wrong. Help,please?

Your approach... doesn't make any sense, to be frank. The test cases are independent; there is no reason for later cases to be dependent on earlier cases.

So, from my understanding, for each line, it calculates?
example:
-------
1 2(1)prints 1
2 2(2)prints 2

that's how i think the code works, not so sure

The answer for 2 2 is 3, not 2.

In your code, the value of e, which you print, is dependent on previous cases. For example, the following will not work in your code:

Input:
2
2 2
1 2

Output:
3
1

so, I don't get it. How to do that no matter the value?

How to do what? Get the answer? I'm not going to tell you how to do the problem.

You may gain some insights by reading the previously posted comments.

Also I'm not convinced 100% that you know for sure that the cases are independent... so yeah. They are.


Try solving some sample data by yourself.
You just might find a pattern wink.gif

Like what?

Asking for answers defeats the point of solving problems.

Why am I using so much more memory than everyone else? The code is practically the same thing. (Note that I submitted twice, once with scanf, once with cin)

The memory reading is usually inaccurate for small amounts of memory. For example, I just rejudged both of your submissions and now they use the same amount of memory as those of anybody else.

hey brian, i tricked one ;)

Indeed xD

Curses.
Overthinking is not fox.

oh, and you misspelled "separate"