## 165 – StampsTime limit: 3.000 seconds |

Stamps |

This has been analysed by government mathematicians who have derived a formula for *n*(*h*,*k*), where *h* is the number of stamps that may be attached to a document, *k* is the number of denominations of stamps available, and *n* is the largest attainable value in a continuous sequence starting from $1. For instance, if *h*=3, *k*=2 and the denominations are $1 and $4, we can make all the values from $1 to $6 (as well as $8, $9 and $12). However with the same values of *h* and *k*, but using $1 and $3 stamps we can make all the values from $1 to $7 (as well as $9). This is maximal, so *n*(3,2) = 7.

Unfortunately the formula relating *n*(*h*,*k*) to *h*, *k* and the values of the stamps has been lost–it was published in one of the government reports but no-one can remember which one, and of the three researchers who started to search for the formula, two died of boredom and the third took a job as a lighthouse keeper because it provided more social stimulation.

The task has now been passed on to you. You doubt the existence of a formula in the first place so you decide to write a program that, for given values of *h* and *k*, will determine an optimum set of stamps and the value of *n*(*h*,*k*).

## Input

Input will consist of several lines, each containing a value for *h* and *k*. The file will be terminated by two zeroes (0 0). For technical reasons the sum of *h* and *k* is limited to 9. (The President lost his little finger in a shooting accident and cannot count past 9).

## Output

Output will consist of a line for each value of *h* and *k* consisting of the *k* stamp values in ascending order right justified in fields 3 characters wide, followed by a space and an arrow (`->`

) and the value of *n*(*h*,*k*) right justified in a field 3 characters wide.

## Sample input

1 2 |
3 2 0 0 |

## Sample output

1 |
1 3 -> 7 |

题意是给出h，k，h是一张信封上面最多可以贴的邮票数目，k是邮票最多的面值个数，然后求邮票可以组成的连续面值的最大数的最大值n(h, k)是多少，比如h，k分别为3 2 的时候，邮票的面值种类分别为1和3时，邮票可以组成的面值分别为1 2 3 4 5 6 7 9，故连续数的最大数是7，然后遍历所有情况过后连续数最大数的最大值是7，故n(h, k) = 7。

已知对于每一对h、k，n(h, k)都有一个固定的值，所以可以先假设h一定，然后分别求n(h, 1), n(h, 2)…直至求到n(h, k)，然后还必须知道的是对于第i张邮票ai，ai对应的是n(h, i)，ai的面值取值范围是(a(i-1), n(h,i-1)+1]。

剩下的就开始暴力吧！

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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
/******************************************************** * File Name: uvaoj165.cpp * Author: razrLeLe * Mail: razrlele@gmail.com * Homepage: https://yueyu.io * Created Time: Tue 10 Mar 2015 02:43:50 PM CST ******************************************************/ #include "vector" #include "set" #include "deque" #include "queue" #include "algorithm" #include "functional" #include "iostream" #include "cstdio" #include "cmath" #include "cstdlib" #include "string" #include "cstring" #include "string.h" #include "map" #include "cctype" #include "list" #include "stack" using namespace std; #define INF 0x3f3f3f3f #define LOCAL int h, k; int maxValue[10]; int stampValue[10]; bool occured[200]; int ans[10], ansMax; void dfs(int cur, int sum, int count){ occured[sum] = true; if(count == h) { return; } for(int i = 1; i <= cur; i++ ) dfs(cur, sum+stampValue[i], count+1); return ; } void solve(int cur){ if(cur == k){ if(ansMax < maxValue[cur]){ ansMax = maxValue[cur]; for(int i = 1; i <= k; i++){ ans[i] = stampValue[i]; } } return ; } for(int i = stampValue[cur]+1; i <= maxValue[cur]+1; i++){ memset(occured, false, sizeof(occured)); stampValue[cur+1] = i; dfs(cur+1, 0, 0); int tmp = maxValue[cur], tmpflag = maxValue[cur]+1; while(occured[tmpflag++]) tmp++; maxValue[cur+1] = tmp; solve(cur+1); } return ; } int main() { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif while(scanf("%d%d", &h, &k)){ if(h+k == 0) { break; } ansMax = 0; maxValue[1] = h; stampValue[1] = 1; solve(1); for(int i = 1; i <= k; i++){ printf("%3d", ans[i]); } printf(" ->%3d\n", ansMax); } return 0; } |