tux 的飞行编队安排 (Hard Version)

题目描述

今年是国庆 75 周年，tux 想安排一场飞行表演来庆祝国庆。为了让表演更加壮观，参与表演的飞机数量要尽可能多，但是 tux 最多只能使用 $n$ 架飞机（可以使用小于等于 $n$ 架）。编队必须严格排列成如下格式的 “75” 形状（星号代表飞机）：

****    ****
   *    *
   *    *
  *     ****
  *        *
 *         *
 *      ****

图形解释：设图形中 “7” 和 “5” 的横向宽度为 $k$（$k \ge 3 $，图中为 $4$），则 “7” 的纵向高度为 $2k-1$，“7” 的竖线略有倾斜，斜率为 $2$ 。“5” 共有三条横线，相邻的横线之间有 $k-2$ 行。“7” 和 “5” 之间用 $k$ 个空格隔开，“7” 左侧没有空格，上方没有空行。

输入

一个数，表示 tux 最多能使用 $n$ 架飞机，$18 \le n \le 4000$.

输出

若干行字符，表示在使用不超过 $n$ 架飞机的条件下可以形成的最大编队安排。飞机用星号*表示。

输入样例1

42

输出样例1

******      ******
     *      *
     *      *
    *       *
    *       *
   *        ******
   *             *
  *              *
  *              *
 *               *
 *          ******

样例解释1

$k=6$，全部 $42$ 架飞机均参与表演。

输入样例2

25

输出样例2

***   ***
  *   *
  *   ***
 *      *
 *    ***

样例解释2

排成 $k=3$ 的编队至少需要 $18$ 架飞机，排成 $k=4$ 的编队至少需要 $26$ 架飞机。现有 $25$ 架飞机，最多只够满足 $k=3$ 的编队。

Hint

试着用 $k$ 表示编队飞机的数目，寻找 $n$ 和 $k$ 的关系。

---

Author: