Задача про листок и письмо

Question

Условие задачи:

Валя устала от социальных сетей и решила написать своей подруге Саше письмо на прямоугольном листе бумаге. Длины сторон листа равны n и m сантиметрам. Потом она нашла конверт прямоугольной формы, длины сторон которого равны h и w сантиметрам. К сожалению, письмо может не помещаться в конверт, в этом случае Вале придется несколько раз сложить письмо. За одно действие Валя может сложить письмо пополам по вертикали или по горизонтали. После того, как Валя, при необходимости, несколько раз сложит письмо пополам, она планирует положить его в конверт. Валя — очень аккуратная девочка, она всегда кладёт письмо в конверт таким образом, чтобы его стороны были параллельны сторонам конверта. Письмо помещается в конверт, если длины его стороны не больше длин соответствующих сторон конверта. Прежде чем положить письмо в конверт, Валя может повернуть его на 90 градусов. Например, если длины сторон письма равны 10 и 20 сантиметрам, а длины сторон конверта равны 20 и 10 сантиметрам, Вале не нужно сгибать письмо, она может повернуть его на 90 градусов и положить в конверт. Валя не хочет, чтобы письмо получилось очень мятым, поэтому она хочет сложить письмо пополам минимальное число раз. Помогите ей выяснить, какое минимальное число раз ей придется сложить письмо перед тем, как она сможет положить его в конверт.

Идеи как написать решение минимальны, вот что получилось, но программа работает не правильно, думаю что настолько в лоб решать задачу плохо, но других идей я не нашел.

#include <iostream>
#include <ctime>
using namespace std;
int main()
{
    int n,m;
    int h, w;
    int answ = 0;
    cin >> n >> m; // лист
    cin >> h >> w; // конверт

    if (n != h && m != w || n != w && m != h)
    {
        while (n >= h)
        {
            while (n >= w)
            {
                n / 2;
                answ++;
            }

        }
        while (m >= h)
        {
            while (m >= w)
            {
                w / 2;
                answ++;
            }
        }
        cout << answ;
    }
    else
    {
        answ = 0;
        cout << answ;
    }
    cout << answ;


    cin.get();
    return 0;
}

Идея решения:

Мы проверяем обе стороны листа с сторонами конверта, если стороны листа не равняются сторонам конверта, то мы делим стороны напополам и проверяем еще раз, при этом накапливает answ как ответ, не знаю насколько это верно, но только это лезет в голову

UPD:

Я понял что мое решение имеет право на жизнь, но в консоли не выводится answ, помогите пожалуйста

int main()
{
    int n,m;
    int h, w;
    int answ = 0;
    cin >> n >> m; // лист
    cin >> h >> w; // конверт

    if (n != h & m != w || n != w & m != h)
    {
        while (n >= h || n >= w)
        {

            n /= 2;
            answ += 1;
        }

            while (m >= h || m >= w)
            {
                
                    w /= 2;
                    answ += 1;
                
            }
            cout << answ << endl;
        
        
    }
    else
    {
        cout << answ << endl;
    }

    cin.get();
    return 0;

Answer 1

Давайте попробуем подкинуть идею.

Если сложить листок a раз по горизонтали, и b раз по вертикали, то размеры станут

m/2^a, n/2^b

А по отношению m/w и n/h нетрудно найти a и b

С другой стороны, если смотреть отношения n/w и m/h (другая ориентация), то получатся другие числа a'и b'.

Остаётся только проверить, какая сумма меньше a+b или a'+b'

int steps(unsigned long long v) {
    int k = 0;
    unsigned long long t = 1;
    while (t < v) {
        k++;
        t *= 2;
    }
    return k;
}

int main()
{
    unsigned long long h, w, lh, lw;
    unsigned long long answ = 0;
    cin >> lh >> lw; // лист
    cin >> h >> w; // конверт

    int a1 = steps((lh + h - 1) / h); //округляем вверх
    int b1 = steps((lw + w - 1) / w);
    int a2 = steps((lh + w - 1) / w);
    int b2 = steps((lw + h - 1) / h);

    cout << min(a1 + b1, a2 + b2);

    return 0;
}

БЛОГ НА HUSL

Задача про листок и письмо

Ответы (1 шт):