[UVA][greedy+字串] 10333 - The Tower of ASCII
The Tower of ASCII
| The Tower of ASCII |
The tower of ASCII is a nice tower made of asterisk (*) , hash sign (#) and periods (.) . A sample tower could be :
#****# #**....**# #........# #**........**# #............# #............# #**............# #..............# #..............# #..............# Fig : Tower of Height 10The tower of ASCII (TOA) has the following properties :
1. It has a fixed height, H.
2. Its external architecture is made up of several pieces of different sizes like :
#** **# **# **# #** # # # # # # # # # 1 2 3 4 5 So there are two types of piece. One is T-shape(1,5) and another is 1-shape(2,3,4). T-shape pieces construct the Left part of TOA whether 1-shape pieces make the right part. Each piece width is fixed which is 3. But the height can be any positive integer. The intermediate spaces is filled with period.3. The number of pieces in Left part is always 1 more than that of right part. In the example TOA in left part pieces of 4,3,2,1 height and in right part pieces of 7,2,1 height have been used.
4. The total number of pieces used in a TOA is it's cardinality. In our example the cardinality is 4+3=7. A TOA of fixed height also has a fixed cardinality.
5. In each part pieces of greater height will precede pieces of less height. In the given example no alternation of ( 4,3,2,1 ) order is possible. And also pieces of same height can be used only once in one part.
6. There is one and only one TOA of height H.
The Problem
As specified in the properties that for a particular height the cardinality is fixed. To ensure this, the maximum possible cardinality is chosen for a TOA. Thus in our example 7 is the maximum cardinality for height,10. To make the TOA unique in each part the pieces of maximum height are chosen. Such as in case of TOA of height 12 the left part could be ( 6,3,2,1 ) or ( 5,4,2,1 ). Whether the right part could be ( 9,2,1 ) or ( 8,3,1 ) or ( 7,3,2 ) or ( 7,4,1 ) etc. But only ( 6,3,2,1 ) and ( 9,2,1 ) will be considered for the left and right part.
Lets come to your task. You have to build a TOA of given height H using T-shape and 1-shape piece. You may consider each piece of any height is available.
The Input
The input will contain an integer H (5<=H<=500) per line. Input is terminated by EOF.
The Output
The output specification starts with a line "Tower : #N" where N is the current TOA. In next H lines you have to draw the TOA of height H. Look in each line the starting hash sign may contain leading spaces but the ending hash sign should not be followed by any space. You have to use a line break after each ending hash sign. Print a blank line after each TOA.
Sample Input
5 10
Sample Output
Tower #1
#****#
#**....#
#......#
#......#
#......#
Tower #2
#****#
#**....**#
#........#
#**........**#
#............#
#............#
#**............#
#..............#
#..............#
#..............#
很明顯地，會發現層數的高低一定是個 greedy, 盡可能每次只多 1。
Md. Kamruzzaman
題目描述：
//cardinality：基數，也就是相當於集合 S，所有元素個數 |S| 即為基數。
左邊的層數一定比右邊多一層，而且基數越大越好，然後最後一個越大越好。
而每一層都是嚴格遞增。
題目解法：
然後右邊的最後一層一定是左邊的最後兩層加起來。
輸出會稍微麻煩一點，要動點腦筋去處理。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char ret[505][505];
int main() {
int H, cases = 0;
int i, j, k;
while(scanf("%d", &H) == 1) {
printf("Tower #%d\n", ++cases);
int sum = 0;
int left[1000], lidx = 0;
int right[1000], ridx = 0;
for(i = 1; ; i++) {
if(sum+i+i+1 > H) break;
left[lidx++] = i;
sum += i;
}
if(sum != H) left[lidx++] = H-sum;
for(i = 0; i < lidx-2; i++)
right[ridx++] = left[i];
right[ridx++] = left[lidx-1]+left[lidx-2];
int baseX1, baseX2;
baseX1 = (lidx-1)*2;
baseX2 = baseX1+5;
lidx = ridx = 0;
int leftnew = 1, rightnew = 1;
for(i = 0; i < H; i++) {
if(left[lidx] == 0) {
leftnew = 1;
baseX1 -= 2, lidx++;
}
if(right[ridx] == 0) {
rightnew = 1;
baseX2 += 2, ridx++;
}
left[lidx]--, right[ridx]--;
for(j = 0; j < baseX1; j++)
putchar(' ');
putchar('#');
int tmp = baseX1+1;
if(leftnew)
putchar('*'), putchar('*'), tmp += 2;
if(rightnew)
tmp += 2;
for(j = tmp; j < baseX2; j++)
putchar('.');
if(rightnew)
putchar('*'), putchar('*');
putchar('#');
leftnew = 0;
rightnew = 0;
puts("");
}
puts("");
}
return 0;
}