Valya and Letter
Time limit1sMemory limit512 MB
Given a sheet n by m and an envelope h by w, fold the sheet in half along either axis repeatedly so it fits (rotation allowed), minimizing folds.
- Level
Medium6 of 10
- Topics
- Math, Greedy, Implementation, Binary search
- Solved
- No attempts yet
Problem
Valya got bored with social media, so she decided to write a good old handwritten letter to her friend. Valya wrote the letter on a rectangular sheet of paper. The sheet's dimensions are and cm. Then she found a rectangular envelope with dimensions and cm.
Unfortunately the letter could be too big to be placed into the envelope. So she might need to fold it several times. In one move Valya can fold the letter in half vertically or horizontally.
After folding the letter if necessary, Valya would put it into the envelope. Valya is a perfectionist, so she would always put the letter into the envelope in such way that its sides are parallel to the envelope's sides. The letter can be placed into the envelope if its corresponding dimensions don't exceed the envelope's dimensions. Before placing the letter Valya can rotate it by degrees. For example, if the letter's dimensions are equal to and cm, and the envelope's dimensions are equal to and cm, Valya doesn't need to fold the letter, she can rotate it by degrees to fit it into the envelope.
Valya doesn't want the letter to be crumpled so she wants to fold it the minimal possible number of times. Help her find this number.
Input
The first line of the input contains four integers , , and denoting the dimensions of the letter and dimensions of the envelope, respectively ().
Output
Output one number --- the minimal number of folds required, so that Valya could put the letter into the envelope.