程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 509C. Sums of Digits 貪心枚舉

Codeforces 509C. Sums of Digits 貪心枚舉

編輯:C++入門知識

Codeforces 509C. Sums of Digits 貪心枚舉



貪心枚舉,代碼裡的注釋很詳細

C. Sums of Digits time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Vasya had a strictly increasing sequence of positive integers a1, ..., an. Vasya used it to build a new sequence b1, ..., bn, where bi is the sum of digits of ai's decimal representation. Then sequence ai got lost and all that remained is sequence bi.

Vasya wonders what the numbers ai could be like. Of all the possible options he likes the one sequence with the minimum possible last number an. 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 b1, ..., bn — the required sums of digits. All bi belong to the range 1?≤?bi?≤?300.

Output

Print n integer numbers, one per line — the correct option for numbers ai, 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 bi.

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

Sample test(s) input
3
1
2
3
output
1
2
3
input
3
3
2
1
output
3
11
100

/* ***********************************************
Author        :CKboss
Created Time  :2015年02月06日 星期五 15時31分06秒
File Name     :CF509C.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
int b[333];
int pos[333];
int num[333][500];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",b+i);
   	pos[0]=1; 

	/// 第一個數 貪心
	int temp=b[1];
	if(temp==0) num[1][pos[1]++]=0;
	while(temp>0)
	{
		if(temp>=9) { temp-=9; num[1][pos[1]++]=9; }
		else { num[1][pos[1]++]=temp; temp=0; }
	}

	/// 剩下的數 貪心
	for(int i=2;i<=n;i++)
	{
		int lastsum=b[i-1];/// 上一位的已經確定的數字和
		bool flag=false;
		for(int j=0;flag==false;j++) /// 枚舉位置
		{
			if(j-1>=0) lastsum-=num[i-1][j-1];

			///枚舉所在的位加多少
			for(int k=num[i-1][j]+1;k<=9&&flag==false;k++)
			{
				int add = k-num[i-1][j];
				/// 剩下的數的范圍可以在 0 ~ 9*j 之間
				if(j-1>=0)
				{
					if(lastsum+add<=b[i]&&lastsum+add+9*j>=b[i]) /// 成功
					{
						flag=true;
						pos[i]=max(j+1,pos[i-1]);
						/// 貪心部分的值 val
						int val = b[i]-lastsum-add;
						int tn=0;
						while(val>0)
						{
							if(val>=9) { val-=9; num[i][tn++]=9; }
							else { num[i][tn++]=val; val=0; }
						}
						/// 枚舉的那一位
						num[i][j]=k;
						/// 如果存在的不變部分
						for(int kk=j+1;kk=0;j--) 
			printf("%d",num[i][j]); 
		putchar(10);
	}
	
    return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved