codeforces R701 D2

solved: 0 out of 6

바로 어제 밤을 새서 스킵하려다 그냥 쳤는데 무려 0솔입니다 😅

따라서 업솔한 문제는 그때 그때 추가하겠습니다🙃

 

A. Add and Divide

그냥 수학문제입니다.

저는 대회중에 식은 다 뽑았는데 구현을 못하고 끝났습니다.

각각의 연산에 대해 k번 n번 했다고 했을 때,

WLOG, $b = k$ 그리고 $a = \left \lfloor \frac{a}{b^n} \right \rfloor$

따라서 이때 $min\left ( n+k \right ), a <  \left \lfloor \frac{a}{k^n} \right \rfloor$를 찾아주면 문제를 해결 할 수 있습니다.

이후 최악의 상황에 대해서 min값은 최대 32를 넘지 않기 때문에 두가지 연산의 총 횟수가 32를 넘지 않게 짜주면 됩니다.

	for (ll i = 0; i < 32; i++) {
            for (ll j = i; j < 32-i; j++) {
                ll tmp = b+i;
                ll tmp2 = power(tmp, j);
                if (tmp2>a) {
                    ans=min(ans, i+j);
                    break;
                }
            }
        }