「CF509C」Sums of Digits

2015年1月31日3,2751

Vasya had a strictly increasing sequence of positive integers a₁, …, a_n. Vasya used it to build a new sequence b₁, …, b_n, where b_i is the sum of digits of a_i‘s decimal representation. Then sequence a_i got lost and all that remained is sequence b_i.

Vasya wonders what the numbers a_i could be like. Of all the possible options he likes the one sequence with the minimum possible last number a_n. Help Vasya restore the initial sequence.

It is guaranteed that such a sequence always exists.

Input

The first line contains a single integer number n (1 ≤ n ≤ 300).

Next n lines contain integer numbers b₁, …, b_n — the required sums of digits. All b_i belong to the range 1 ≤ b_i ≤ 300.

Output

Print n integer numbers, one per line — the correct option for numbers a_i, in order of following in sequence. The sequence should be strictly increasing. The sum of digits of the i-th number should be equal to b_i.

If there are multiple sequences with least possible number a_n, print any of them. Print the numbers without leading zeroes.

Sample test(s)

input

output

1
2
3

input

output

3
11
100

100

题解

贪心

若bi大于bi-1，就从低位一个个变成9，高位复制上一个答案

否则从选一位+1，低于它的位数清0，再从低位开始一个个放9，高位复制上一个答案

注意，可以构造出最终答案在340位。。

赛后突然想起来TAT 跪烂了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define inf 1000000000
#define rad 100000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[305][505],b[305];
int l[305];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)b[i]=read();
    l[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(b[i]>b[i-1])
        {
            int now=1,rem=b[i]-b[i-1];
            for(;rem;now++)
            {
                int t=min(rem,9-a[i-1][now]);
                a[i][now]=a[i-1][now]+t;rem-=t;
            }
            for(int j=now;j<=l[i-1];j++)a[i][j]=a[i-1][j];
            l[i]=max(now-1,l[i-1]);
        }
        else 
        {
            int now=1,rem=b[i]-b[i-1]-1,sum=1;
            for(;rem<0||a[i-1][now]==9||sum<b[i]-b[i-1];now++)
            {
                rem+=a[i-1][now];
                sum+=(9-a[i-1][now]);
            }
            a[i][now]=a[i-1][now]+1;
            for(int j=now+1;j<=l[i-1];j++)a[i][j]=a[i-1][j];
            for(int j=1;rem>0;j++)
                a[i][j]=min(rem,9),rem-=a[i][j];
            l[i]=max(now,l[i-1]);
        }
        for(int j=l[i];j;j--)
            printf("%d",a[i][j]);
        puts("");
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define inf 1000000000

#define rad 100000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[305][505],b[305];

int l[305];

int main()

{

n=read();

for(int i=1;i<=n;i++)b[i]=read();

l[0]=1;

for(int i=1;i<=n;i++)

{

if(b[i]>b[i-1])

{

int now=1,rem=b[i]-b[i-1];

for(;rem;now++)

{

int t=min(rem,9-a[i-1][now]);

a[i][now]=a[i-1][now]+t;rem-=t;

}

for(int j=now;j<=l[i-1];j++)a[i][j]=a[i-1][j];

l[i]=max(now-1,l[i-1]);

}

else

{

int now=1,rem=b[i]-b[i-1]-1,sum=1;

for(;rem<0||a[i-1][now]==9||sum<b[i]-b[i-1];now++)

{

rem+=a[i-1][now];

sum+=(9-a[i-1][now]);

}

a[i][now]=a[i-1][now]+1;

for(int j=now+1;j<=l[i-1];j++)a[i][j]=a[i-1][j];

for(int j=1;rem>0;j++)

a[i][j]=min(rem,9),rem-=a[i][j];

l[i]=max(now,l[i-1]);

}

for(int j=l[i];j;j--)

printf("%d",a[i][j]);

puts("");

}

return 0;

}

« 「CF509B」Painting Pebbles 「CF516A」Drazil and Factorial »

小小腮帮

代码好短ORZORZ

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

「CF509C」Sums of Digits

分类目录

热门文章

Myfriends

近期评论