One Chance To Be The God Of Chrysanthemum
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 132 Accepted Submission(s) : 27
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Last week xysDavid had gone for an interview. The interviewer asked him a funny question. Here is it.
Given a number n, your mission is to find a set, that every number between 1 and n (inclusive) can be the sum of some elements in this set.
xysDavid seckilled it soon after reading the statement. If you can solve the problem too, xysDavid will accept you to be his apprentice, who can get the honorary title 'the god of chrysanthemum'.
Can you finish it?
Given a number n, your mission is to find a set, that every number between 1 and n (inclusive) can be the sum of some elements in this set.
xysDavid seckilled it soon after reading the statement. If you can solve the problem too, xysDavid will accept you to be his apprentice, who can get the honorary title 'the god of chrysanthemum'.
Can you finish it?
Input
There is a number T (1<=T<=50) in the first line, indicating the number of test cases.
There is a number n in each line. (1<=n<=10^18);
There is a number n in each line. (1<=n<=10^18);
Output
You should output "Case #D:" first, which "D" means the index of the test case.
Then output all the numbers in the set in one line in increasing order. Use one space to separate two numbers. Please note that no more spaces in the end of a line.
If there are multiple answers, output the one with smallest number of elements. If it is still a tie, output the one with the smallest lexicographical order.
The comparison between two sequences uses lexicographical ordering: first, the first two numbers are compared, and if they differ this determines the outcome of the comparison; if they are equal, the next two numbers are compared, and so on, until either sequence is exhausted. If all numbers of two sequences compare equal, the sequences are considered equal. If one sequence is an initial subsequence of the other, the shorted sequence is considered the smaller one.
Then output all the numbers in the set in one line in increasing order. Use one space to separate two numbers. Please note that no more spaces in the end of a line.
If there are multiple answers, output the one with smallest number of elements. If it is still a tie, output the one with the smallest lexicographical order.
The comparison between two sequences uses lexicographical ordering: first, the first two numbers are compared, and if they differ this determines the outcome of the comparison; if they are equal, the next two numbers are compared, and so on, until either sequence is exhausted. If all numbers of two sequences compare equal, the sequences are considered equal. If one sequence is an initial subsequence of the other, the shorted sequence is considered the smaller one.
Sample Input
2 1 3
Sample Output
Case #1: 1 Case #2: 1 2
Source
华南师范大学·2012年ACM程序设计竞赛·决赛