Intermediate.
Put your skills to the test.

Problem summary

Fold a rectangular M×N centimetre sheet along centimetre divisions until its footprint is a 1×1 square. Minimize the number of folds. The illustrated 3→2→1 fold allows unequal halves.

Constraints

1 ≤ M,N ≤ 1000.

Worked example

Input and output for the worked example discussed below.

5 3

5

Solution analysis

1. A fold affecting a side of integer length x cannot reduce the footprint below ceil(x/2): one of the two parts has at least that length. Folding as evenly as possible attains exactly ceil(x/2).
2. Apply x=(x+1)/2 until x=1 and count the folds. Do this independently for both dimensions; a fold parallel to one edge changes only the perpendicular dimension.
3. For 5×3, one side needs 5→3→2→1, or three folds, and the other needs 3→2→1, or two. Total 5. A side already equal to 1 needs no fold.

Why it works

After f folds affecting a dimension, its original length can shrink by at most a factor 2^f, so at least ceil(log2 x) folds are necessary. Balanced integer folds attain that lower bound. Since each fold affects only one dimension, adding their two optimal counts is both necessary and sufficient.

Watch out. Folding exactly in half is not required when the length is odd, as the source’s 3→2→1 diagram shows. Use ceiling division, not x/2. Do not fold a unit side again.

An independently written complete program with standard headers.

#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int folds(int length){
    int answer=0;
    while(length>1){
        // A balanced integer fold leaves the longer half as the footprint.
        length=(length+1)/2;
        answer++;
    }
    return answer;
}
int main(){
    int rows;
    int columns;
    cin>>rows>>columns;
    cout<<folds(rows)+folds(columns)<<'\n';
}