CodeForces 1060 B Maximum Sum of Digits
Maximum Sum of Digits
You are given a positive integer n.
Let S(x)S(x) be sum of digits in base 10 representation of xx , for example, S(123)=1+2+3=6S(123)=1+2+3=6 , S(0)=0S(0)=0 .
Your task is to find two integers a,ba,b , such that 0≤a,b≤n0≤a,b≤n , a+b=na+b=n and S(a)+S(b)S(a)+S(b) is the largest possible among all such pairs.
Input
The only line of input contains an integer nn (1≤n≤1012)(1≤n≤1012) .
Output
Print largest S(a)+S(b)S(a)+S(b) among all pairs of integers a,ba,b , such that 0≤a,b≤n0≤a,b≤n and a+b=na+b=n .
Examples
35
17
10000000000
91
Note
In the first example, you can choose, for example, a=17a=17 and b=18b=18 , so that S(17)+S(18)=1+7+1+8=17S(17)+S(18)=1+7+1+8=17 . It can be shown that it is impossible to get a larger answer.
In the second test example, you can choose, for example, a=5000000001a=5000000001 and b=4999999999b=4999999999 , with S(5000000001)+S(4999999999)=91S(5000000001)+S(4999999999)=91 . It can be shown that it is impossible to get a larger answer.
解题思路:
给出一个数字n,将他拆分为2个数字,使拆分的两个数字每一位相加的和最大,输出相加后的和。
个人感觉不用管下面提示。我们本着贪心的思想,希望获得尽可能多的9,就是将35,拆分为9与26,将10000000000,拆分为9999999999与1,既将原始数字拆分为比其第一位的全由9组成的数字与另一个补偿数字,补偿数字为原始数字减去拆分的全9数字。之后将拆分的两个数字所有位都相加便可以得到答案。
#include<iostream>
#include<sstream>
#include<string>
#include<cstdio>
//CodeForces不支持万能头文件bits/stdc++.h
using namespace std;
typedef long long ll;
string n;
ll power(int a, int b){ //快速幂
ll ans = ;
while(b){
if(b & ){
ans = ans * a;
}
a = a * a;
b >>= ;
}
return ans;
}
int main()
{
ll a, b;
while(cin >> n)
{
int suma=;
int sumb=;
a = power(, n.size() - );
//若想拆分出小于且9最多的数字,只需要找到n的位数n.size() - 1
//之后便可以用10的n.size() - 1次幂找到与n位数相等数字中最小数字
//减一便可以得到我们所要拆分的数字
istringstream cinn(n);
cinn >> b;
//先用istringstream读取n中的值输入到整形b中
//b - a就是补偿的数字。
a--;
b = b - a;
while(a) //将a的每一位加起来
{
suma += a % ;
a/=;
}
while(b)
{
sumb += b % ; //将b的每一位加起来
b/=;
}
cout << suma + sumb << endl; //所有位数加和
}
return ;
}
最新文章
- MVC5+EF6 入门完整教程六
- Nginx+Keepalived(带Nginx监控脚本)
- Oracle数据库初级学习
- <;a>;标签的href和onclick属性
- [moka同学笔记]yii2.0小物件的简单使用(第一种方法)
- [Java] Java 打包成jar包 和 解压jar包
- php像新浪微博一样生成短域名
- 关于java.lang.String理解中的一些难点
- HTML5拖拽功能drag
- Vue.js快速入门
- C#_会员管理系统:开发二(会员资料管理界面的‘增删改查’)
- 【NOIP2007提高组】字符串展开
- mysql metadata lock
- 一步一步带你实现virtual dom(二) -- Props和事件
- LeetCode算法题-Happy Number(Java实现)
- javascript的性能优化tips
- $Django cbv源码分析 djangorestframework框架之APIView源码分析
- Embedded SW uses STL or not
- POI导出Word插入复选框
- dstat 性能监测工具