2014
02-23

# Bigger is Better

Bob has n matches. He wants to compose numbers using the following scheme (that is, digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 needs 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 matches):

Write a program to make a non-negative integer which is a multiple of m. The integer should be as big as possible.

The input consists of several test cases. Each case is described by two positive integers n (n ≤ 100) and m (m ≤ 3000), as described above. The last test case is followed by a single zero, which should not be processed.

The input consists of several test cases. Each case is described by two positive integers n (n ≤ 100) and m (m ≤ 3000), as described above. The last test case is followed by a single zero, which should not be processed.

6 3
5 6
0

Case 1: 111
Case 2: -1

dp[i][j]+1==dp[newi][newj]满足的话，那么如果dp[newi][newj]存在的话，那么新增的K就是下一位，用next[i][j]表示当前状态的下一个数

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
const int MAXM = 3010;
const int used[10] = {6,2,5,5,4,5,6,3,7,6};

int dp[MAXN][MAXM],next[MAXN][MAXM];
int n,m,maxlen;

int main(){
int cas = 0;
while (scanf("%d",&n) != EOF && n){
scanf("%d",&m);
memset(dp,-1,sizeof(dp));
dp[0][0] = 0,maxlen = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (dp[i][j] >= 0)
for (int k = 9; k >= 0; k--)
if (i + used[k] <= n){
int newi = i+used[k],newj = (j*10+k)%m;
if (dp[i][j] + 1 > dp[newi][newj]){
dp[newi][newj] = dp[i][j] + 1;
if (dp[newi][newj] > maxlen && newj == 0)
maxlen = dp[newi][newj];
}
}
memset(next,-1,sizeof(next));
for (int i = n; i >= 0; i--)
for (int j = 0; j < m; j++)
if (dp[i][j] >= 0){
if (dp[i][j] == maxlen && j == 0){
next[i][j] = 10;
continue;
}
for (int k = 9; k >= 0; k--){
if (i + used[k] <= n){
int newi = i + used[k];
int newj = (j*10+k)%m;
if (dp[newi][newj] == dp[i][j] + 1 && next[newi][newj] >= 0){
next[i][j] = k;
break;
}
}
}
}
printf("Case %d: ",++cas);
int i,j,u,v;
if (maxlen > 0){
i = 0,j = 0;
while (next[i][j] != 10){
u = i + used[next[i][j]];
v = (j*10+next[i][j]) % m;
printf("%d",next[i][j]);
i = u,j = v;
}
printf("\n");
}
else if (n >= used[0])
printf("0\n");
else printf("-1\n");
}
return 0;
}

1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}