「CF440C」One – Based Arithmetic

2014年6月4日3,5130

Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.

Input

The first line of the input contains integer n (1 ≤ n < 1015).

Output

Print expected minimal number of digits 1.

Sample test(s)

input

121

121

output

6

题解

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,f[18];
int cal(ll x)
{ 
    int res,i=16;
    if(x<=11)return min(x,2+11-x);
    while(f[i-1]>=x)i--;
    res=((x/f[i-1])*(i-1))+cal(x%f[i-1]);
    if(x<f[i]-x)return res;
    return min(res,i+cal(f[i]-x));
}
int main()
{
    f[1]=1;
    for(int i=2;i<=16;i++)f[i]=10*f[i-1]+1;
    scanf("%I64d",&n);
    printf("%d",cal(n));
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

ll n,f[18];

int cal(ll x)

{

int res,i=16;

if(x<=11)return min(x,2+11-x);

while(f[i-1]>=x)i--;

res=((x/f[i-1])*(i-1))+cal(x%f[i-1]);

if(x<f[i]-x)return res;

return min(res,i+cal(f[i]-x));

}

int main()

{

f[1]=1;

for(int i=2;i<=16;i++)f[i]=10*f[i-1]+1;

scanf("%I64d",&n);

printf("%d",cal(n));

return 0;

}

« 「NOIP模拟赛」密码锁「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果 »

hzwer.com _ Home | http://hzwer.com

「CF440C」One – Based Arithmetic

分类目录

热门文章

Myfriends

近期评论