|
C. One-Based Arithmetic
time limit per test
0.5 seconds memory limit per test
256 megabytes input
standard input output
standard output Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. 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 Output
6 |
http://codeforces.com/contest/440/problem/C
用一堆由1组成的数来加减得到某数，输入某数，求最少要用多少个1。
深搜！由于这题的性质，每次搜肯定能得到一个解，然后之后搜的时候用的1数大于这个解，就可以跳出，怒剪了一大波枝。（最优性剪枝）
就是从最高位开始，慢慢把位削成0。因为把第i位消除成0后，可以选择数保证这一位不会再变回1，所以就一位一位消下去就行。
深搜只有两种方向，例如第i位是x，第一种方向就是搞x个11111把它消了，另一种是搞一堆11111把它加上去，然后搞一个多一位的111111把它再消掉，这两种都有可能，而其他的方法都不如这2种。
所以哐哐哐就是搜啦！搜啊！
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std; typedef long long ll; int ans,len;
ll one[]={,,,,,,,,,,
1111111111LL,11111111111LL,111111111111LL,1111111111111LL,
11111111111111LL,111111111111111LL,1111111111111111LL};
void dfs(ll x,int sum)
{
int a,b;
if(sum>=ans) return;
if(x==)
{
ans=sum;
return;
}
if(x<) x=-x;
ll y=x;
int t=;
while(y!=) t++,y/=;
ll reta=x,retb=one[t+]-x;
ll h=pow(,t-);
int sa=,sb=t+;
while(reta>=h) reta-=one[t],sa+=t;
while(retb>=h) retb-=one[t],sb+=t;
dfs(reta,sum+sa);
dfs(retb,sum+sb);
return;
} int main()
{
ll x;
while(scanf("%I64d",&x)!=EOF)
{
ans=1e9;
dfs(x,);
printf("%d\n",ans);
}
return ;
}