hdu 4608 I-number

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数学

【2013多校联合训练第一场】

题意:略

应该是今天最水的一题,做法很简单。对于给出的数字统计各位数的和为sum,那么看看它距离能被10整除还有多少,delta = 10 - sum%10,也就是说这个sum + delta新的和一定能被10整除,对于原数字就是在个位上加。如果原数字个位加上delta没有发生进位,那么这个就是答案了。如果发生了进位,则不是,并且整个计算都打乱了,要重新来。所以进位了话,不用加上delta 这么多,直接令到个位为0即可,然后搞出新的数字。对于新的数字,再求一次sum,delta,重复的工作………..其实这题怎么写都可以的,我的同学直接用更暴力的方法,一直加1,直到找到答案为止,其实这样也不会超时的,因为可以知道加1的次数不会超过20次(更少一些,没有准确计算证明,但是加20次肯定出答案),所以就暴力点吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010

int a[N],len;

void solve(int sum,int delta){
while(true){
if(a[0] + delta < 10){
a[0] += delta; break;
}
a[0] = 0;
int c = 1;
for(int i = 1;i < len; i++){
a[i] += c;
c = a[i] / 10;
if(a[i] < 10) break;
a[i] %= 10;
}
if(c) a[len++] = c;
sum = 0;
for(int i = 0; i < len; i++)
sum += a[i];
if(sum % 10 == 0) break;
delta = 10 - sum%10;
}
for(int i = len-1; i >= 0 ; i--)
printf("%d",a[i]);
printf("\n");
}

int main(){
char temp[N];
int cas;
int sum,delta;
scanf("%d",&cas);
while(cas--){
scanf("%s",temp);
len = strlen(temp);
sum = 0;
for(int i = 0,j = len-1; j>=0; j--,i++){
a[i] = temp[j] - '0';
sum += a[i];
}
delta = 10 - sum%10;
solve(sum,delta);
}
return 0;
}