easy math problem
easy math problem
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
1つの数nについて、次の2つの操作があります.
1つは1を減らすことで、aが必要です.
しかし、nがkで除去されれば、bを費やしてnをkで除算することもできる.
すみません、この数を1にするには最低いくらかかりますか?
Input
1行目の整数n(n<=1 e 5)
2行目の3つの正の整数は、それぞれa,b,k(0Output
出力整数は最小コストを表します.
Sample Input
Sample Output
Hint
Source
歩く二叉木
構想:この問題の構想は非常に簡単で、nを1にするのは2つのステップにほかならない.そしてその場合を判断して、そのステップを使います.
コードは次のとおりです.
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
1つの数nについて、次の2つの操作があります.
1つは1を減らすことで、aが必要です.
しかし、nがkで除去されれば、bを費やしてnをkで除算することもできる.
すみません、この数を1にするには最低いくらかかりますか?
Input
1行目の整数n(n<=1 e 5)
2行目の3つの正の整数は、それぞれa,b,k(0
出力整数は最小コストを表します.
Sample Input
10
1 2 2Sample Output
6Hint
Source
歩く二叉木
構想:この問題の構想は非常に簡単で、nを1にするのは2つのステップにほかならない.そしてその場合を判断して、そのステップを使います.
コードは次のとおりです.
#include
#include
int main()
{
int n ;
int a ,b , k ;
int sum = 0 ;
scanf("%d",&n) ;
scanf("%d %d %d",&a,&b,&k) ;
while(n!=1)
{
if(n%k==0&&(n-n/k)*a>b)
{
sum+=b ;
n = n/k ;
}
else
{
sum+=a ;
n-- ;
}
}
printf("%d
",sum) ;
return 0 ;
}