Skip to content

11600: 【原1600】A number

题目

题目描述

author: xzj 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1600

Description

一个十进制非负整数称为A类数,当且仅当它仅由0或1构成。例如0,10,11,1010,1100101都是A类数。给定十进制非负整数n,将n拆分成个数最少的A类数的和,输出最少的加数的个数。

Input Format

一个整数n。

Output Format

最少的加数的个数。

Sample Input

53

Sample Output

5

样例说明

一种拆分方式为53 = 10+10+11+11+11,加数有5个。可以证明53不能够被表示为4个或4个以下的A类数的和,因此输出5。

数据范围

  • 对于50%的数据,n不超过10^3;
  • 对于70%的数据,n不超过10^18;
  • 对于100%的数据,n不超过10^1000。

yyong119's solution

#include <cstdio>
using namespace std;
char ch;
int k;
int main() {
    ch = getchar();
    while (ch >= '0' && ch <= '9') {
        if (ch > k) k = ch;
        ch = getchar();
    }
    printf("%d", k ^ 48);
    return 0;
}