Algorithm

B1027. 打印沙漏

随着题目难度的不断增加，这道题目已经不再是像以前那样简单的判断和输出了。

需要对“沙漏”这个模型进行足够的分析，并总结其中隐藏的规律。题目给出的正整数 N 是任意至，不一定刚好能够组成一个“沙漏”的形状，可能是有剩余的，且题目也要求求出最后剩余的数量。

其实这就是一个数学问题罢了。根据提供的正整数，求出能够组成最大的沙漏的个数。最后打印沙漏那就是分分钟的事儿。我们假设 n（n 为正整数）为第一排沙漏字符的个数，则上三角部分所需要的字符数为 (n + 1)^2 / 4（因为每一行沙漏都相差两个字符），故总的沙漏字符数为 (n + 1)^2 / 2 - 1。根据 (n + 1)^2 / 2 - 1 <= N 可得， -sqrt(2 * (N + 1)) <= n <= sqrt(2 * (N + 1))。又因为 n 为正整数，故 n = [sqrt(2 * (N + 1))]。至此，问题就迎刃而解了。

最后提供一下自己的解决方案：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void printRow(int row, int n, char ch) {
    int blankCol = (n - row) / 2;
    for(int i = 0; i < blankCol; i++) {
        printf(" ");
    }
    for(int i = blankCol; i < blankCol + row; i++) {
        printf("%c", ch);
    }
    printf("\n");
}
int main() {
    int N = 0;
    char ch;
    scanf("%d %c", &N, &ch);

    // Calculate the max n
    int n = floor(sqrt(2 * (N + 1)) - 1);
    if(n % 2 == 0) {
        n--;
    }

    int remain = N - ((n + 1) * (n + 1) / 2 - 1);
//    printf("n: %d, remain: %d\n", n, remain);

    // Print the pattern
    for(int i = n; i > 0; i -= 2) {
        printRow(i, n, ch);
    }

    for(int i = 3; i <= n; i += 2) {
        printRow(i, n, ch);
    }

    printf("%d", remain);
    return 0;
}