AT_abc200_e [ABC200E] Patisserie ABC 2

题目描述

在“ABC洋菓子店”工作的糕点师高桥君，为了庆祝 AtCoder Beginner Contest 200，决定制作蛋糕。

高桥君制作的蛋糕有“美丽度”、“美味度”、“人气度”三个参数，每个参数都是 $1$ 到 $N$ 之间的整数。

高桥君为每一种“美丽度”$i$、“美味度”$j$、“人气度”$k$（$1 \leq i, j, k \leq N$）的组合各制作了一个蛋糕。
然后，他将制作好的 $N^3$ 个蛋糕按照以下顺序排列：

• “美丽度”$+$“美味度”$+$“人气度”之和较小的蛋糕排在更左边。
• 如果和相同，则“美丽度”较小的蛋糕排在更左边。
• 如果仍然相同，则“美味度”较小的蛋糕排在更左边。

请你求出从左起第 $K$ 个蛋糕的各参数值。

输入格式

输入为一行，包含两个整数：

$N$ $K$

输出格式

请输出“美丽度”、“美味度”、“人气度”，以空格分隔的三个整数。

输入输出样例 #1

输入 #1

2 5

输出 #1

1 2 2

输入输出样例 #2

输入 #2

1000000 1000000000000000000

输出 #2

1000000 1000000 1000000

输入输出样例 #3

输入 #3

9 47

输出 #3

3 1 4

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 10^6$
• $1 \leq K \leq N^3$

样例解释 1

将每个蛋糕的参数写作（美丽度, 美味度, 人气度），蛋糕从左到右的排列顺序如下：$(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)$

样例解释 2

输入的数值也可能很大。

由 ChatGPT 4.1 翻译