Problem B
Minimum Weight
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

You have to weigh all integral weights from 1 to N. You can use weights in either pan. Such as if you have weight 2 and 3. You can weigh 1 using 3 in one pan and 2 in other pan. You can also weigh 5 (3+2=5) though you cannot weigh 4.

For a given N, you have to find out minimum number of weights which are enough to weigh any integral weight from 1 to N.

Input 

The input file contains several sets of inputs. The description of each set is given below:

First line of each set contains two integers N (Fits within signed 64-bit integer) and K (0<=K<=100). The next line contains K positive integers less than N. You have to show a combination of weights which will make those weights.

Input is terminated by a case where N and K both are zero. This case should not be processed.

Output 

For each set of input produce (K+1) lines of output.

In the first line print the total number of weights required to measure all the integral weights from 1 to N.

For each input print minimum number of weights required followed by the weights in ascending order. If multiple output is possible, take the combination which contains largest weights.
Next show the combination of these weights to make the weight for each query. The weights should be in descending order irrespective of sign.

Sample Input                             Output for Sample Input

Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters' Panel

請非常小心 overflow 問題。

#include <stdio.h>

int main() {
	long long N;
	int K, i, j, k, n;
	while(scanf("%lld %d", &N, &K) == 2 && N) {
		long long w[100] = {1};
		for(n = 0; (w[n]*3-1)/2 < N && n < 39; n++) {
			w[n+1] = w[n] * 3;
		}
		printf("%d", n+1);
		for(i = 0; i <= n; i++)
			printf(" %lld", w[i]);
		puts("");
		while(K--) {
			scanf("%lld", &N);
			for(i = 0; i <= n; i++) {
				if(i == n || (w[i+1] - 1) / 2 >= N) {
					printf("%lld", w[i]);
					N -= w[i];
					for(i--; i >= 0; i--) {
						if(N < 0 && N + w[i] <= (w[i]-1)/2)
							printf("-%lld", w[i]), N += w[i];
						else if(N > 0 && N - w[i] >= -(w[i]-1)/2)
							printf("+%lld", w[i]), N -= w[i];
						//printf("%lld\n", N);
					}
					puts("");
					break;
				}
			}
		}
	}
	return 0;
}

您可能對以下文章有興趣

[UVA][大數] 324 - Factorial Frequencies

[UVA][greedy] 10716 - Evil Straw Warts Live

[UVA][SCC、Tarjan算法] 11709 - Trust groups

[UVA] 12485 - Perfect Choir