Editorial for DMOPC '15 Contest 2 P3 - Origami


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

by cheesecake

Every cut we make, let's greedily cut the maximum amount of paper we can. Until we have more pieces of paper than K, we will always double the amount that we currently have with each cut. Once we have more than K, we can only obtain K pieces more with each cut, so we can use division to find the remaining cuts needed.

#include <bits/stdc++.h>
using namespace std;

long long N, K;
int main()
{
    scanf("%lld%lld",&N,&K);
    long long ans = 0;
    long long piece = 1;
    while (piece < K && piece < N)
    {
        piece += piece;
        ans++;
    }
    ans += (N-piece+K-1)/K;
    printf("%lld",ans);
    return 0;
}

Time Complexity: \mathcal{O}(log(min(N,K)))


Comments

There are no comments at the moment.