B. Our Tanya is Crying Out Loud
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Right now she actually isn't. But she will be, if you don't solve this problem. You are given integers n, k, A and B. There is a number x, which is initially equal to n. You are allowed to perform two types of operations: Subtract 1 from x. This operation costs you A coins.
Divide x by k. Can be performed only if x is divisible by k. This operation costs you B coins.
What is the minimum amount of coins you have to pay to make x equal to 1?
Input
The first line contains a single integer n (1 ≤ n ≤ 2·109). The second line contains a single integer k (1 ≤ k ≤ 2·109). The third line contains a single integer A (1 ≤ A ≤ 2·109). The fourth line contains a single integer B (1 ≤ B ≤ 2·109). Output
Output a single integer — the minimum amount of coins you have to pay to make x equal to 1. Examples
inputCopy
9
2
3
1
output
6
inputCopy
5
5
2
20
output
8
inputCopy
19
3
4
2
output
12
Note
In the first testcase, the optimal strategy is as follows: Subtract 1 from x (9 → 8) paying 3 coins.
Divide x by 2 (8 → 4) paying 1 coin.
Divide x by 2 (4 → 2) paying 1 coin.
Divide x by 2 (2 → 1) paying 1 coin.
The total cost is 6 coins. In the second test case the optimal strategy is to subtract 1 from x 4 times paying 8 coins in total.
题目大意:给一个数n,进行两个操作1.将x减一,但是要花费A;2.只有x能被k整除时,才能除以k,但是要花费B.问进行这两个操作后使的n变成1,问最少要花多少
分析:这个两个操作实际上可以写成:(n-n%k)*A(k<=n,当n不能被整除)和B(当n能被整除),但是这题有个坑点,要注意k=1的时候,不管A比B大多少,除k明显是不行的,所以要当k==1,花费=(n-1)*A
详细见代码
#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define pb push_back
using namespace std;
typedef long long ll;
pair<ll,ll>PLL;
pair<int,ll>Pil;
const int INF = 0x3f3f3f3f;
const double inf=1e8+100;
const ll maxn =1000;
const int N = 1e4+10;
const ll mod=1000007;
ll n,d;
ll A,B,k; void solve() {
int i,j,t=1;
// cin>>t;
while(t--) {
ll ans=0;
cin>>n>>k>>A>>B;
if(k==1)
ans=(n-1)*A;
else {
while(n!=1) {
if(k<=n) {
if(n%k) {
ans+=(n%k)*A;
n-=n%k;
} else {
ans+=min(B,(n-n/k)*A);
n/=k;
}
}
else{
ans+=(n-1)*A;
n=1;
}
// cout<<ans<<endl;
}
}
cout<<ans<<endl;
}
} int main() {
ios_base::sync_with_stdio(false);
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
本人也是菜鸡,如有写的不好的地方请指出,谢谢
codeforce round#466(div.2) B. Our Tanya is Crying Out Loud的更多相关文章
-
Codeforces Round #466 (Div. 2) B. Our Tanya is Crying Out Loud[将n变为1,有两种方式,求最小花费/贪心]
B. Our Tanya is Crying Out Loud time limit per test 1 second memory limit per test 256 megabytes inp ...
-
codeforce round#466(div.2)C. Phone Numbers
C. Phone Numbers time limit per test2 seconds memory limit per test256 megabytes inputstandard input ...
-
Codeforces Round #466 (Div. 2) 题解940A 940B 940C 940D 940E 940F
Codeforces Round #466 (Div. 2) 题解 A.Points on the line 题目大意: 给你一个数列,定义数列的权值为最大值减去最小值,问最少删除几个数,使得数列的权 ...
-
Codeforces Round #466 (Div. 2) E. Cashback
Codeforces Round #466 (Div. 2) E. Cashback(dp + 贪心) 题意: 给一个长度为\(n\)的序列\(a_i\),给出一个整数\(c\) 定义序列中一段长度为 ...
-
Codeforces Round #466 (Div. 2) Solution
从这里开始 题目列表 小结 Problem A Points on the line Problem B Our Tanya is Crying Out Loud Problem C Phone Nu ...
-
Codeforces Round #466 (Div. 2)
所有的题目都可以在CodeForces上查看 中间看起来有很多场比赛我没有写了 其实是因为有题目没改完 因为我不想改,所以就没有写了(大部分题目还是改完了的) 我还是觉得如果是打了的比赛就一场一场写比 ...
-
Codeforces Round #466 (Div. 2) 题解
人生中第三次\(CF\)... 考试中切了\(A\)~\(E\) \(F\)题会做没时间写 题解 A:Points on the line 题意 给定一个数列,删最小的数,使最大差不大于一个定值 So ...
-
【codeforces】【比赛题解】#940 CF Round #466 (Div. 2)
人生的大起大落莫过如此,下一场我一定要回紫. [A]Points on the line 题意: 一个直线上有\(n\)个点,要求去掉最少的点,使得最远两点距离不超过\(d\). 题解: 暴力两重fo ...
-
CF940B Our Tanya is Crying Out Loud
Our Tanya is Crying Out Loud time limit per test 1 second memory limit per test 256 megabytes input ...
随机推荐
-
Type mismatch: cannot convert from MainFragment to Fragment 报错
源码: FragmentTransaction mFragmentTranscation = getSupportFragmentManager().beginTransaction(); Fragm ...
-
Grails 1.2参考文档速读(10):Controller
转载:http://keyvalue.blog.51cto.com/1475446/303260 从本篇起,我们将开始进入Grails的Web层,首先让我们从Controller说起. G ...
-
getMeasuredHeight() 与 getHeight() 的区别
http://www.cnblogs.com/x-dev/p/3767538.html?utm_source=tuicool&utm_medium=referral public final ...
-
MSSQL 生成有意义的PROC
MSSQL 生成有意义的PROC --MSSQL 用PROC 生成有意义的单号:如WP200011101 GO/****** 对象: Table [dbo].[tbl_SequenceNum] ...
-
在浏览器中运行Keras模型,并支持GPU
Keras.js 推荐一下网页上的 demo https://transcranial.github.io/keras-js/#/ 加载的比较慢,但是识别的非常快. Run Keras models ...
-
chrome启动参数之
--remote-debugging-port Chrome 启动的时候,默认是关闭了调试端口的,如果要对一个目标 Chrome PC 浏览器进行调试,那么启动的时候,可以通过传递参数来开启 Chro ...
-
Ubuntu 18.04 LTS搭建GO语言开发环境
一.下载Go语言安装包 官网下载地址:https://golang.org/dl/,使用tar命令将档案包解压到/usr/local目录中: sudo tar -C /usr/local -xzf g ...
-
Python enum 枚举 判断 key(键) 或者 value(值)是否在枚举中
Python enum 枚举 判断 key(键) 或者 value(值)是否在枚举中 python 的基本用法请浏览:https://www.cnblogs.com/ibingshan/p/98564 ...
-
python爬取商品信息
老严要爬某网购网站的商品信息,正好我最近在学python,就一起写了一个简单的爬虫程序. 需求:某网的商品信息,包括商品名,市场价和售价 工具:python2.7.8,urllib2,re #codi ...
-
Path Sum I&;&;II
I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up ...