B. Our Tanya is Crying Out Loud

• Quiz
  • https://codeforces.com/problemset/problem/940/B
• AC
  • https://codeforces.com/contest/940/submission/98362694
• 解説
  • k>1とする
  • 2つ選択肢があるように見えて、大抵は片方しか選べない
  • kで割る場合、何回連続で割るか考えそうになるが、1ステップのみ最適に動けば十分間に合う

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll n,k,a,b;cin>>n>>k>>a>>b;
    ll cost=0;

    if(k==1){
      cost += (n-1)*a;
      p(cost);
      return 0;
    }

    while(n!=1){
      if(n<k){
        cost += (n-1)*a;
        n=1;
      }
      else if(n%k!=0){
        ll r = n%k;
        cost += r*a;
        n -= r;
      }
      else{
        // n%k==0
        // 安い方を選ぶ
        // kで割る場合のコスト
        ll cost0 = b;
        // 1歩ずつ進む場合のコスト
        ll len = n-n/k;
        ll cost1 = a*len;
        cost += min(cost0, cost1);
        n /= k;
      }
    }
    p(cost);
    
    return 0;
}